https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net # 조건 1번부터 N번까지의 사람이 원을 이루며 앉아있고 양의 정수 K가 주어진다. K번째 사람을 제거하며 N명 모두가 제거 될 때까지 반복 제거되는 순서를 (N, K) - 요세푸스 순열이라고 한다. # 접근 방법 큐의 성질을 이용하여 '줄 세우기와 같이' 앞에서 빼주고 K번째가 아니라면 다시 APPEND해준다. 출력 모양이 좀 이상해서 좀 당황했지만 자료구조를 떠올린다면, 어려운 문제는 아니였다고 생각한다. N, K = map(int, input().split()) arr = [..

앞에서 봤던 트리의 종류 중 높이가 h이고 노드수가 n개 일 때, 포화 이진트리의 1번부터 n번까지 빈자리가 없는 트리였던 완전 이진 트리에 있는 노드 중 키 값이 가장 큰 노드 or 키 값이 가장 작은 노드를 찾기 위해 만든 자료 구조이다. 최대 힙 (max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리 (부모 노드의 키값 > 자식 노드의 키값) 루트 노드 : 키값이 가장 큰 노드 최소 힙 (min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리 (부모 노드의 키 값 < 자식 노드의 키 값) 루트 노드 : 키값이 가장 작은 노드 삽입 삭제 힙에서는 루트 노드만이 삭제 가능 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최솟값 또는 최댓값 구하기 가능 # 파이썬에서의 힙..

앞서 봤던 트리들에서 탐색 효율을 높이기 위해 사용하는 '이진 탐색 트리'에 대해서 알아보자. 목차 1. 이진 탐색 트리? 2. 연산 3. 성능 1. 이진 탐색 트리? 탐색 작업을 효율적으로 하기 위한 자료구조 모든 원소는 서로 다른 유일한 키를 가진다. key(왼쪽 서브 트리) < key(루트 노드) < key(오른쪽 서브 트리) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리 중위 순회하면서 오름차순으로 정렬된 값을 얻을 수 있다. 2. 연산 탐색 연산 루트에서 시작한다. 탐색할 키 값 x를 루트 노드의 키 값과 비교한다. (키 값 x = 루트 노드의 키값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공 (키 값 x < 루트 노드의 키값)인 경우 : 루트노드의 왼쪽 서브 트리에 대해서 탐색연..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net # 조건 숫자 카드는 정수 하나가 적혀있다. N개의 숫자카드를 입력 받는다 이후 주어지는 M개의 카드가 주어질 때 '같은 번호'의 카드가 몇 개인지 출력하라 # 접근 방법 및 SOLUTION 리스트를 정렬 후 counter 메서드를 이용하여 푸니 시간초과가 발생하였다. 이진 탐색 또는 딕셔너리를 활용해주는 것이 바람직해 보였고 딕셔너리 내에 각 카드 숫자의 개수를..

# 조건 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이 때, 나이가 적은 순으로, 나이가 같다면 등록순으로 출력하여라. # 접근 방법 버블 정렬을 이용하여 나이순으로 정렬해 줄 수 있다. 하지만 파이썬엔 sort라는 좋은 함수가 있고 lambda라는 또 다른 함수도 존재한다. 처음에 문자열로 받아주기 때문에 lambda x:x[0]로 정렬을 해준다면 문자열 기준 1 -> 9와 같이 보기 때문에 나이가 9살인 친구가 10인 친구보다 뒤로 가게 된다. 따라서 정렬 기준을 int형으로 바꿔준다. T = int(input()) people = [list(map(str, input().split())) for _ in range(T)] people.sort(key= lambda x:i..

지금까지는 단순 구조, 선형 구조에 대해서 알아보았다. 이번 글에서는 '비선형 구조' 중 하나인 '트리'에 대해 알아보자! 목차 1. 개념 및 정의 2. 이진트리 3. 순회 4. 표현 및 저장 5. 연결 리스트 1. 개념 및 정의 개념 비선형 구조 원소들 간에 1 : N 관계를 가지는 자료구조이다.ㅣ 또한 원소들 간 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가며 확장되는 나무(트리) 모양의 구조 정의 한 개 이상의 노드로 이루어진 유한 집합 노드 중 최상위 노드 -> 루트(root) 나머지 노드들은 n개의 분리 집합 T1... TN으로 분리될 수 있다. 이들 T1... TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다. 용어 정리 노드(node..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net # 조건 VPS를 판별하는 문제이다. VPS란, 괄호가 짝이 맞는 경우를 말하는데, (())와 같이 괄호안에 올바른 괄호가 들어가 있는 경우도 포함이다. 첫 째줄에는 테스트 케이스 수 N, 그 이후에는 괄호 문자열이 주어진다 # 접근 방법 및 SOLUTION 전형적인 STACK문제라고 생각이 들었다. 여는 괄호가 온다면 괄호 리스트에서 POP과 동시에 STACK에 넣..

백준 5557_1학년 # Problem 줄 지어있는 숫자 들이 있을 때 아래의 조건을 지키며 등식을 완성하여라 마지막 두 숫자 사이에는 &#39;=&#39;, 나머지 숫자 사이에는 &#39;+&#39;또는 &#39;-&#39; 이 때, 왼쪽부터 계산을 할 때, 중간 결과값이 모두 0이상 20이하여야 한다. 올바른 등식의 수를 구하는 프로그램 작성 # 접근 방법 모든 경우의 수를 구하게 되면 2^100의 경우의 수가 생기므로 dp로 풀어야 될 것 같다. bottom-up 방식으로 DP TABLE 이용 DP TABLE의 경우 최댓값이 20이 넘어가면 안된다는 조건이 있기 때문에 21개만 만들어주면 된다. 점화식 equation[i][j+number[i]] += equation[i-1][j] equation[..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net # 조건 - D km 길이의 고속도로를 지나는데 이 고속도로는 심각하게 커브가 많아 운전하기 힘들다. - 이 고속도로에는 지름길이 존재하는데 - 모든 지름길은 일방통행이며, 고속도로 역주행은 불가 - 운전해야하는 최소 거리를 구하여라 # 접근 방법 및 풀이 과정 - 문제를 읽으며 드는 생각은 거리를 기록해둔 후 이를 통하여 최소 값을 구하면 될 것같다. - 내가 이용하는 지름길의 거리와..