본문 바로가기

분류 전체보기

 (386)
[boj] 백준 1043 거짓말 (Java) - 유니온 파인드 [문제] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net [풀이] 진실을 아는 사람과 같이 파티에 참석했던 사람들은 진실을 알게 된다. 1. 같이 파티에 참석한 사람들이 같은 parent를 갖도록 union 해준다. 2. 진실을 아는 사람의 최종 parent는 같은 파티에 참석했으므로 진실을 알게된다. knowTruth에 체크해준다. 3. 파티 참석자 중 누군가의 최종 parent가 진실을 알고 있다면 그 파티에서는 거짓말을 할 수 없다. [코드] pac..
[boj] 백준 12852 1로 만들기 2 (Java) - dp [문제] https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net [풀이] 3으로 나눌 수 있는 경우, 2로 나눌 수 있는 경우, 1을 뺄 수 있는 경우에 대해서 dp[i]는 i를 1로 만들 수 있는 연산의 최솟값을 저장해준다. 정답 출력 시 과정도 함께 출력해야 하기 때문에 trace[i]에 이전 값을 저장해둔다. [코드] package dp; import java.util.*; import java.io.*; public class boj_12852_java { static int n; static int[] dp; static int[] trace; p..
[pro] 프로그래머스 level1 64061 크레인 인형뽑기 (Java) - 스택 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 주어진 board내 인덱스만 조절해서 풀어도 되지만 column별 큐에 담아 쉽게 맨 위에 있는 인형을 뽑을 수 있도록 했다. 바구니는 맨 위에 있는 인형과 비교해서 터뜨리거나 그냥 넣기 때문에 스택을 이용해서 구현한다. [코드] package heap_stack_dequeue; import java.util.*; class Pro_level2_64061 { public int ..
[boj] 백준 1654 랜선 자르기 (Java) - 이분탐색 [문제] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 기본 이분탐색 문제이다. 다만 주의해야 할 점은 랜선의 최대 길이가 2^31-1 이기 때문에 low, mid, high 값을 long으로 선언해주어 오버플로우가 발생하지 않게 해야 한다. [코드] package 이분탐색; import java.util.*; import java.io.*; public class boj_1654_java { //k개의 ..
[boj] 백준 19236 청소년 상어 (Java) - DFS, 시뮬레이션 [문제] https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net [풀이] 상어는 같은 방향으로 최대 *3만큼 이동할 수 있으며 이 모든 이동경로에 따라 상어가 먹을 수 있는 물고기 번호의 합이 달라질 수 있으므로 dfs를 통해 탐색해야 한다. 1. 상어가 이동하여 물고기를 잡아 먹는다. 상어는 잡아먹은 물고기의 방향을 갖게 된다. 2. 물고기를 이동시킨다. 1~16번까지 차례로 이동하며 물고기가 이동 가능하다면 위치를 바꿔준다. 불가..
[boj] 백준 16236 아기 상어 (Java) - BFS, 시뮬레이션 [문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [풀이] BFS를 이용한 시뮬레이션 문제이다. 1. 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 이동한다. 여러 마리라면 가장 가까운 순으로 먹는다. 거리가 같다면 위쪽, 왼쪽 순으로 먹으러 이동한다. bfs를 이용하여 먹을 수 있는 물고기에 대해 탐색을 진행하여 그 좌표와 거리를 저장한다. 2. 탐색이 끝나면 조건에 맞게 먹을 수 있는 물고기 리스트를 정렬한다. 먹을 수..
[boj] 백준 17779 게리맨더링2 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net [풀이] 1. 모든 가능한 r, c, d1, d2 에 대해서 완전 탐색해야 한다. 4중 for문을 돌며 범위를 초과하지 않는 r, c, d1, d2에 대해서 경계선에 의해 만들어지는 사각형의 4가지 꼭짓점을 설정해주도록 한다. 꼭짓점은 (r, c)를 0으로 반시계 방향으로 회전하며 0, 1, 2, 3 번 꼭짓점으로 설정하였다. 2. 경계선을 그려준 후, 각 선거구마다 인구의 합을 구한 후 정렬..
[boj] 백준 17825 주사위 윷놀이 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net [풀이] https://stritegdc.tistory.com/220 [boj] 백준 17825 주사위 윷놀이 (c++) - DFS, 시뮬레이션 [문제] https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net [풀이] 1. 윷놀이 판을 위와 같이 새롭게 세팅해준다. 윷놀이 판에 stritegdc.tistory.com 말 판은 하드코딩했기 때문에 인덱스가 달라짐. [코드] import ja..

티스토리툴바