CODING119 [BAEKJOON] 1920번 수 찾기 주어진 A 배열과 입력되는 수간의 비교 연산으로 포함 여부를 판단하는 문제이다. 물론, 반복문으로 배열 전체와 입력되는 수를 하나씩 비교하며 포함되는지 여부를 알 수 있다. 하지만 반복문을 사용할 경우 메모리 초과를 경험할 수 있을 것이다. 결론부터 말하자면 A 배열을 오름차순 정렬하여 이진 탐색 방법으로 타켓 수와의 비교 연산을 줄여 효율을 높인다. 위의 그림과 같이 시작과 끝 인덱스를 기준으로 mid에 해당하는 중간 지점 인덱스를 구한다. '시작~중간' 과 '중간~끝' 중에 target이 되는 수가 어디 지점에 있는지만 알면 된다. target이 배열의 중간을 기준으로 오른쪽과 왼쪽 부분으로 나누었을 때 어느 지점에 있는지 찾아가는 과정을 반복하면 결국 중간지점은 언제나 마지막 하나가 남을 때까지 반.. 2022. 3. 30. [BAEKJOON] 2775번 부녀회장이 될테야 아래 표를 보면 규칙이 보이면 문제 해결 끝이다. 0층의 경우 i호에 i명이 산다고 했으니 1호에 1명, 2호에 2명 , ... , 가장 끝 방(∵ n≤14)인 14호에 14명이 거주 중일 것이다. 0층의 바로 윗 층인 1층을 보자. 1층의 1호는 0층의 1호부터 1호까지 합 즉, 1명 거주 1층의 2호는 0층의 1호부터 2호까지 합 즉, 3명 거주 1층의 3호는 0층의 1호부터 3호까지 합 즉, 6명 거주 중이다. 규칙이 보이지 않는가? 모든 층의 1호는 모두 1명이 거주할 것이고, arr[1층][2호] = arr[0층][2호] + arr[1층][1호] arr[1층][3호] = arr[0층][3호] + arr[1층][2호], ... 아래와 같은 규칙이 나타난다. arr[층][호수] = arr[층-1][.. 2022. 3. 28. [BAEKJOON] 1018번 체스판 다시 칠하기 아래 그림들은 위의 입력 예제에서 N : 10, M : 13일 때의 경우이다. 문제를 풀어보기 전에 완벽한 체스판의 8*8 윈도우가 있다고 가정하자. 물론 맨 왼쪽 시작이 B인지 W인지 두 가지 모두 고려해야 한다. 이 아래 하늘색의 윈도우를 한 칸씩 이동하며 주어진 체스판의 범위를 넘어가지 않는 한 탐색할 수 있도록 조정한다. 만약 주어진 체스판과 윈도우와 일치하지 않는 칸이 많다면 최소 개수를 만족하지 못 하므로 윈도우를 다음 칸으로 옮겨 탐색을 시작한다. 윈도우를 이동할 수 있는만큼 이동할 때까지 반복하며 주어진 체스판과 윈도우의 일치하지 않는 칸의 최소 개수를 구하면 된다. ※ 여기서 고려해야 할 점! 위에서 언급했듯이 윈도우의 맨 왼쪽 윗 칸이 B로 시작할 때와 W로 시작할 때 두 경우를 모두 .. 2022. 3. 25. [BAEKJOON] 1914번 하노이탑 ※ 3개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정 ※ N개의 원판을 A(초기)에서 C(목적) 기둥으로 옮기는 과정 가장 큰 원판 위에 쌓여있는 N-1개의 원판들을 하나의 덩어리로 가정하고 생각해보자. 먼저 덩어리 N-1개의 원판을 B(임시)기둥으로 옮겨놓은 상태에서 가장 큰 원판을 C(목적)기둥으로 이동시키자. 이후, B(임시) 기둥에 있는 N-1개의 덩어리들을 C(목적) 기둥으로 옮기기만 하면 끝이다. 더 세세하게 과정을 나누어서 바로 위의 세 번째 그림을 보자. 위와 같이 가장 큰 원판(빨강색)을 C(목적) 기둥으로 옮겼다면 현실적으로 덩어리를 한 번에 C(목적) 기둥으로 옮길 수는 없다. 따라서 그 다음으로 큰 원판(주황색) 역시 C(목적) 기둥으로 옮기는 과정이 필수이다. 그 전에 .. 2022. 3. 24. [BAEKJOON] 7562번 나이트의 이동 8가지 방향으로 탐색하며 방문하지 않은 경우 큐에 저장한다. 그 다음 큐에서 꺼낸 현재 위치에 지금까지의 누적 거리에 1을 더해 저장한다. 방문하지 않은 위치는 0으로 초기화된 상태 그대로일 것이고, 방문했다면 누적 거리를 저장하기 때문에 0인지 아닌지로 방문 여부를 구분한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int I, arr[][], cnt, end_x, end_y; .. 2022. 3. 23. [BAEKJOON] 7569번 토마토 이전에 토마토 문제를 다룬적이 있는데 아래 글 먼저 보고 오시면 좋을 것 같습니다. 오늘 문제는 이전 문제보다 조금 더 심화된 문제입니다. 2022.03.05 - [CODING/BAEKJOON] - [BEAKJOON] 7576번 토마토 [BEAKJOON] 7576번 토마토 1(익은 토마토)인 위치에서 하루가 지날 때마다 맞닿은 부분(0)이 1로 변경된다. 내 주변 탐색 후 변경하는 과정을 반복해야 한다. 너비우선탐색 문제 유형으로 큐에 삽입하여 과정을 하나씩 따라 snowwhite1106.tistory.com 0은 익혀야 할 토마토, 1은 익은 토마토, -1은 토마토가 없어서 방문하지 않아도 된다. 이번 문제는 토마토 상자가 n단으로 쌓아올려져 있고, 내 주변 상하좌우 방향 뿐만 아니라 현재 위치에서 쌓.. 2022. 3. 23. 이전 1 ··· 9 10 11 12 13 14 15 ··· 20 다음
