https://www.acmicpc.net/problem/21606 모든 검은색 노드는 흰색 노드를 통과할 수 있고, 검은색 노드는 통과하지 못할 때,모든 이동 가능한 검은색 노드 사이 경로의 개수를 세는 문제이다. 이 문제는 그래프를 단순화시킨 뒤 순열과 트리의 특성을 이용해 개수를 세면 문제를 풀 수 있다. 그림과 같이 노드가 구성되어 있다고 해보자.우리가 구하려고 하는 것은 두 검은색 노드 사이의 경로가 존재하는지 파악하는 것이다.이 정보를 파악하는데 중요한 것은, 여러개의 인접한 흰색 노드는 우리가 구하려는 것을 찾는 과정에서 전혀 의미가 없다는 것이다.그러면 이 그래프를 다음과 같이 단순화할 수 있다. 흰색 노드의 번호는 더 이상 정답을 구하는데 있어 큰 의미가 없다. (코드로 구현할 때는 번..
https://www.acmicpc.net/problem/2618 질문게시판에서 힌트 하나를 얻고 푼 문제..처음에는 스티커 문제처럼 어떤 사건을 경찰차 1이 해결한 경우, 경찰차 2가 해결한 경우로 나누어서 테이블을 구성하고,dp[w][1] = 사건 w를 경찰차 1이 해결했을 때, 그때까지 두 경찰차의 최소 이동거리 합 =min( dp[w-1][1] + dist(w-1, w) , dp[w-1][2] + dist(w-1을 경찰차 2가 해결한 최적해에서의 경찰차 1의 위치, w) ) 로 두고 dp[w][1], dp[w][2] 로 이루어진 2차원 배열로 풀려고 했다. 이렇게 말로만 적어도 벌써부터 점화식이 복잡한데, 이 점화식은 안타깝게도 틀렸다.비교하고 있는 두 값이 '같은' 경우 어떤 값을 취할 지 정할..
https://www.acmicpc.net/problem/1450 문제 풀이 주어진 물건들을 가방 안에 담을 수 있는 모든 경우의 수를 출력하는 문제나이브하게 접근하면 물건이 최대 30개 있으므로, 2^30 조합을 모두 시도해보면 된다.하지만 이렇게 접근하면 최악의 경우 1,073,741,824 가지의 경우의 수가 나오기 때문에 시간초과가 발생한다.따라서 meet in the middle 테크닉을 이용하여 시간을 줄이는 것이 이 문제의 핵심이다. '중간에서 만나기' 라는 이름으로도 불리는 이 테크닉은, 사이즈가 큰 전체 대상을 처음부터 끝까지 직접 탐색하는 것보다,전체 영역을 반으로 나눈 뒤, 반씩 쪼개서 탐색한 결과를 조합하여 해답을 구하는 기법이다. 이 문제의 경우, 2^30의 조합을 모두 구하는 것..
https://www.acmicpc.net/problem/2179 가장 긴 prefix를 구하는 건 쉬운데, 입력된 순서상 앞선 조합을 골라내는 것이 까다로운 문제가장 긴 prefix를 구할 때는 단어를 정렬해서 한번 순회하면 O(n log n) 시간에 구할 수 있다. 이때 같은 길이의 prefix에 대해서 입력이 먼저된 단어를 출력해야 한다.그래서 단어를 저장할 때, 입력된 순번도 같이 저장했다. n = int(input())l = []for i in range(n): s = input().rstrip() l.append((s, i)) 단어를 정렬하고 순회하면서 prefix를 체크할 때는 별도 함수를 사용했다.이때 같은 prefix 를 갖는 단어들을 모두 저장하기위해 딕셔너리와 셋을 이용했다..
https://www.acmicpc.net/problem/30804 탕후루 꼬치에서 앞 뒤로 몇개의 과일을 빼 2가지 종류 이내로 구성된 가장 긴 길이의 탕후루 꼬치를 만드는 문제다.처음에는 단순 구현을 해야하나 싶어서 한참 고민했는데, 앞 뒤로 과일을 뺀다는 것은 남은 과일이 연속적이라는 점에서 힌트를 얻어 투 포인터를 생각해낼 수 있었다. 앞에서부터 과일을 하나씩 살펴보면서 2가지 종류가 되지 않았다면 연속된 길이에 포함하고, 2가지가 넘는 종류가 나오는 순간 그때까지 담은 길이를 정답 후보로 체크한다.그리고 그 이전에 담았던 과일 중, 제일 마지막에 나왔던 종류가 아닌 과일을 2가지 종류에서 제외하고, 새로 나온 종류를 2가지 종류에 추가한 뒤 위 과정을 반복한다. n = int(input())fr..
https://www.acmicpc.net/problem/17472구현 + MST 섬의 위치가 격자판 모양으로 주어질 때, 격자판 모양으로부터 그래프를 직접 정의하고, 그 그래프에 대해 MST를 찾으면 됩니다.이런 복잡한 문제는 어떤 것들을 구현해야 하는지 잘 나눠서 생각하면 구현하기 좋습니다.(그래도 이 문제는 구현이 엄청 복잡한 편까지는 아닙니다.) 먼저 섬부터 찾아보겠습니다.섬을 찾는다는 것은 격자판을 그대로 그래프로 보았을 때, 컴포넌트를 찾는 것과 같습니다.# 섬 찾기island_number = 2island_tiles = []for i in range(N): for j in range(M): if board[i][j] == 1: # BFS ..
https://www.acmicpc.net/problem/1661 문제 분류를 봐도 아이디어를 떠올리기 힘들었던 문제분류를 보기 전까지는 자연스럽게 그리디가 계속 떠올랐다. 우선 N이 작기때문에 뭔가 다 해보면 될 것 같다는 생각은 든다.그런데 어떻게 다 해봐야할 지 감이 잘 안온다.이 문제를 풀 때는 한번 예제 입력 1번에 해당하는 케이스를 다 써보면 풀이를 떠올릴 수 있다. 예제 입력에 1번에 있는 물건 3개에 대해서 각각을 사는지 안사는지 경우의 수를 모두 따지면 이렇게 8가지가 나온다.이를 직접 손으로 다 쓰다보면 규칙이 보인다. 어쨌든 할인율은 결국 1, 2, 3 프로중 하나밖에 없다.그리고 최종 할인되는 가격은 어떤 물건을 먼저 사느냐에 상관없이 항상 기존 가격 * 각각의 할인율들의 곱으로 표..
요구사항에 맞게 구현하면 되는 문제오랜만에 풀어서 그런지 꽤 어려웠다.. 윷놀이 문제처럼 말을 이동하다가 다른 말을 만나면 쌓아야 하는데, 말을 쌓더라도 자신이 갖고있는 방향은 바뀌면 안된다. class Unit: def __init__(self, number, row, col, direction): self.number = number self.row = row self.col = col self.direction = direction def check_next(self): if self.direction == RIGHT: return self.row, self.col + 1 if self.dire..
https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net BFS 를 활용하는 시뮬레이션 문제이다. 구현할 때 모든 조건을 꼼꼼히 살펴야하고, 작은 사소한 실수 하나로도 문제를 틀리기 때문에 난이도가 높다. N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] score = 0 while True: x, y, size = find_block..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 간단한 시뮬레이션 문제이다. 나는 생각을 어렵게 해서 쌩 배열로 구현해서 그런지 구현이 빡셌지만.. 난이도 매기는 사람들 의견보니 구현은 쉬운편이라고.. 그냥 덱 자료구조로 하면 더 쉽게 할 수 있을 것 같다. Python 리스트 (배열) 사용 풀이 배열과 리스트는 다르지만 사실상 리스트를 배열처럼 활용하여 풀었다. 나는 2N 개의 배열을 미리 잡아두고 '올리는 위치(put_..
