본문 바로가기

PAINTYCODE

 (61)
[문제풀이] 백준 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와 다르게 루트노드에 인접한 노드들 부터 먼저 탐색하고 그 다음으로 가까운 노드를 탐색하는 구조이다. 즉 정점에 가까운 노드들을 먼저 순회하고, 먼 노드는 나중에 순회하게 된다. 이러한 특징으로 인해서 일반적으로 두 노드 사이의 최단 경로를 찾고 싶을때 사용한다. 구현으로써는 큐를 이용한다. 장점 트리의 깊이가 얕은 경우에 매우 빠르게 동작할 수 있는 알고리즘이다. 더불어 단순하게 생각하면 깊이우선탐색보다 너비우선탐색이 더 빠르다. 또한 루트노드와 가까운 노드부터 탐색하기 때문에 최단경로를 보장할 수 있다. 단점 너비우선탐색은 깊이우선탐색보다 많은 메모리를 필요로 한다. 왜냐하면 다음에 탐색할 정점들을 알고있어야 하기 때문이다. 또한 노드의..
[알고리즘] DFS (Depth First Search) DFS (Depth First Search) 그래프를 전체 탐색하는 깊이 우선 탐색 DFS는 탐색을 시작한 시작점부터 해당 부분을 완벽하게 탐색하고 다음으로 넘어가는 방식이다. 아래 그림을 보면 좀더 빠르게 이해할 수 있다. 위 그림처럼 한개의 분기에 대해 모든 탐색이 완료되면 다음 분기로 넘어가고, 완벽하게 탐색한 후에 다음 분기로 넘어가는 흐름을 띄고 있다. 이는 스택, 재귀호출 방식으로 구현할 수 있다. 일반적으로 재귀호출을 사용하였을때 구현하기 편해 자주 사용하지만, 스택오버플로우가 발생할 수 있기 때문에 잘 구현해야 한다 (노드 방문시 방문여부를 검사하면서 진행해야 무한반복에 빠지지 않을 수 있다). 장점 한 분기의 깊이가 깊더라도 완벽하게 탐색하고 다음 분기로 넘어가기 때문에 목표노드가 깊은 ..
[문제풀이] 백준 4673번 셀프 넘버 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net org_numbers = set(range(1, 10001)) gen_numbers = set() for number in org_numbers: keep = number while number > 0: keep += int(number % 10) number = int(number / 10) gen_numbers.add(keep) self_numbers = sorted(org_numbers-gen_numbers..
[알고리즘] 완전탐색 (Exhaustive Search) Exhaustive Search 완전탐색은 무식하게 문제를 풀어나가는 방식이라고 하는데, 필자 생각에는 무식하다는 표현은 어울리지 않는 것 같다. 대부분의 알고리즘 문제는 완전탐색으로 다 풀수 있을 정도로 강력한 방식이다. 물론 그래서 무식하다고 부를 수 있지만 사실 컴퓨팅 성능이 미친듯이 좋으면 어떤알고리즘을 쓰더라도 빠르게 결과를 볼 수 있다. 그래서 무식한 방법이라고 절대 무시하면 안된다. 완전탐색을 문제를 해결하기 위한 모든 경우의 수를 나열하고, 정답을 찾아가는 방법을 의미한다. 완전탐색에는 Brute-Force, Bitmask, Recursive Fuction, Permutation, BFS, DFS 알고리즘이 있다. 완전탐색은 탐색의 방법론을 의미하고 그 안에 다양한 알고리즘들이 있다. Br..
[문제풀이] 백준 14713번 앵무새 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 7차 시도 n = int(input()) lines = [] for i in range(n): lines.append(list(map(str, input().split()))) target = list(map(str, input().split())) for item in target: correct = False for idx in range(n): if len(lines[idx]) != 0: if item == lines[idx][0]: lines[i..

티스토리툴바