![]()
문제https://www.acmicpc.net/problem/7662 풀이1. 단순히 deque과 sort(O(N * log N))를 이용하여 이중 우선순위 큐를 모사할 시 시간 초과 발생2. heapq는 O(logN)으로 시간 초과 발생 X, 하지만 최대 힙, 최소 힙을 유지하면서 max, min 제거와 동기화를 같이 해줘야 함.3. default dict 사용 - I로 들어온 val에 대해 관리. D로 삭제 시 반영. >> 최대 힙, 최소 힙 동기화 - idx로 구분하여 관리하기에 중복 값에 대한 관리 가능.from heapq import heappush, heappopfrom collections import defaultdictinput = __import__('sys').stdin.re..
https://www.acmicpc.net/problem/11279문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열..
문제N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.127915513811196211026311648142835255220324149이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.입력첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.출력첫째 줄에 N번째 큰 수를 출력한다.코드import heapqN = int(input())heap = []for _ in range(N): row = list(map(i..
https://www.acmicpc.net/problem/4435문제중간계에 전쟁이 일어나려고 한다. 간달프는 사우론에 대항하기 위한 군대를 소집했고, 여러 종족이 이 군대에 가담했다. 전쟁을 시작하기 전에 간달프는 각 종족에 점수를 매겼다.간달프의 군대의 각 종족의 점수는 다음과 같다.호빗 - 1인간 - 2엘프 - 3드워프 - 3독수리 - 4마법사 - 10사우론의 군대의 점수는 다음과 같다.오크 - 1인간 - 2워그(늑대) - 2고블린 - 2우럭하이 - 3트롤 - 5마법사 - 10중간계는 매우 신비한 곳이어서 각 전투의 승리는 날씨, 장소, 용맹에 영향을 받지 않는다. 전투에 참여한 각 종족의 점수를 합한 뒤, 큰 쪽이 이긴다.전투에 참여한 종족의 수가 주어졌을 때, 어느 쪽이 이기는지 구하는 프로그램..
![]()
https://www.acmicpc.net/problem/10799문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.이러한..
![]()
문제https://www.acmicpc.net/problem/33848 Algorithm해당 스택의 3번 쿼리, 3 j: 최근 j개의 1번 또는 2번 쿼리를 취소한다. 취소할 수 있는 1번 또는 2번 쿼리가 j개 이상인 경우에만 주어진다. 를 수행하기 위해 이전 쿼리의 작동을 기억해야 할 필요가 있다.그렇기에 메인 스택, 임시 스택을 두어 메인 스택에는 위의 쿼리를 진행한다. 임시 스택에는 1번 쿼리 수행시 0을 집어넣고, 2번 쿼리 수행시 메인 스택에서 제거된 수를 집어 넣는다.이후에 3번 쿼리가 들어오면 j번 만큼 임시 스택에서 pop연산을 진행하여 값이 0이면 메인 스택에서 제거, 값이 0이 아니면 해당 수를 메인 스택에 집어넣는 연산을 해주면 된다. Codeimport sysinput = sys..
문제 https://www.acmicpc.net/problem/1700 문제기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,키보드헤어드라이기핸드폰 충전기디지털 카메라 충전기키보드헤어드라이기키보드, 헤어드라이기,..
문제 https://www.acmicpc.net/problem/1926 Algorithm1. dfs 알고리즘을 이용해 한 그림 즉 1이 이어져있는 것을 찾는다.2. 찾는 과정에서 정수 e를 전역변수로 두고 그림의 크기를 기록해 가장 큰 그림의 크기를 구한다.3. dfs 알고리즘을 통해 그림을 하나 찾을 때 마다 정수 cnt를 활용해 그림의 개수를 구한다. Codeimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 8)def dfs(x, y): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] global e for i in range(4): nx = x + dx[i] ny =..
![]()
문제 & 링크https://www.acmicpc.net/problem/1294 풀이1. 각 문자열을 원하는 대로 쪼갤 수 있기에, 각 문자열(string)의 맨 앞 문자(char) 끼리 비교하여 사전순으로 가장 앞서는 문자 하나를 가져온다.2. 사전순으로 가장 앞서는 문자가 여러 문자열에 있을 경우 그 다음인 두 번째 문자도 고려해야 한다. - 문자열을 쪼개되, 조각의 순서는 유지해야 하는 조건 - 문제의 출력 조건을 만족하기 위해서 뒤의 문자도 고려하여 해당 문자열의 맨 앞 문자 추출 ex) CB, CA이렇게 두 문자열이 있을 경우 맨 앞 문자는 C로 사전순으로 같다. 그러면 두 번째 문자인 A와 B를 비교하여 두 번째 문자열에서 맨 앞 문자를 추출해야 한다. (이 경우 최종 결과 CACB, 만약..
![]()
문제 & 링크https://www.acmicpc.net/problem/13911 풀이1. 음의 가중치가 없는 그래프에서 최단 거리를 구해야 하기에 다익스트라 알고리즘을 사용한다.2. x세권인지 아닌지 판단하는 값이 주어지기에, 다익스트라 알고리즘에서 우선순위 큐에 넣을 때 이 값을 고려한다.3. 모든 집에서 다익스트라를 수행 할 경우 x세권이 아님에도 탐색 대상이 되는 경우가 있기에 비효율적이다.4. 맥도날드 or 스타벅스에서 다익스트라를 수행하여 x세권인 집만 탐색을 한다.5. 모든 맥도날드 or 스타벅스에서 다익스트라를 한 번씩 수행하면, 최악의 경우 9,999개의 노드에 대한 다익스트라 수행으로 시간 초과가 나게 된다. 6. 가상 노드라는 개념을 추가하여 모든 맥도날드의 시작점을 하나로 묶고, 모든..
![]()
문제 & 링크https://www.acmicpc.net/problem/1422 풀이1. K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다.2. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 중 큰 수를 N - K 만큼 붙여야 한다.3. 숫자를 string으로 바꾸어 사전 순으로 가장 앞서는 수를 구한다. 숫자를 그냥 넣게 될 경우, 아래와 같은 예시가 존재할 수 있다. ex) K = { 31, 34 } -> 사전 순으로 정렬: 34, 31 -> 결과: 3431 (기댓값: 3431) ex) K = { 3, 34 } -> 사전 순으로 정렬: 34, 3 -> 결과: 343 (기댓값: 343) ..
문제 https://www.acmicpc.net/problem/5972문제농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]..
