개발일기

문제 링크 : https://www.acmicpc.net/problem/1057 문제 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 ..

문제 링크 : https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 ..

힙은 특정한 규칙을 가지는 트리이다. 최소값과 최대값을 찾는 연산을 빠르게 하기 위해 만들어진 완전이진트리를 토대로한다. # 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 # 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 파이썬 힙 자료구조 파이썬의 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다. 모든 부모 노드는 그의 자식 노드보다 값이 크거나 작은 바이너리 트리(이진트리) 구조이다. 0의 인덱스를 시작으로 k번재 원소가 항상 그의 자식원소인 2k + 1, 2k + 2 보다 작거나 같은 최소 힙 형태로 정렬된다. heapq 모듈은 별도의 설치 없이 import 를 통해 바로 사용할 수 있다. 힙 관련 함수 heapq.hea..

https://hanmingi.tistory.com/159 defaultdict( ) 클래스는 위 글에서 살펴본 딕셔너리를 만드는 dict 클래스의 서브 클래스이다. 작동방식은 dict 클래스의 방식과 거의 비슷한데, defaultdict 인자로 주어진 객체의 기본값을 딕셔너리 값의 초기값으로 지정하여 사용할 수 있다. # 사용 방법 >>> from collections import defaultdict >>> dict = defaultdict(int) >>> dict["key1"] 0 >>> dict { "key1" : 0 } 위와 같이 dict를 int형으로 지정하게 되면 값을 지정하지 않은 키는 그 값이 0으로 지정된다. >>> dict["key2"] = "test" >>> dict { "key1"..

# 해시 - Key Value 쌍으로 데이터를 빠르게 찾아 문제를 해결한다. 프로그래머스에서 해시에 관한 문제는 Key Value 쌍으로 데이터를 찾아 문제를 해결 하도록 되어 있다. 이 때 많이 사용하는 것이 딕셔너리다. # 딕셔너리란? 사람은 누구든지 "이름" = "한민기", "생일" = "10월 08일" 등으로 구별할 수 있다. 파이썬도 이처럼 대응 관계를 나타낼 수 있는 자료형을 가지고 있다. 파이썬 뿐만 아니라 C언어, JAVA 등의 요즘 사용하는 대부분의 언어도 이러한 대응 관계를 나타내는 자료형을 가지고 있는데, 이를 연관 배열 또는 해시라고 한다. 파이썬에서는 이러한 자료형을 딕셔너리라고 부른다. 딕셔너리를 직관적으로 해석하면 사전이라는 뜻이 된다. 즉 "people" 이라는 단어에 "사람..

문제 링크 : https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄..

문제 링크 : https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net 문제 파스칼 고등학교에 다니는 많은 여학생들은 규정에 없는 귀걸이를 착용한 채 도망다닙니다. Sneddon 교감선생님은 흔들거리는 긴 빨간 귀걸이들을 볼때마다 압수합니다. 교감선생님은 귀걸이를 압수당한 여학생들을 숫자를 매겨 리스트를 작성하고 있습니다. 그리고 압수한 귀걸이 뒤쪽에 여학생 번호와 마음대로 선택한 'A' 또는 'B'를 함께 적어두었습니다. 모든 정규 일과와 방과후 수..

문제 링크 : https://www.acmicpc.net/problem/1268 1268번: 임시 반장 정하기 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. www.acmicpc.net 문제 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇..