KEEP GOING

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 삼성 코딩테스트 같은 경우, itertools 모듈을 사용할 수 없습니다. 그래서 permutations(순열)이나 combinations(조합) 같은 기능을 사용하지 못하는데, 이를 대비하기 위해 DFS를 이용하여 조합을 구할 수 있는 대표적인 문제입니다. [dfs] def dfs(arr, idx): if len(arr) == M: print(*arr) return for i in range(..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net [투포인터] n = int(input()) lst = sorted(map(int, input().split())) liquid = 4*(10**9) answer = [] for i in range(n-1): start, end = i+1, n-1 while start < end: total = lst[i] + lst[start] + lst[end] if abs(total) <..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net [dfs] 트리의 지름을 구하는 공식을 모르면 풀 수 없는 문제 * 트리의 지름 구하기 : 아무 노드나 하나를 정해서(root) 가장 먼거리에 있는 노드(far_node)를 구하고, 그 노드와 가장 먼 노드의 거리를 구하면 트리의 지름이다. * 귀류법을 사용하면 명제를 증명할 수 있다고 한다. import sys sys.setrecursionlimit(10**5) def dfs..

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 [완전탐색] 외판원 순회2의 경우, 도시의 수가 최대 10개로 완전 탐색으로 풀어도 문제없이 동작한다. 모든 노드가 서로 연결되어있다고 가정했을 때, 시간복잡도는 O(n!)이 된다. n = 10이므로 10! = 3628800으로 시간 초과가 발생하지 않는다. 만약 n이 12이상으로 주어지 경우 연산 횟수는 대략 5억으로 시간초과가 발생한다는 점을 주의하..

문제를 풀기 위해 앞서 알아야 할 지식은 최소 공통 조상을 찾는 LCA에 대한 개념이다. * LCA(Lowest Common Ancestor) 트리 내에서 공통 부모인 LCA를 찾아주는 알고리즘 두 점 사이의 거리를 구할 때 사용한다. ( 두 노드의 공통된 조상 중에서 가장 가까운 조상 찾기 ) 처음 트리 생성 시 각 노드마다 부모 노드와 level을 정리한다. 두 노드에서 올라가면서 부모 노드가 같아질 때까지 찾아간다. * A와 B 두 점 사이의 거리 = 1부터 A까지의 거리 + 1부터 B까지의 거리 - 1부터 LCA까지의 거리*2 예를 들어, 아래와 같이 이진 트리가 주어진 경우 12번 노드와 7번 노드의 거리 = 1부터 12까지의 거리 + 1부터 7까지의 거리 - 1부터 LCA(3)까지의 거리*2 ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net board = [list(input().rstrip()) for _ in range(12)] moves = [(1,0), (0,1), (-1,0), (0,-1)] answer = 0 def dfs(x, y, count, color): global tmp tmp[x][y] = True for dx, dy in moves: nx = dx + x ny = dy + y if 0

[1] 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [BFS + 시물레이션] 이 문제는 deq에서 결국 하나의 좌표만 관리되기 때문에 굳이 BFS로 풀지 않고 좌표로만 접근해도 됐다. 보통 현재 좌표에서 네 가지 방향 모두 사용했는지 체크하는 변수를 두거나 for문으로 4가지 방향을 돌려서 검사하는 방식으로 구현하는데, 나는 전자의 방식을 사용했는데 (네 가지 방향 모두 사용했는지 체크하는 변수 : turn_time) for문..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제의 경우, 벽을 부술 수 있는 기회 한 번이 주어진다. 테스트 케이스로 주어지지 않았지만 0,0 좌표에서 n-1,m-1 좌표까지 갈 때 벽을 부수지 않고 이동하는 최단 경로도 있다. 나는 벽인 좌표들을 walls라는 배열에 넣어 벽을 하나씩 부숴가며 bfs를 돌려주었다. 하지만 한 번도 벽을 부수지 않고 이동하는 경우에 대해서는 검사하지 않았다. 따라서 벽을 부수는..