Python

문제 링크 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/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 설명 문제 풀이 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 이 문제는 패턴이 잘 눈에 띄지 않아서 어려웠는데, 결과적으로 굉장히 간단한 패턴을 찾을 수 있다. 예를 들어, dp[0][2]를 선택하고 싶을 경우 앞에서는 dp[1][0] 혹은 dp[1][1]을 선택해야 하는데 둘 중 큰 것을 선택해야만 한다. dp[1][2]를 선택하고 ..

문제 링크 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이 된다. 이와 같은 ..

신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데 대표적인 최소 신장 트리 알고리즘이 '크루스칼 알고리즘'이다. 최소 신장 트리는 일종의 트리 자료구조이므로, 최종적으로 신장 트리에 포함되는 간선의 개수가 '노드의 개수 - 1'과 같다는 특징이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. [알고리즘] 1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 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): ..

정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정의 반복. 데이터가 N개일 때, '가장 작은 것을 선택'하는 과정을 N-1번 반복하면 정렬이 완료된다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(Array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[..