흰 스타렉스에서 내가 내리지

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net n = int(input()) arr = list(map(int, input().split())) dp = [1] * n for i in range(1, n): for j in range(i): if arr[j] = dp[i]: dp[i] = dp[j] + 1 print(max(dp)..

# 백트래킹 - 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서, 이 경우가 답이 될 수 없으면 그 노드의 이전(부모)로 돌아간다. - 구현을 하면 재귀 형태가 된다. - 재귀 함수는 탈출 조건이 필요한데, 탈출 조건은 해를 만족하였을 때로 하면 된다. # 백트래킹의 포맷 def backtrack(candidate): # 만약 현재 후보군이 유효한 해라면 정답 처리하고 backtrack 함수를 종료 if find_solution(candidate): output(candidate) return # 반복문을 돌면서 가능한 모든 후보군에 대해 탐색 for next_candidate in list_of_candidates: # 유효한 후보군인 경우에만 탐색 진행 if is_valid(next_cand..

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net n = int(input()) next_move = list(map(int, input().split())) arr = [i for i in range(n)] now = 0 res = [] for _ in range(n): p = arr.pop(now) res.append(p+1) if _ == n-1: break move = next_move[p] if move > 0: now..

# 1. 만약 q 가 deque 일 경우 # 만약 q가 deque 일 경우 while q: q 가 일반 큐일 경우, 시작점을 q와 visited에 먼저 채워 넣는다. while문을 시작하고, for 문 전까지 원하는 로직만 작성한다. 다음으로 이동할 수 있는 칸에 대하여 for문을 수행하는데, 이 때는 방문하지 않은 점들만 탐색하고, q에 추가하자마자 방문 처리를 해준다. 이는 가중치는 없고 오로지 먼저 도착하면 장땡인 문제에 적용된다. # 2. 만약 q가 heapq 일 경우 # 만약 q가 heapq일 경우 while q: 먼저 도착한다고 되는게 아니라, 가중치가 있어서 이에 따른 우선순위가 존재할 때 적용할 수 있는 문제다. 일반 ..

- 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 다익스트라 최단 경로 알고리즘 ✅ 플로이드 워셜 알고리즘 ✅ 벨만 포드 알고리즘 # 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작한다. - 실제로 GPS 소프트웨어의 기본 알고리즘이다. - 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드..

'한 번 계산한 문제는 다시 계산하지 않도록 한다.' 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. # 메모이제이션 :: memoization - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법을 의미한다. - 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. - 구현: 단순하게, 한 번 구한 정보를 리스트에 저장한다. - 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때에는 이미 구한 정답을 그대로 리스트에서 가져온다. # 다이나믹 프로그래밍과 분할 정복의 차이 - 다이나믹 프로그래밍은 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net # Parametric Search - 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. - '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 파라메트릭 서치를 사용한다. - 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. - 코딩 테스트에서는 보통 파라..

- 입력 데이터의 개수가 많은 문제에 input()을 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. - 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하며 시간 초과를 피할 수 있다. import sys input_data = sys.stdin.readline().rstrip() - rstrip() 함수를 꼭 호출해야 한다. - 소스코드에 readline() 으로 입력하면 '\n' 도 입력되기 때문.

순차 탐색 이진 탐색 # 1. 순차 탐색 - 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다. # 2. 이진 탐색 - 배열 내부에 데이터가 정렬되어 있어야만 사용할 수 있다. - 3개의 변수를 사용한다. → 시작점, 끝점, 그리고 중간점 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. - 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN) 이다. * 이진 탐색 구현 ..

선택 정렬 :: selection sort 삽입 정렬 :: insertion sort 퀵 정렬 :: quick sort 병합 정렬 :: merge sort 계수 정렬 :: count sort ... # 1. 선택 정렬 :: Selection Sort - O(N^2) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾼다. - 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 한다는 의미에서 선택 정렬 알고리즘이라 한다. arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[min_i..