코테 탈출일지

https://www.acmicpc.net/problem/1213

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방식 - 트리 구조의 그래프에서 부모 노드를 확인하는 방법 고민 - bfs/dfs 탐색 방식 선택 코드 풀이 import sys input = sys.stdin.readline from collections import deque n = int(input()) graph = list([] for _ in range(n)) # 그래프의 연결 관계 저장할 리스트 parent = [0]*n # 각각의 노드의 parent를 조사해 저장할 리스트 visited =..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 접근 방식 - Bottom up (A to B), Top down (B to A) 방식 고민 - 두 가지 종류의 연산의 반복 구현과 현 상황의 최적해 고민 코드 풀이 a, b = map(int, input().split()) cnt = 1 # 최소값에 1을 더한 값 출력하라고 했음 while b != a: if b % 10 == 1: # 맨 뒷자리 1이라면 일단 1 떼주는 연산 b = int(b/10) cnt += 1 elif b % 2 == 0 and b!=0: # elif로 처리해야 시간초과 방지, b = 0 무한루프..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 접근 방식 - 주어진 사탕 정보 배열에서 연속인 최대 사탕수를 세는 방법 고민 - 사탕의 색이 다른 인접한 두 칸을 서로 교환하는 방법 고민 코드 풀이 n = int(input()) # 보드의 크기 candy = [list(input()) for _ in range(n)] # 사탕 색깔 정보 di = [1, 0] # 우하향 방향으로 탐색, 인접 사탕을 바꾸는 데 필요 dj = [0, 1] answer=0 cnta, cntb = 1, 1 # 가로, 세로의 연속 사탕 개수 count def check(graph, n)..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 방식 - 재귀를 통해 아직 방문하지 않았으며, 방문할 수 있는 도시를 순차적으로 방문하는 dfs 구현 - 이때 최소비용을 더하는 방법, 방문처리 해주는 방법 고민 - 시작점이 어느 도시인지가 유효한지 고민 코드 풀이 n = int(input()) # 도시의 수 cost = [list(map(int, input().split())) for _ in ..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 접근 방식 - 하나의 질문/대답 정보를 통해 유추할 수 있는 숫자들의 풀을 차례로 조사하여 교집합 처리해주는 방식 - or 가능한 전체 경우의 수에서 하나의 질문/대답 정보를 통해 불가능한 숫자를 차례로 제외해주는 방식 코드 풀이 위의 접근방식 중 첫 번째 방식은 하나의 질문/대답에서 고려해야 하는 순열, 조합의 경우의 수가 너무 복잡하여 두 번째 방식을 활용하였습니다. 두 번째 방식은 차례대로 ..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근 방식 - 주어진 숫자들의 모든 배열 경우의 수 탐색 방법 (개별 숫자 단위, 전체 배열 단위 등) 코드 풀이 from itertools import permutations n = int(input()) nums = list(map(int, input().split())) ans = [] for nums_per in permutations(nums): sums = 0 for i in range(n-1): #..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 접근 방식 - 수열의 부분합을 처리할 수 있는 효율적인 탐색 방법 고안 - 복잡도를 낮출 수 있는 방법 고민 코드 풀이 n, m = map(int, input().split()) nums = list(map(int, input().split())) cnt = 0 start, end = 0, 0 # nums[start:end] 방식으로 접근 (투 포인터 알고..