0. 들어가며 정렬 알고리즘은 시간 복잡도에 따라 성능이 좌우되며, 성능이 좋을 수록 구현 방법이 어려워진다 O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)버블 정렬(Bubble Sort)선택 정렬(Selection Sort)삽입 정렬(Insertion Sort)O(n log n)의 시간 복잡도병합 정렬(Merge Sort)퀵 정렬(Quick Sort)셸 정렬 1. 버블 정렬버블정렬은 인접한 두 수를 비교하며 정렬해나가는 방법으로 O(n²)의 느린 성능을 가지고 있다. 주요 처리 과정앞에서부터 (2개씩 비교를 )시작하여 큰 수를 뒤로 보내, 뒤가 가장 큰 값을 가지도록 완성해나가는 방법이다.한바퀴 돌면, 가장 오른쪽 원소는 최대값으로 fix될테니, 고정시켜두고, 그 앞 인덱..

문제 풀이 경우의수를 통해 규칙성을 발견해 dp[i] = dp[i-1] + 2 * d[i-2] 이라는 점화식을 세웠다.  코드n = int(input())dp = [0] * 1001# 초기값 지정dp[0] = 1dp[1] = 1for i in range(2, n+1): dp[i] = dp[i-1] + 2 * dp[i-2]print(dp[n]%10007) *주의dp = [0]*(N+1)로 dp배열을 만들 수 있지만, 이 경우 N=0인 경우에 dp[1]을 참조할 수 없게 된다 (런타임 에러 (IndexError) 발생)주어진 입력이  1 ≤ n ≤ 1,000 이므로, 처음부터 크기가 1001으로 배열의 크기를 지정해서 런타임에러를 방지할 수 있다.그게 아니라면, 런타임 에러를 방지하기 위해 아래와 같이..

문제   풀이시도1)  메모리초과K = int(input())if K==1: print(0,1,end=" ")else: dp = [""]*(K+1) dp[0] = "1" dp[1] = "0" for i in range(2,K+1): dp[i] = dp[i-1] + dp[i-2] final = dp[-1] a_num = final.count("1") b_num = final.count("0")print(a_num,b_num,end=" ") 메모리 초과 이유 dp 배열을 문자열로 채운 것이 메모리 초과의 이유다. 문자열의 길이는 지수적으로 증가하기 때문에 K가 크면 매우 큰 문자열을 생성하게 되고, 이에 따라 메모리 사용량도 급격히 증가하된다 ( 참고로..

슬라이딩 윈도우 알고리즘(Sliding Window)고정된 사이즈의 윈도우를 이동시켜셔 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘이다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하기에 유용하다ex) 구간 합 구하기, 부분 문자열 구하기 등   슬라이딩윈도우와 투포인터슬라이딩 윈도우 알고리즘은 *투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 부분 배열의 길이(크기)가 고정적 이라는 가장 큰 차이점이 있다.  슬라이딩 윈도우투포인터공통점-  부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘 - 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우O(N²) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있..

TSP (외판원 문제) 란? home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다. 즉, 아래와 같이 문제를 생각할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.  그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은..

플로이드 워셜 알고리즘 개요플로이드 워셜 알고리즘은모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다다익스트라 알고리즘과 마찬가지로, 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 그러나, 아래 두 가지에서 다익스트라와 차이가 있다. 다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있다. 음의 가중치를 가지는 그래프에서도 쓸 수 있다플로이드 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘각 단계마다 특정 한 노드 k를 거쳐가는 경우를 확인한다.a에서 b로 가는 최단거리보다, a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.점화식은 다음과 같다...

다익스트라 알고리즘다익스트라 알고리즘은 최단경로를 구하는 알고리즘 중 하나이다.다익스트라 알고리즘을 사용하면 하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있다. 다익스트라 알고리즘 원리다익스트라 알고리즘은 아래의 두 문장으로 정리될 수 있다.최단거리를 구할 노드에서 시작하여, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택한다.노드를 돌아가면서, 더 거리가 짧다면 값을 갱신한다. (a) 노드 0에서 거리를 기록한 후, 가장 가까운 노드인 1번노드를 선택한다(b) 선택된 1번노드를 기준으로, 거리가 최소가 되도록 갱신한다. 0번노드에서 3번 노드로 바로 갈 경우, 거리가 무한대이지만, 1번노드를 거쳐가면 거리가 6이므로 3번노드까지의 거리를 6으로 갱신한다. 가장 가까운 노드는 ..

문제* 아래 문제의 recursive property를 제시하라. 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다. 조약돌을 놓는 방법 (제약조건)- 각 열에는 적어도 하나의 조약돌을 놓아야 한다.- 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 목표돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기 합법적인 예 합법적이지 않은 예  문제풀이  다이나믹 프로그래밍 - 행렬의 Column 1">11부터 Column i">i𝑖 까지의 최적해(=최고점)는  Column 1">11부터 Column i−1">i−1𝑖−1 까지의 최적해를 포함하는 구조이기 때문이다.  패턴 분석각각의 Column에 돌을 놓을 수 있는 경우의 수는, 아래와 같이 4가지로 존재한다...