https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw#none SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 높이가 B인 선반과 N명의 점원 각 점원들의 키는 Hi 고 (1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 a-> b와 같은 순서로 비상연락망과 연락을 시작하는 당번에 대한 정보가 주어진다. 한 번에 여러 명에게 연락이 가능할 때 연락을 받을 수 있는 사람 중 가장 마지막에 받은 사람의 번호를 출력하라 이 때, 가장 마지막에 받은 사람이 여러 명이라면 제일 큰 번호 출력 # 접근 방법 bfs를 이용하여 연락가능한 사람들을 큐에 넣어준다. 이후 큐에 있는 번호를 pop해주며 연락 사이클을 돌려주는..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net # 조건 문서의 우선 순위에 따라 인쇄를 진행한다. 우선 순위는 동일할 수 있다. 우선 순위가 가장 높은 경우가 인쇄 차례일 때만 인쇄를 진행한다. 이 때 몇 번째로 인쇄되는지 궁금한 문서의 인덱스가 주어질 때 몇 번째 인쇄되는지 구하여라. # 접근 방법 문제에 나와있듯이 deque를 이용하여 앞에서의 출력, 뒤로 입력을 해주었다. 이 때, 처음 궁금했던 문서였음을 알리기 위하여 인덱스를 저장해주고,..

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..