나를 위한 기록

https://www.acmicpc.net/problem/3584 문제 접근 처음에는 DFS를 통해 자식 노드를 모두 찾으면 해당 노드 번호를 반환하도록 구현했다. 따라서 부모 노드의 자식을 저장하도록 트리를 만들었다. 하지만 결과는... 사실 노드의 갯수가 최대 10000개이기 때문에 메모리 초과가 나올 줄 몰랐다... 고민 끝에 최근 풀었던 Union-Find 문제를 풀었던 기억을 되살려 트리를 만들 때 부모의 자식을 저장하는 것이 아니라 자식의 부모를 저장하도록 하여 문제를 해결하였다. DFS를 이용할 때는 탐색하지 않아도 될 노드를 탐색했는데 트리를 저장하는 방식을 바꾸니까 찾고자 하는 자식의 노드만 탐색하므로 시간 복잡도도 O(logN)으로 해결할 수 있었다. 풀이 과정 문제 풀이 과정을 그림으..

https://www.acmicpc.net/problem/14725 문제 접근 트리를 생성하면 풀 수 있는 문제이다. 트리를 만들 때 딕셔너리나 리스트를 이용해서 만들 수 있는데 이 문제는 노드의 값이 정수형이 아닌 문자열이므로 Dictionary를 이용하여 트리를 생성하도록 한다. 풀이 과정 1. 트리를 생성한다. 주어진 입력에서 depth별 노드의 정보를 받을 수 있다. 재귀를 통해 입력받은 리스트를 하나씩 트리에 추가한다. def add_tree(tree, nodes): if not nodes: return if nodes[0] not in tree: tree[nodes[0]] = {} add_tree(tree[nodes[0]], nodes[1:]) 2. 트리를 출력한다. 트리를 출력할 때 DFS를..

https://www.acmicpc.net/problem/16954 문제 접근 BFS를 이용하여 시작점부터 도착점까지 이동할 수 있는지 판별하는 문제이다. 일반적인 BFS 문제와 다른점은 4방향 탐색이 아닌 현재위치를 포함하여 9방향 탐색을 하는 것이고 탐색을 하는 중간에 배열의 상태가 바뀐다는 것이다. 풀이 과정 9방향 BFS를 구현해주면 된다. 일반적으로 BFS를 구현하면 아래처럼 구현할 것이다. def bfs(x, y): while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if ( nx = 8 or ny = 8 or chess[nx][ny] == "#" or visited[n..

https://www.acmicpc.net/problem/3108 문제 접근 이 문제를 풀기 위한 아이디어는 사각형끼리 교점이 있으면 같은 그룹으로 묶을 수 있고 같은 그룹이면 연필을 올리는 연산인 PU를 하지 않고도 한번에 그릴 수 있다는 것이었다. 또 시작 위치는 원점이고 방향은 위쪽을 보고 있으므로 사각형 그룹이 원점에서 바로 그릴 수 있으면 PU 명령을 할 필요가 없으나 그렇지 않은 경우는 반드시 PU 명령을 해야한다. 하지만 사각형을 그룹핑하기 위한 방법이 떠오르지 않아 풀이를 참조하여 Union-Find(합집합 찾기)를 이용하면 된다는 것을 알았다. 즉 Union-Find를 통해 사각형을 그룹핑하고 그룹의 갯수를 구하면 PU 명령을 실행해야할 횟수를 알 수 있다. 풀이 과정 이 문제의 풀이 코..

https://www.acmicpc.net/problem/11066 문제 접근 DP 문제이다. i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면서 문제를 해결했다. 풀이 과정 앞서 말한 것처럼 i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면 된다. 예를 들어, 0~2까지의 파일을 합치는 데 드는 최소 비용은 [0, 1~2]와 [0~1, 2] 중 작은 값이 될 것이다. 0~3까지의 파일을 합치는 경우는 [0, 1~3], [0~1, 2~3], [0~2, 3] 중 작은 값이다. 이렇게 최소 비용이 드는 임시 파일의 케이스를 찾고 실제 파일을 합치는데 드는 비용을 더해주면 파일을 합칠 때 드는 최소 비용을 구할 수 있다. 1. 임시 파일의 크기 조합을 구한다 for j in r..

문제 설명 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다. 제한사항 n은 10,000,000,000이하인 자연수입니다. 입출력 예시 n return 12345 [5,4,3,2,1] 나의 풀이 리스트의 역순을 구할 때는 인덱스 슬라이싱을 이용하면 좀 더 pythonic한 코드를 작성할 수 있다. def solution(n): return list(map(int, str(n)))[::-1]

https://www.acmicpc.net/problem/1981 문제 접근 풀이 방법이 떠오르지 않아 문제의 알고리즘 힌트와 질문 검색을 통해 문제를 해결하였다. 이 문제는 이분탐색 + BFS로 해결할 수 있다. 최댓값과 최솟값의 차이를 이분탐색을 통해 찾고 BFS를 통해 그 값이 가능한지 탐색하면 된다. 풀이 과정 이분 탐색을 통해 가능한 값을 찾는 것이 핵심! while left end: continue if bfs(start, end): return True return False 마지막으로 BFS를 통해 (0, 0)에서 (n-1, n-1)까지 도달할 수 있는지 검사하면 된다. def bfs(start, end): dx = [-1, 0, 0, 1] dy = [0, -1, 1, 0] visited ..

https://www.acmicpc.net/problem/4991 문제 접근 이 문제는 BFS + 순열을 이용한 문제였다. 더러운 칸의 갯수가 10개를 넘지 않기 때문에 최대 10! 만큼만 연산하면 되었기 때문이다. 그래서 탐색할 더러운 칸의 순서를 permutations 연산을 통해 순열을 구하고 BFS를 통해 하나씩 탐색하면서 지나치는 칸의 갯수를 세어주었다. 하지만 BFS를 통해 매번 칸의 갯수를 연산하는 방식은 시간초과를 해결할 수 없었고, 메모이제이션(Memoization)을 통해 각 더러운 칸 사이를 탐색할 때 지나치는 칸의 갯수를 저장하여 매번 연산하지 않도록 수정했다. 오답 코드 import sys from itertools import permutations from collections..

https://www.acmicpc.net/problem/7579 문제 접근 최근에 풀었던 평범한 배낭과 똑같은 문제이다. 평범한 배낭에서 N개의 물품을 합해서 K만큼의 무게를 확보했던 것과 매칭하면 이 문제에서는 N개의 앱을 합해서 M만큼의 메모리를 확보해야 하는 것이다. 단, 이 문제에서는 앱을 비활성화했을 경우의 비용을 최소화하도록 해야 한다. 그렇다면 앱들을 비활성화했을 경우의 비용별 최대 메모리 바이트 수를 dp 배열에 저장하여 문제를 풀도록 하면 된다. 풀이 과정 dp 점화식은 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])이다. 테스트 케이스를 기준으로 모든 앱들을 비활성화할 경우 총 비용은 15이다. dp[N][Cost] ..

https://www.acmicpc.net/problem/2933 문제 접근 시뮬레이션 + BFS로 구현하는 문제이다. 전체적으로 문제풀이 과정은 문제에서 제시하는대로 따라서 구현하면 된다. 문제의 핵심 로직은 미네랄 클러스터가 막대기를 던질 때 미네랄이 파괴되면서 클러스터가 분리되는지 확인하는 것이다. 미네랄 클러스터는 동서남북으로 인접한 경우만 클러스터로 인정되므로 가장 밑줄의 미네랄들을 BFS나 DFS로 인접한 4방향을 탐색하고 탐색이 종료된 후에 아직 탐색되지 않은 미네랄이 존재하는 경우는 막대기에 의해 분리된 클러스터로 간주하면 된다. 풀이 과정 문제 풀이 과정은 미네랄 파괴 -> 클러스터 체크 -> 분리된 클러스터 낙하를 구현하면 된다. 1. 미네랄 파괴 for i, height in enum..