조준장 개발자 생존기

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 알고리즘 - set() 자료형을 통해 진실을 아는 사람과 파티에 참여하는 사람을 입력받는다. - 파티의 수만큼 반복하여 파티에서 진실을 아는 사람이 포함되어 있는 파티를 찾는다. 파티의 수만큼 반복하는 이유는 모든 파티를 확인 후 진실을 아는 사람이 더 생길 경우 모든 파티를 한번 더 확인해줘야 하기 때문이다. 따라서 최대 파티의 수만큼 반복하여 진실을 아는 사람을 찾아야 한다. - 반복문을 통해 각 파티의 참여한 사람을 확인하고 파티의 참여한 사람 중 진실을 아는 ..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 - 리스트 안에 미리 제일 작은 수를 넣어놓는다. - 비교할 수도 제일 작은 수로 초기화시킨다. - 각 행의 열의 크기를 비교하면서 타겟보다 큰 수라면 큰 수를 heap 리스트에 추가한다. - 다음으로 heap 리스트에 제일 작은 수를 팝하고 그 수를 타겟으로 바꾼다. - n번째로 큰 값을 구하는 것으로 n번째보다 큰 수이면 리스트에 제일 작은 수를 팝한 후 큰 수를 heap 리스트에 넣는 방법을 문제를 수행했다. 코드 import heapq import..

문제 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 퍼즐 모양과 그 모양을 만들기까지 걸린 횟수를 딕셔너리형을 처리하여 무한 루프에 빠지지 않게 하고 답을 도출한다. - 빈 공간(0)에 인덱스를 찾고 그래프에서 빈 공간의 x 좌표와 y 좌표를 찾는다. - 상/하/좌/우를 탐색하여 빈 공간의 인덱스와 현재 좌표를 바꾼다. - 현재 퍼즐 모양이 없다면 딕셔너리에 추가하고 이 과정을 반복하여 정리된 모양의 퍼즐을 찾는다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): d..

문제 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 알고리즘 - 이분 탐색과 bfs 탐색을 통해 문제를 수행한다. - 이분 탐색을 통해 현재 중량을 구하고 그 중량으로 다리를 건널 수 있는지 bfs 탐색을 통해 확인한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): queue = deque([start]) visited[start] = True # 큐가 없을 때까지 반복 while..

문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 알고리즘 - 테스트 케이스만큼 반복하고 연산의 수만큼 반복하여 연산을 수행한다. - 삽입 연산인 경우 최대 힙과 최소 힙을 나누어 푸시하고 정수의 여부를 체크한다. - 제거 연산의 경우 조건문을 통해 최대 힙을 제거할 건지 최소 힙을 제거할 건지 확인한다. - 최대 힙이나 최소 힙 모두 반복문을 통해 이미 제거된 정수가 있는지 확인하고 있다면 팝하여 제거한다. - 그 후 최대 힙이나 최소 힙을 팝하여 제거한다. - 연산이 끝나고 정수가 없다면 "EMPT..

문제 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 알고리즘 - 단어의 수만큼 반복하여 단어를 확인한다. - 반복문을 통해 입력받은 단어의 문자열을 확인한다. - 스택 구조를 이용하여 스택의 마지막 요소와 현재 탐색하고 있는 요소가 같으면 아치형이 되므로 스택의 마지막 요소를 팝해준다. - 그렇지 않다면 스택에 추가한다. - 반복문을 끝내구 스택의 길이가 1이면 아치형으로 모두 연결된 것으로 좋은 단어이다. - 스택에 길이가 1인 이유는 처음에 스택에 0을 넣었기 때문이다. 코드 import sys n = int(sy..

문제 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 알고리즘 - collections 모듈에 Counter 클래스를 사용한다. - 람다 정렬을 통해 개수를 내림차순으로, 이름을 오름차순으로 정렬한다. 코드 import sys from collections import Counter n = int(sys.stdin.readline()) temp = [] for _ in range(n): temp.append(str(sys.stdin.readline().strip())) res = Counter(temp..

문제 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 알고리즘 - pop(), append() 함수를 잘 이용하여 문제를 수행한다. - 카드를 버리고 난 후에 카드가 없다면 반복문을 멈출 수 있게 코드를 작성한다. 코드 import sys n = int(sys.stdin.readline()) card = [i for i in range(1, n + 1)] res = [] while True: res.append(card.pop(0)) # 제일 위에 있는 카드를 바닥에 버린다. if not card: # 위에서..

문제 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 알고리즘 - 반복문을 통해 출입 기록을 확인한다. - 방문자의 출퇴근 여부를 통해 방문자를 추가하거나 제거한다. - 사전 순의 역순으로 정렬하여 출력한다. 코드 import sys n = int(sys.stdin.readline()) temp = dict() # 딕셔너리 형 # 반복문을 통해 출입 기록울 확인한다. for _ in range(n): a, b = map(str, sys.stdin.readline().sp..

문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 알고리즘 - union-find 알고리즘을 통해 문제를 수행한다. - 친구의 부모 노드를 찾고 부모 노드의 탐색 횟수를 출력한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # a가 속한 집합과 b가 속한 집합 합치기 def union(x, y): # 각 친구의 부모 노드를 찾는다. x = find(x) y = find(y) # 부모 노드가 같으면 리턴 if x == y: return else: # 부모 노드..