ALGORITHM (31) 썸네일형 리스트형 [알고리즘] Binary Search Binary Search 이진 탐색 알고리즘을 말 그대로 탐색 알고리즘이다. 하지만 단순하게 처음부터 마지막까지 순서대로 비교하면서 탐색하는 방법이 아닌, 탐색 범위를 좁혀가며 데이터를 찾아내는 방식이다. 이진 탐색 알고리즘을 적용하기 위한 조건으로 배열 혹은 리스트에 있는 데이터들은 정렬이 되어있어야 한다. 그리고 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하면서 원하는 데이터를 찾게 된다. 이진 탐색 알고리즘은 재귀호출을 이용하여 구현할 수도 있고, 반복문을 이용해서 구현할 수도 있다. Example Code def binary_search(source, target, start, end): if start > end: return None mid = (start + end) // 2 .. [문제풀이] 백준 1932번 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제풀이 n = int(input()) t = [] for i in range(n): t.append(list(map(int, input().split()))) k = 2 for i in range(1, n): for j in range(k): if j == 0: t[i][j] = t[i][j] + t[i-1][j] elif i == j: t[i][j] = t[i][j] + t[i-1][j-1] else: t[i][j] = max(t[i-1][j-1], t[i - 1][j]) + t[i][j] k += 1 print(max(t[n-1.. [문제풀이] 백준 2579번 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제풀이 N = int(input()) score = [0] * 300 dp_table = [0] * 300 for i in range(N): score[i] = int(input()) dp_table[0] = score[0] dp_table[1] = max(score[0] + score[1], score[1]) dp_table[2] = max(score[0] + score[2], score[1] + score[2]) for i in range(3, N): dp_table[.. [문제풀이] 백준 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제풀이 N = int(input()) dp_table = [0] * (N+1) for i in range(2, N+1): dp_table[i] = dp_table[i-1] + 1 if i % 3 == 0: dp_table[i] = min(dp_table[i], dp_table[i//3] + 1) if i % 2 == 0: dp_table[i] = min(dp_table[i], dp_table[i//2] + 1) print(dp_table[N]) [문제풀이] 백준 2839번 설탕 개수 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제풀이 N = int(input()) count = 0 while N > 0: if N % 5 == 0: temp = int(N / 5) N -= 5 * temp count += temp break N -= 3 count += 1 if N == 0: print(count) else: print(-1) [알고리즘] Dynamic Programming Dynamic Programming Dynamic Programming에서 Dynamic programming은 딱히 의미 없는 용어이다. 그냥 Dynamic, 멋있어서 붙인 용어라고 한다. Dynamic programming은 Optimal Substructure(최적 부분 구조)와 Overlapping Subproblem(중복되는 부분 문제)를 만족할때 자주 사용한다고 한다. Optimal Substructure는 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 결과를 도출하고 그 결과를 모아 큰 문제를 해결할 수 있는 문제를 의미한다. Overlapping Subproblem은 동일한 문제를 반복적으로 해결하는 문제이다. Fibonacci Sequence 대부분 동적 프로그래밍 예제로서 피보나치.. [문제풀이] 백준 4963번 섬의 개수 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 풀이 import sys # 이거를 해줘야 하는지 몰랐었다... sys.setrecursionlimit(50000000) def dfs(x, y): if 0 [알고리즘] BFS (Breadth First Search) 너비우선탐색 그래프를 전체 탐색하는 방법 중 너비우선탐색은 DFS와 다르게 루트노드에 인접한 노드들 부터 먼저 탐색하고 그 다음으로 가까운 노드를 탐색하는 구조이다. 즉 정점에 가까운 노드들을 먼저 순회하고, 먼 노드는 나중에 순회하게 된다. 이러한 특징으로 인해서 일반적으로 두 노드 사이의 최단 경로를 찾고 싶을때 사용한다. 구현으로써는 큐를 이용한다. 장점 트리의 깊이가 얕은 경우에 매우 빠르게 동작할 수 있는 알고리즘이다. 더불어 단순하게 생각하면 깊이우선탐색보다 너비우선탐색이 더 빠르다. 또한 루트노드와 가까운 노드부터 탐색하기 때문에 최단경로를 보장할 수 있다. 단점 너비우선탐색은 깊이우선탐색보다 많은 메모리를 필요로 한다. 왜냐하면 다음에 탐색할 정점들을 알고있어야 하기 때문이다. 또한 노드의.. 이전 1 2 3 4 다음
