문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 처음 시도한 풀이(시간 초과) 처음에는 단순히 목표 노드에서 연결된 노드를 거꾸로 접근해 가면 dp배열을 업데이트 시켰다. def d(i: int): if not graph[i]: dp[i] = times[i] return dp[i] dp[i] = max(map(d, graph[i])) + times[i] return dp[i] for _ in range(int(input())):..
문제 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 가장 쉬운 방법은 각각의 원소에 대하여 모든 원소와 매칭 하는 것이겠지만, 원소의 개수가 최대 1,000,000개 이므로 O(N^2)의 시간 복잡도로는 시간 초과가 날것이다. 따라서 모든 원소를 딕셔너리의 key로 만들어주고 각 원소에 대해서 문자열의 앞부분을 슬라이싱하여 딕셔너리의 key에 존재하는지 확인하였다. 딕셔너리에서 key가 존재하는 찾..
문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 모든 좌표에 대해서 방문하지 않은 곳이면 깊이 우선 탐색을 진행한다. 다만, 적록색약과 아닌 시각을 구분해야 하기 때문에 visited 배열을 두 개 만들어 주었다. 또한 dfs함수에 color_type을 매개변수로 넘겨주어서 코드의 중복을 줄일 수 있었다. 코드 import sys sys.setrecursionlimit(10**9) N = int(input()) graph = ..
문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 후위 순위의 마지막 값을 출력하고 그 값을 기준으로 전위 순위를 왼쪽과 오른쪽으로 나누어 각각 재귀 함수를 실행시켰다. 처음에는 함수에 슬라이싱을 통해 새로운 리스트를 넘겨주었는데, 메모리 초과가 났다. 첫 번째 실패 코드 def find_pre_order(in_order: list, post_order: list): if not in_order: return print(post_order[-1], end=" "..
백준 4256번 파이썬
문제 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 1. 전위 순위의 첫 번째 원소를 기준으로 중위 순위를 나눈다. 2. 전위 순위의 첫 번째 원소를 제거한다. 3. 중위 순위의 원소가 없을 때까지 1과 2의 과정을 반복한다 예를 들어 전위 순위 : 3 6 5 4 8 7 1 2 / 중위 순위 : 5 6 8 4 3 1 2 7 라고 한다면, 트리는 다음 과정으로 만들어진다. 매번 확정된 숫자(매번 전위 순위의 첫 번째 원소)를 동..
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 전형적인 시뮬레이션 문제이다. 제시된 조건을 하나하나 구현해나가면 해결할 수 있다. 지나간 자리의 몸통은 deque에 넣어주었고 사과가 없으면 popleft()를 통해 꺼내 주었다. 뱀의 머리가 벽에 닿았거나 뱀의 몸통에 닿을 때(deque에 현재 좌표가 이미 존재할 때) 종료 조건을 설정했다. 처음에 방향 전환 조건을 매 초가 시작될 때로 설정해 주어서 틀렸는데, 문제를 자세히 보니 매 초가..