명왕성의 공전기록

https://www.acmicpc.net/problem/20551 해당 문제는 주어진 배열의 길이 | 찾아야 할 요소 길이 | 배열 요소 | 찾아야 할 요소를 주고, 해당 배열을 정렬한 뒤, 찾아야 할 요소가 정렬된 배열에 존재하면 해당 요소의 index를, 없으면 -1 을 반환하는 문제다. 이분탐색 문제인데 2분만에 풀진 못했다. 그 이유로는 처음 완성한 이진탐색 로직에는, 배열에 중복된 요소가 없으리라 가정하고 작성되었기 때문에 만약 해당 함수에 arr = [5,5,5,5,5], x = 5 가 인자로 들어오더라도 가장 처음의 index값이 아닌, 중간값 index를 반환한다는 문제를 발견했다. def bisect (arr, x) : left, right = 0, len(arr) if arr[left..

https://www.acmicpc.net/problem/2193 문제는 N자리의 이친수 (0으로 시작하지 않으며, 1이 두번으로 나타나지 않는 수)의 갯수를 구하는 문제다. 직접 써보며 점화식을 구할 수 있을 것 같아 각 N자리에 몇 개의 이친수가 존재하는지 헤아렸다. ''' 1 : 1 / 1 2 : 10 / 1 3 : 100 101 / 2 4 : 1000 1001 1010 / 3 5 : 10000 10001 10010 10100 10101 / 5 6 : 100000 100001 100010 100100 101000 100101 101001 101010 / 8 ''' 헤아리다보니 [1,1,2,3,5,8] 라는 익숙한 수의 조합이 등장한다. 보였다! 틈새의 점화식! 전체 소스 코드 import sys d..

https://www.acmicpc.net/problem/9020 문제는 정수 n 이 주어질 때, 가장 차이가 적으며 합이 n을 만족하는 두 소수를 찾아 출력하는 문제다. 이전 포스팅했던 에라스토테네스의 체를 활용하여 소수를 판정하는 테이블을 만든 뒤, 반복문을 통해 조건을 만족하는 값을 찾았다. 처음 작성한 코드 # table = 에리스토테네스의 체로 소수판정한 리스트 | n = 정수 def act (table, n) : x,y = 10000,0 for i in range(n-1, 0, -1) : if table[i] : for j in range(n-1, 0, -1) : if table[j] and i + j == n and abs(x - y) > abs(i - j): x,y = i,j return ..

https://www.acmicpc.net/problem/5557 문제는 다음과 같이 주어진 요소에 + || - 를 조합하여, 요소 마지막에 나오는 숫자를 만들 수 있는 경우의 수를 구하는 문제다. 주어지는 요소의 수가 최대 100개 이하이기 때문에 모든 경우를 직접 모두 구하려면 2^n의 높은 시간복잡도가 우려되고, 왼쪽부터 계산할 때 0 미만 | 20 초과의 수는 포함하지 않기 때문에 다이나믹 프로그래밍을 활용하여 풀이하였다. 풀이 과정은 다음과 같다. 앞서 얘기했던 것처럼 0 이상 | 20 이하의 수만 사용하기 때문에, 다이나믹 프로그래밍으로 메모리제이션할 내용들은 아래와 같은 형식으로 담을 수 있다. dp = [[0] * 21 for _ in range(N-1)] 즉, 0 ~ 20 까지의 나오는 ..

https://www.acmicpc.net/problem/20291 해당 문제는 입력값에서 등장하는 확장자 파일의 갯수를 확장자 이름의 사전순으로 정렬하여 반환하는 문제다. 파이썬에서는 아래와 같은 콜렉션 모듈에서 제공하는 Counter 메서드를 사용해도 되지만, 이번 포스팅에서는 다루지 않고, 파이썬과 자바스크립트 모두 딕셔너리(Python) | 객체(JS)를 사용하여 풀이했다. from collections import Counter 문제 풀이는 그리 어렵지 않다. 먼저 확장자를 key | 등장 횟수를 value로 가질 딕셔너리 | 객체를 선언한다. 이후 파일명에서 등장하는 온점이 하나 뿐이라고 했으니, '.'을 기준으로 입력값을 쪼갠 뒤에 뒤에 있는 확장자를 딕셔너리 | 객체에 추가한다. 데이터 추..

https://www.acmicpc.net/problem/4948 해당 문제는 입력값이 1

https://www.acmicpc.net/problem/11286 어제 포스팅한 최소 힙과 비슷한 문제지만, 절댓값으로 정렬한 힙을 구현하는 문제다. 특이사항으로는 가장 작은 값이 여러 개일 경우, 가장 작은 수(절댓값이 같은 수가 둘 있다면 음수)를 먼저 출력하고 제거해야 한다. 내가 풀이한 방법은 다음과 같다. - 힙 데이터 추가의 경우 ( v != 0 ) 먼저 정수 절댓값으로 변환 후 절댓값 힙에 넣기 전, 해당 정수를 기록하기 위한 빈 딕셔너리를 선언했다. 이 딕셔너리는 중복도 헤아리기 위해 현재 힙에 있는 특정 정수의 수를 기록한다. storage = {} for v in arr : if v != 0 : # 자바스크립트의 경우 단축평가를 활용한 # storage[v] = (storage[v] ..

https://www.acmicpc.net/problem/1927 먼저 힙은 이진트리를 기반으로 한 자료구조로 특정한 규칙에 따라 원소들이 정렬되어 있는 자료구조다. 이진트리란, 한 노드가 최대 두 개의 자식 노드를 가질 수 있는 노드로, 이 덕분에 계층적 정렬 저장이 가능하다. (간단히 [1,2,3] 을 하나의 큐라고 한다면, 중간에 위치한 2는 앞에 1 | 뒤에 3 이라는 자식 노드를 가짐을 의미한다.) 자료구조 힙의 경우는, 파이썬에서 heapq라는 내장 모듈을 불러와 사용이 가능하다. 물론 직접 힙을 구현하여 사용하는 방법도 있겠지만, 비슷한 자료구조인 큐보다는 비교적 사용빈도가 적기에 해당 포스팅에서는 모듈을 사용한 풀이만 다룬다. heapq를 사용한 힙에서 사용하는 메서드는 여러가지가 있겠지만..