본문 바로가기

전체 글

 (276)
정수 삼각형 유형 분석 이 문제 또한 전에 풀었던 금광문제처럼 사고의 전환이 필요하다. 1열에서 2열로 더한다 라기 보단 2열을 기준으로 1열에서 최선의 선택을 해 더한다로 생각하는게 낫다. 다만, 헷갈렸던 점은 대각선을 더해야하는데, 2차원 배열로 나타내면 대각선 표현이 어렵다는 점이다. 그걸 주의해서 잘 풀어야 하는것 같다. 코드 n = int(input()) m = int(input()) graph = [] graph.append([m]) for i in range(1, n): graph.append(list(map(int, input().split()))) dy = [-1, 0] for x in range(1, n): for y in range(len(graph[x])): max_value = 0 for i ..
금광 문제 금광은 N,M 행열로 구성되어 있다. 첫번째 열부터 시작해 마지막 열까지 이동하는데, 방문한 행에 있는 금을 캘 수 있다. 오른쪽 위, 아래, 옆 중 하나를 선택해 이동가능하다. 최대한 많이 캔경우 금의 양은? 유형 파악 및 구현 금광 (x, y)는 (x-1, y-1) or (x, y-1), (x+1, y-1) 중 하나와 더해 가장 크게 만들어야 한다. 첫번째 열부터 시작하니 이동 경로마다 값을 구하기 보단 생각을 역전해서 두번째 열에 있는 금들은 첫번째 열의 어떤 금들과 더해져야 가장 커지는가?에 대해서 생각하면 좋다. 1행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? 2행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? ... 1행 4열은 3열의 금들 중 어떤 금이랑..
효율적인 화폐 구성 문제 주어진 코인을 이용해 문제에서 주어진 돈을 만들어라 유형 파악 및 구현 전형적인 DP문제인것 같다. 예를 들어 [2, 3]원을 활용해 5원을 만든다고 가정하자. 1원 만들 수 있는가? X 2원 만들 수 있는가? O -> 2%2 == 0 3원 만들 수 있는가? O -> 3%3 == 0 4원 만들 수 있는가? O -> 4%2 == 0 5원 만들 수 있는가? O -> 5%2 ==0 ? X -> 5%3 ==0 ? X -> (5-2)원은 만들 수 있는가? == 0? O -> 3원을 만드는 경우의 수 + 1 즉, 5원을 만들때, 2원이나 3원만으로는 만들 수 없다. 하지만 5-2 or 5-3원을 만들 수 있는지 체크 한 후 만들 수 있다면 그 값에 1을 더하면 된다. 코드 n = 3 result = 10 co..
바닥공사 문제 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..

티스토리툴바