DonHurry

📖 문제 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 🔎 풀이 슬라이딩 윈도우를 활용하는 문제입니다. 먼저 주어진 기간인 X 크기의 윈도우를 생성합니다. 이후 윈도우를 한 칸씩 오른쪽으로 이동하면서 각 윈도우의 합을 계산해줍니다. 매번 sum 함수로 계산시 시간비용이 O(n)이므로, 이전 합에서 맨 앞의 원소를 빼주고, 새로 추가되는 원소를 더해주는 식으로 계산합니다. 💻 코드 N, X = map(int, input().split()) # 방문자 수를 담는 리스트 visited = [int(x) fo..

📖 문제 1100번: 하얀 칸 체스판은 8×8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 🔎 풀이 문자열 관련 구현 문제입니다. 조건문을 어떻게 구현하느냐에 따라 코드의 가독성이 달라질 수 있습니다. 💻 코드 cnt = 0 for i in range(8): row = input() for j in range(8): # 짝수 행(0부터 시작)의 짝수 번째는 하얀 칸이므로 이에 맞추어 조건문 생성 if not (j - (i%2)) % 2 and row[j] == 'F': cnt += 1 print(cnt)

📖 문제 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 🔎 풀이 큐를 활용하는 문제입니다. deque를 선언하고, popleft 함수를 이용하면 0번째 인덱스의 원소를 O(1)에 추출할 수 있습니다. 앞에서부터 추출하면서, 해당 원소가 K번째라면 결과 리스트에 추가해줍니다. 아니라면 기존 리스트에 다시 맨 뒤로 추가합니다. popleft 함수의 비용이 O(1)이더라도, 결과적으로는 전부 탐색해야하기 때문에 생각보다 시간이 오래 걸리는 문제였습니다. 오히려 pop(i)를 이용해 원하는 K번째 요소를 우선적으로 뽑는 것이 더 효율이 좋습니다. 아래 코드는 큐를 이용하였습니다. 💻 코드 import..

📖 문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 🔎 풀이 유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 모든 정점들을 연결하면서, 가중치의 합을 최소로 만들기 위해서는 사이클을 만들지 않아야 합니다. 이는 크루스칼 알고리즘으로 잘 알려져 있습니다. 풀이 방법은 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면서 각 노드를 연결하는 것입니다. 이때 사이클을 판단하는 과정은 유니온파인드를 이용합니다. 💻 코드 import sys input =..

📖 문제 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 🔎 풀이 어떻게 푸느냐에 따라 코드의 간결성이 크게 차이나는 문제입니다. 주어진 문자열의 크기가 크지 않기 때문에 count 함수를 이용하여 크로아티아 알파벳들을 하나씩 세줍니다. 이때 전체 문자열의 합을 구해놓고, 크로아티아 알파벳 개수만큼 빼주는 식으로 구현합니다. (크로아티아 알파벳들은 두 자리씩 차지하므로) 'dz='는 '=' 에서 한 번 더 걸러지므로 총 2번을 빼, 알맞은 결과가 출력됩니다. 💻 코드 ar..

📖 문제 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 🔎 풀이 우선순위 큐를 활용하는 문제입니다. 특정한 조건에 따라 우선순위가 가장 높은 요소를 추출합니다. 파이썬의 heapq 모듈은 최소 힙만을 지원합니다. 하지만 음수 형태로 저장한다면, 최대 힙처럼 활용이 가능합니다. 💻 코드 import sys import heapq input = sys.stdin.readline # 선물을 담을 배열 giftbox = [] for _ in range(int(input())): a = list(map(int, inpu..

📖 문제 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 🔎 풀이 큐를 이용하여 푸는 문제입니다. 초기 리스트에는 다리 위 공간을 모두 0으로 채워줍니다. 이때 매번 리스트 합을 계산하여 무게를 구하면 비효율적입니다. 때문에 따로 변수를 생성하여 트럭이 다리 위로 진입하면 트럭의 무게를 더해주고, 나가면 빼줍니다. 만약 트럭이 더 이상 다리에 진입하지 못하는 경우에는 리스트에 0을 추가해줍니다. 💻 코드 import sys import collections inp..

📖 문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 🔎 풀이 연결리스트 혹은 스택을 이용하여 푸는 문제입니다. 아래 코드는 스택을 활용하였습니다. 우선, 현재 위치를 기준으로 왼쪽과 오른쪽으로 나누어 글자를 담을 리스트를 생성해줍니다. 이후 커서의 위치가 이동할 때마다 리스트를 갱신해줍니다. 예를 들어, 커서가 오른쪽으로 움직이기 위해서는 오른쪽에 있는 글자를 왼쪽 리스트로 옮겨주어야 합니다. 이때 오른쪽 리스트에서는 첫번째 원소를 뽑아오게 되는데, 리스트는 pop(0)를 사용 시 O(n)의 비용..