본문 바로가기

Algorithm

 (140)
바닥공사 문제 3가지 종류의 타일을 사용해 가로 N 세로 2인 바닥을 채울 때, 채울 수 있는 경우의 수를 구하라 유형파악 및 구현 타일의 종류는 2x1, 1x2, 2x2가 있다. N이 1일 때, 경우의 수는 한가지 경우이다. 1x2 N이 2일 때, 경우의 수는 세가지 이다 (1x2, 1x2), (2x1, 2x1), (2x2) N이 3일 때, - (1x2, 2x1, 2x1), (1x2, 2x2) : N(1) + (2x1, 2x1) or (2x2) - (1x2, 1x2, 2x1), (2x1, 2x1, 1x1), (2x2, 1x2) : N(2) + (1x2) 점화식을 만들어보면, check[n] = check[n-1] + 2*check[n-2] 이다. 코드 n = 10000 check = [0]*(n+1) check..
개미전사 문제 식량창고가 있을 때 최소한 한칸이상 차이가 나야 약탈을 연속으로 가능하다. 유형 파악 및 구현 내가 나름 정한 규칙이 있다. 전의 값이 지금 구하고자하는 값에 영향을 주는 가? DP 2차원 그래프에서 특정조건에 맞춰 연결된 집합을 구하거나 거리를 구하는가? DFS/BFS 완전탐색이나 시뮬레이션 문제 유형인가? Implementation 아무 생각이 안나는가? Greedy 뭐 이 중에서 알고리즘이 섞여서 나오기도 하지만 기본적으로는 저런 조건이 있다면 해당 알고리즘을 생각해내는게 중요하다. 이 문제는 전에 구한값이 지금 구하는 값에 영향을 미친다. 식량 창고가 다음과 같다고 가정하자 [2, 1, 9, 10, 11, 8] 첫번째 인덱스까지만 존재한다고 가정하고 턴다면 최대값은 2이다. check[1] ..
1로 만들기 문제 X가 주어질 때, 5, 3, 2로 나누거나 1을 빼서 결과적으로 1을 만들 때, 가장 최소의 연산의 수로 1을 만들어라 유형 파악 및 구현 전형적인 DP문제이다. 예전에 구한 값이 지금 현재 구하고자 하는 값에 영향을 준다 예를 들어, 26을 1로 만든다고 생각을 해보자 - 26은 5나 3으로는 나누어지지 않는다. - 26은 2로 나누거나 1을 뺄 수 있다. 이 때, 2로 나누는 경우 - 13에서 1을 만들기 위한 최소한의 연산의 수 + 1 1을 빼는 경우 - 25에서 1을 만들기 위한 최소한의 연산의 수 + 1 즉, 13 또는 25를 1로 만들기 위해 사용되는 연산의 수 + 1을 하고 둘 중 작은 값이 정답이 된다. x 를 1로 만드는 횟수 1 : 0 2 : min(2//2를 1로 만드는 횟수+1..
Dynamic Programming - Concept 해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. 다이나믹 프로그래밍(DP) - 메모리 공간을 더 사용해 연산속도를 늘리는 방법 - 탑다운, 보텀업 - 메모이제이션(캐싱) 다이나믹 프로그래밍을 사용할 수 있는 조건 - 큰 문제를 작은 문제로 나눌 수 있다. - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. "예전에 구한 값이 지금 구하는 연산에 영향을 주는 경우에 이를 기록해놓는 메모이제이션을 통해 DP를 구현한다." 탑다운 - 큰 문제를 해결하기 위해 작은 문제를 호출한다. - 메모이제이션 - 재귀함수를 이용해 구현 보텀업 - 작은 문제에서부터 차근차근 답을 도출한다. - DP 테이블 - 반복문을 이용해 구현 유형 정리 - 예전에 구한 값들이 지금 계산할 값에 ..
괄호변환 이 문제는 DFS나 BFS를 사용하기 보단 구현, 재귀함수와 가까운 듯 하다. 코드내에 간단한 조건들과 구현을 정리해보았다. 코드 # 올바른 문자열인지 확인해주는 함수 def test1(array): count = 0 for i in array: if i == "(": count += 1 else: count -= 1 if count < 0: return False return True # 메인 함수 def solution(array): # 길이가 0이면 그대로 반환 if len(array) == 0: return "" # 해당 문자열이 균형잡혔는지 확인 count1,count2 = 0, 0 for i in range(len(array)): if array[i] == "(": count1 += 1 els..
경쟁적 전염 문제 1부터 K까지 번호가 있는 바이러스가 K 있을 때, N크기의 맵에서 바이러스가 증식한다. 유형 - 일종의 퍼진다 개념이다. - 노드와 간선의 개념이다. - 그래프에서 연결된 노드 집합 구하는 것과 유사하다. 구현 - 입력을 받을때, 바이러스 초기시간(0초), 위치, 값을 처리한다. - 이 후, 값을 작은 순서대로 정렬한다. -> 번호가 작은 순서대로 증식하기 때문에 - 큐에 넣는다. - 선입부터 쭉쭉 꺼낸다. - 만약 꺼낸 데이터의 시간이 기준 시간보다 같다면 멈춘다. - 꺼낸 데이터를 상하좌우 따져서 범위 안인지 확인한다. - 범위 안이면 숫자로 방문처리, 큐에 삽입, (삽입시 현재 시간 + 1 해야한다.) 코드 from collections import deque n, k = map(int, i..
연구소 문제 0 - 빈칸, 1 - 벽, 2 - 바이러스일 때, 바이러스는 상하좌우로 0이 있으면 그 길을 통해 퍼진다. 이 때 벽을 3개 세워 바이러스를 막을 때, 바이러스가 아닌 부분의 최대 개수 (안전영역) 유형 분석 - 그래프와 연결된 모든 노드를 구해서 바이러스가 퍼지는 유형 -> DFS 벽을 세우는 경우의 수 : combinations 바이러스 처리 : DFS or BFS 코드 # 연구소 from itertools import combinations dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] def virus(x, y, test): for k in range(4): now_x = x + dx[k] now_y = y + dy[k] if now_x = n ..
특정 거리의 도시 찾기 문제 노드의 수(N), 간선의 수 (M), 출발 도시의 번호(X) 가 주어질 때, 노드 X로 부터 거리가 K인 노드 번호를 모두 구하라. 유형 분석 및 해결 - 노드와 간선 그래프이다. - 거리가 모두 1이다. - 특정노드와 거리가 k인 노드 -> BFS 코드 from collections import deque def solution(n, k, x, array): distance = [-1]*(n+1) distance[x] = 0 queue = deque() queue.append(x) while queue: now= queue.popleft() for i in array[now]: if distance[i] == -1: distance[i] = distance[now] + 1 queue.append(..

티스토리툴바