Beelog

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제는 위와 같으며 크기가 가장 작은 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적다는 점을 이용하여 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq heap = [] n = int(stdin.readline()) for _ in range(n): bundle = int(stdin.readline()) heapq.h..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 문제는 위와 같으며 최소 힙을 구현할 수 있으면 쉽게 풀 수 있는 문제입니다. 또한 파이썬에서는 heapq 라이브러리를 통해 문제를 보다 쉽게 실수 없이 해결할 수 있습니다. 먼저 파이썬에서 heapq 를 사용한 코드를 살펴보면 다음과 같습니다. from sys import stdin import heapq n = int(stdin.readline()) heap = [] for _ in range..

www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제는 위와 같으며, 중위순회를 사용하면 위치가 앞인 노드부터 차례로 방문할 수 있습니다. 이때 해당 노드의 레벨을 키로 하고 노드의 위치를 값으로 하여 각 레벨에 존재하는 노드의 위치를 리스트로 저장합니다. (예: {level: [position, position, ...]. level: [position, ...], ...} ) 그런 다음 각 레벨의 노드 위치 리스트에서 가장 뒤에 있는 노..

www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제는 위에서 확인할 수 있으며 예제로 주어진 압축 문자의 압축을 푸는 방법을 보면 아래와 같습니다. 33(562(71(9))) => 33(562(79)) => 33(567979) => 3567979567979567979 => 결과: 19 처음에는 아주 쉽게 생각해서 순서대로 스택에 저장하다가 ")" 가 들어온 경우 "(" 를 찾을 때까지 앞으로 이동하면서 그 수를 세고 "(" 를 만나면 그 앞에 있는 수..

문제는 위와 같으며 skill 의 문자를 하나씩 skill_trees 의 요소에서 찾아서 그 인덱스를 저장하고 순서가 더 뒤에 있지만 앞 인덱스보다 먼저 찾은 경우 순서를 틀린 것으로 하여 반복을 종료하고 그렇지 않고 끝까지 인덱스의 오름차순을 지킨 경우 가능한 스킬트리 개수를 하나 증가하는 방식으로 문제를 해결하였습니다. 파이썬 코드는 다음과 같습니다. # 코딩테스트 연습 > Summer/Winter Coding(~2018) > 스킬트리 skill = "CBD" skill_trees = ["BACDE", "CBADF", "AECB", "BDA"] answer = 0 for sk in skill_trees: i = -1 count = 0 for s in skill: idx = sk.find(s) if i..