Code Diary Code Diary

처음에는 리스트만을 이용해서 짰다. 14번째 줄에 index를 찾는게 시간을 많이 소모해서 시간초과가 났다. 그래서 이번에는 딕셔너리를 이용해서 짰다. 딕셔너리 두 개 씩 저장하면서 늘어난 시간

처음에는 그냥 리스트 메소드 중 count를 이용해서 해봤는데 아니나 다를까 바로 시간초과가 나왔다. N이 오십만 까지 입력되기 때문에 시간단축을 위해 sys입력과 이진탐색을 모두 사용했다. 이진탐색이란 오름차순 정렬된 배열에 사용하는 탐색방법이다. 그러니 먼저 L1.sort()를 해주고, 이진탐색함수를 정의해주자. 매개변수로는 배열(array)과 찾는 수(target)와 시작점(start) 끝점(end)을 받는다. 알고리즘은 매우 간단하다. 배열을 반으로 나누어 찾는 수가 작은 쪽에 있으면 end를 중간 수에서 바로 전 수(mid-1)로 지정해 작은 쪽에서 다시 진행하고 큰 쪽에 있으면 시작점을 중간 수 바로 다음 수(mid+1)로 지정해 큰 쪽에서 다시 진행한다. 이 과정을 정확히 중간 수(mid)에..

병합정렬이란 배열을 길이 1이 될때까지 쪼갠 후 그 상태에서 부터 두 조각씩 붙이면서 정렬해가며 병합하는 방법이다. 재귀함수를 이용한다. 이 문제는 일반적인 병합정렬에서 추가적으로 배열(ans)을 하나 더 만들어 그 배열에 정렬될 때마다 정렬되는 요소를 집어 넣는다.

컴퓨터는 앞에서부터 순서대로 읽기 때문에 예를 들어, ' 문자를 print(' ')내에서 출력하려는데 그냥 넣어버리면 컴퓨터가 print(' ' ')이렇게 읽어야 하는 걸 print(' ' ') 이렇게 읽어버려서 오류가 나기 때문에 print(" ' ")처럼 구분이 가게 해주거나 print(' \' ')처럼 ' 문자 앞에 \ 문자를 넣어주어 (이것은 출력하는 문자임)을 드러내준다. 다만 이제 \ 문자를 또 출력하기 위해서는 print(' \\ ')처럼 \앞에 또 \을 붙여주면 된다.

리스트를 만들고 요소가 들어올 때마다 정렬하고 중간값을 출력하는 알고리즘을 짜봤다. 잘 돌아가기는 했지만 돌아가는게 너무 오래걸려 오답이었다. 아무래도 출제자는 정렬로 푸는 것을 원하지 않는 모양이다. 빠르게 돌아가는 알고리즘을 만들기 위해서 힙을 사용했다. 힙이란 완전 이진 트리의 일종으로 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료구조이다. 부모가 자식보다 큰 최대 힙과 부모가 자식보다 작은 최소 힙이 있다. heapq 모듈은 이런 힙 자료구조를 파이썬에서 이용하게 해준다. min heap을 이용하면 원소들은 항상 정렬된 상태로 삽입, 삭제되고 가장 작은 값은 언제나 인덱스 0에 위치한다. 그리고 그 뒤에 원소들은 왼쪽 자식 노드는 부모 노드*2, 오른쪽 자식 노드는 부모 노드*2 + 1로 계속 이..

여러가지 경우의 수로 주어진 무게 안에서 최고의 가치를 끌어내는 알고리즘을 만들어야만 했다. 처음에는 두개의 리스트나 딕셔너리로 모든 경우를 조합해서 그 중 무게가 허용되는 것 중에서 최고의 가치 를 가지는 조합을 뽑는 알고리즘을 만들어보려 했으나 실패했다. 그리고 이 문제는 냅색 알고리즘으로 풀어낼 수 있는 것을 알아냈다. 0 1 2 3 4 5 6 7 weight value 6 13 0 0 0 0 0 13 13 4 8 0 0 0 8 8 13 13 3 6 0 0 6 8 8 13 14 5 12 0 0 6 8 12 13 14 list[i][j] = list(value+knapsack[i-1][j-weight], list[i-1][j]) 냅색 알고리즘이란 물건의 수 N과 허용된 무게 K로 이루어진 리스트를 돌..

리스트로 받은 후 동일한 것이 있는지 세주는 매우 간단한 문제였다. 그런데 이 문제를 푸는 다른 방법들이 배울만 해 이 문제를 포스팅한다. l.count(x)를 이용하면 리스트에 있는 x의 개수를 쉽고 빠르게 알 수 있었다.

이런식으로 min(L)를 이용해서 최솟값을 찾는 방법으로 풀어냈다. 최솟값을 구하는 3가지 방법을 소개한다. 1. 위와 같이 min(L)이용하기 2. 반복문으로 요소들 하나씩 대조해보기 3. L.sort()으로 리스트 오름차순 정렬 후 L[0] 출력