알고리즘

문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 문제 풀이 i가 현재 숫자, j가 i보다 작은 제곱수들일 때, dp[i - j] 중 가장 최소항의 개수가 작은 것을 찾아낸다. 이 값에 1을 더해주면 i의 최소항의 개수가 나타난다. (1을 더해주는 이유는 제곱수에 대한 항의 수를 추가하기 위해서이다.) 점화식 => dp[i] = min(dp[i - j]) + 1 n = int(input())..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 문제 풀이 포도주가 한 개, 두 개 주어졌을 경우는 별다른 계산 필요없이 첫 번째를 선택하는 경우, 첫 번째 + 두 번째를 선택하는 경우가 최대이다. 세 개 주어졌을 경우에는 (1번 + 3번), (2번 + 3번), (1번 + 2번 [두 개 주어졌을 때의 최댓값) 중 최대의 값을 선택하게 된다. 4개부터 n개의 포도주가 주어졌을 때를 보면, 1) n번째 선택 + (n - 1)번째 선택..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 문제 풀이 Dynamic Programming 문제이다. dp 테이블에 모든 원소를 0으로 초기화시켜준 후 하나씩 반복하여 계산을 하는 것이다. DP는 처음에는 이해가 잘 안되는데 생각해보면 간단하다. 예를 들어 4에 대한 연산의 결과를 생각해보자. 4는 4 -> 2 -> 1 의 연산을 하게된다. 그런데 이걸 하나씩 매번 해줄 필요가 없다. 2에 대한 연산의 횟수(DP(2))에 2를 도출해낸 연산(나누기 2) 한 번(+1)을 카운트해주면 DP[4] = DP[2] + 1이 된다. 이와 같은 ..

문제 링크 https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net 문제 설명 문제 풀이 입력 받은 대로 바로 출력할 수 있어야 한다. 입력이 없을 경우 프로그램을 끝내기 위해 EOF(End Of File)로 예외처리를 해주어 break를 걸어준다. while True: try: print(input()) except EOFError: break

그래프 vs 트리 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드 없음 루트 노드 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프의 구현 방법 1) 인접 행렬 : 2차원 배열을 이용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접 행렬을 이용할 때는 간선 정보를 저장하기 위해 O(V2)만큼의 메모리 공간이 필요하다. 또한, 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있다. ex : 플로이드 워셜 알고리즘 2) 인접 리스트 : 리스트를 사용하는 방식 노드 개수 V, 간선 개수 E인 그래프에서 인접..

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 ('길 찾기' 문제) 다양한 유형에 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다. 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘 으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘 -> 기본적으로 그리디 알고리즘으로 분류 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복 원리 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을..

다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건) 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법 (캐싱) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 # 피보나치 수열 소스코드 - 메모이제이션의 예 [탑다운] # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x ==..

이진탐색 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 찾는 과정 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서 수행된다. # 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): ..