기록

문제백준 22856번 - 트리 순회유사 중위 순회를 수행하면서 이동한 횟수를 계산하는 문제입니다.유사 중위 순회는 다음 규칙을 따릅니다:현재 노드의 왼쪽 자식 노드가 존재하고 방문하지 않았다면, 왼쪽 자식으로 이동합니다.그렇지 않고 오른쪽 자식 노드가 존재하고 방문하지 않았다면, 오른쪽 자식으로 이동합니다.그렇지 않고 현재 노드가 중위 순회의 마지막 노드라면, 탐색을 종료합니다.그렇지 않다면 부모 노드로 이동합니다.중위 순회를 따르는 방식으로 이동하며, 이동한 횟수를 출력합니다.풀이1) 문제풀이트리를 left와 right 배열로 표현하여, 각 노드의 왼쪽과 오른쪽 자식 정보를 저장합니다.중위 순회의 마지막 노드를 findLastNode 함수로 찾아냅니다.마지막 노드는 오른쪽 자식이 없을 때까지 오른쪽으로..

문제백준 20207 - 달력여러 일정이 주어질 때, 이를 달력에 배치하고 차지하는 직사각형 면적을 구하는 문제입니다. 일정은 시작일과 종료일로 주어지며, 겹치는 일정이 있는 경우 이를 높이로 표현합니다. 이를 통해 달력의 전체 면적(폭 × 높이)을 계산하는 것이 목표입니다.풀이1) 일정 마킹날짜를 기준으로 일정의 시작과 끝을 배열에 기록합니다.시작일에는 +1, 종료일 다음 날에는 -1을 기록하여 일정의 변화를 마킹합니다.이를 통해 특정 날짜에 일정이 시작되고 끝나는 구간을 표시할 수 있습니다.for (int[] pair : eventList) { int start = pair[0]; int end = pair[1]; board[start]++; board[end + 1]--;} 예를..

문제https://www.acmicpc.net/problem/14719이번 글에서는 백준 온라인 저지의 14719번 문제, "빗물" 문제를 다뤄보겠습니다.2차원 세계에 블록이 쌓여있고, 비가 내린 후 고일 수 있는 물의 총량을 계산하는 문제입니다.풀이문제의 핵심 아이디어어떤 칸에 고일 수 있는 물의 양은 다음과 같이 계산할 수 있습니다:해당 칸에서 왼쪽 방향으로 가장 높은 블록과 오른쪽 방향으로 가장 높은 블록 중 더 낮은 값을 찾습니다.그 값에서 현재 칸의 블록 높이를 뺀 값이 고일 수 있는 물의 양입니다.식으로 나타내면:물의 양 = Math.min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 칸의 높이위 계산을 모든 칸에 대해 수행한 후, 이를 모두 더하면 전체 고인 물의 양을 구할 수 있습니다.P..

문제 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 board의 내부의 점 (r, c)가 주어질 때, board[r][c]에 적어야 할 값을 반환하는 함수 f가 있다고 하자. ex) f(-3, -3) = 37 f(0, 1) =2 1) 어느 그룹에 속하는가? 메인그룹 mg = abs(max(r, c, key = abs)) 안쪽에서 바깥쪽 껍데기로 나오면서 0, 1, 2... 그룹으로 묶을 수 있다. 0그룹 : 1 1그룹 : 2~9 2그룹 : 10~25 ... 점A (-2, 3)이 주어졌다고 할때 점 A는 3그룹에 속한다. 서브그룹 # corner일때 if abs(r)==abs(c) : if c>0 and r

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1) DFS def dfs(board, w) : if w>=5 : return max(max(board, key = max)) return max(solve(up(board), w+1), solve(down(board), w+1), solve(right(board), w+1), solve(left(board), w+1)) 2) 블록 오른쪽으로 밀기 각 행을 ..

문제 www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 설계도를 입력 받을 때 테두리를 빈 칸 . 으로 채운다. stack에 다음으로 탐색할 노드의 행과 열을 입력한다. [(r1, c1), (r2, c2)...] 더 이상 탐색할 노드가 없을 때까지(stack이 비어 있을 때까지) 탐색한다. 1) .를 만났을 때 상하좌우의 유효한 노드를 stack에 추가한다. 유효한 노드: 설계도 안에 존재하며 벽(*)이 아닌 노드 중복을 체크하기 위해 해당 노드에 벽(*)을 세운다...

문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 1. 미세먼지의 확산 : 함수 diffusion "확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다."라고 명시하고 있기 때문에, 확산되는 먼지의 양은 '변화가 있기 전의 먼지/5'로 계산하여야 한다. BOARD NEW_BOARD 10 9 10 9 0 0 0 0 [초기값] BOARD NEW_BOARD 10-10/5-10/5 = 6 9+10/5 = 11 10 9 0+10/5 = 2 0 0 0 [(0, 0) 미세먼지 10의 확산] BOARD NEW_BO..