알고리즘 문제 풀이45 [백준 1966번] 프린터 큐 - 파이썬 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 💡문제 분석 요약 가장 중요한 문서를 먼저 프린터하고, 현재 문서보다 더 중요한 문서가 있을 경우 현재 문서를 맨 뒤 순서로 보낸다. 내가 원하는 문서는 몇번째로 출력되는가? 💡알고리즘 설계 1. 현재 문서 리스트에서 가장 중요도가 높은 문서의 중요도를 구한다. 2. 현재 문서보다 더 중요한 문서가 있을 경우, 현재 문서를 제일 뒷 순서로 보낸다. 3. 현재 문서가 가장 중요한 문서일 경우, 문서를 .. 2024. 3. 23. [백준 5397번] 키로거 - 파이썬 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 💡문제 분석 요약 글자를 입력받고, 가 입력될 경우엔 커서를 오른쪽으로 이동하여 글자를 입력한다. -가 입력될 경우 커서 왼쪽의 글자를 삭제한다. 💡알고리즘 설계 스택과 연결리스트로 풀 수 있는 문제이다. 커서를 index로 두고, list.insert(index, c)로 해당 위치에 글자를 삽입하는 방법은 insert()의 시간복잡도가 O(N)이고, 문자열의 최대 길이가 백만이므로 시간초.. 2024. 3. 23. [백준 2630번] 색종이 만들기 - 파이썬 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.www.acmicpc.net 💡문제 분석 요약아래와 같이 정사각형 모양으로 나누어 진 종이가 있을 때, 파란색 종이의 개수와 흰색 종이의 개수를 구하여라. 💡알고리즘 설계현재 칸의 종이 색과 첫번째 칸의 종이의 색이 다르면 현재 종이를 4등분으로 자르고, 다시 탐색한다.현재 종이에 있는 모든 칸이 색깔이 같다면, 그 색의 count를 하나 더한다.1. 종이의 색 정보를 입력받는다2. cut 함수를 .. 2024. 3. 16. [백준 20920번] 영단어 암기는 괴로워 - 파이썬 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단www.acmicpc.net 💡문제 분석 요약영단어를 입력받고, 자주 입력받은 횟수, 단어 길이, 사전순으로 정렬하여 출력한다. 💡알고리즘 설계1. 해시를 이용하여 key에 단어를, value에 단어가 입력된 횟수를 하나씩 늘리면서 저장한다.- hash에 입력받은 단어가 있는지 체크하고, 없으면 hash[word]=1, 있으면 hash[word]+=1로 갯수.. 2024. 3. 16. [백준 1913번] 달팽이 - 파이썬 https://www.acmicpc.net/problem/1913 💡문제 분석 요약 구현 문제이다. 달팽이가 배열의 가운데서 시작해, 시계방향으로 숫자를 1씩 키우며 움직인다. 최종적으로 완성된 배열과 같이 입력받은 숫자의 좌표를 출력하라. 💡알고리즘 설계 1. 달팽이가 지나갈 배열을 0으로 초기화한다. 2. 달팽이가 (0,0) 위치에서 N*N을 저장하며 시작한다. 3. 숫자를 하나씩 줄이며, 다음 위치가 배열의 안이며, 다음 위치의 배열에 0이 저장되어 있다면 그 위치로 이동하여 줄어든 숫자를 저장한다. 4. 다음 위치가 배열 밖이거나 이미 다른 숫자로 채워져 있다면 방향을 바꾸고, 다시 이동한다. 방향은 시계 반대 방향으로 변경한다. 💡코드 import sys input = sys.stdin.read.. 2024. 3. 9. [백준 18429번] 근손실 - 파이썬 https://www.acmicpc.net/problem/18429💡문제 분석 요약매일 중량이 K만큼 줄어들 때, 매일 다른 운동 키트를 사용하여 중량을 500 이상으로 유지시킬 수 있는 경우의 수를 구하여라. 💡알고리즘 설계1. 운동키트에 들어있는 운동기구로 늘릴 수 있는 중량과 매일 줄어드는 중량을 입력받는다.2. dfs를 이용해 가능한 운동 기구를 다양한 순서로 이용한다.3. 중량이 500 이하인 경우 탐색을 중단한다. 💡코드import sysinput = sys.stdin.readlineN, K=map(int, input().split())kit=list(map(int, input().split()))visited=[False]*(N)weight=500result=0def search(cou.. 2024. 3. 9. [백준 13305번] 주유소 - 파이썬 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 💡문제 분석 요약 N개의 도시가 있고, 도시 사이에는 거리가 있다. 각 도시에는 주유소마다 기름의 가격이 다른데, 가장 싸게 기름을 충전하여 첫 도시에서 마지막 도시까지 갔을 때의 기름 값을 구하여라. 💡알고리즘 설계 1. 첫 도시에서 다음 도시까지 가기 위한 기름을 구매한다. 2. 첫 도시의 기름값을 가장 싼 기름값으로 저장한다. 3. 다음 도시의 기름 값과 이전에 저장된 가장 싼.. 2024. 3. 2. [백준 7568번] 덩치 - 파이썬 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 💡문제 분석 요약 몸무게와 키를 입력받고, 덩치 등수를 출력한다. 몸무게는 더 무거운데 키는 작거나, 몸무게는 가벼운데 키는 큰 경우는 덩치를 가릴 수 없으므로, 같은 등수로 출력한다. 💡알고리즘 설계 1. 사람들의 몸무게와 키 정보를 입력받는다. 2. 한 사람씩, 이 사람보다 키와 몸무게가 둘 다 큰 사람이 몇명인지 구하여 rank 리스트에 추가한다. 💡코드 import sys in.. 2024. 3. 2. [백준 2594번] 놀이공원 - 파이썬 https://www.acmicpc.net/problem/2594 2594번: 놀이공원 첫째 줄에 놀이기구의 개수 N이 주어진다. 이어 N줄에 걸쳐 각 놀이기구의 운행시작 시각과 종료 시각이 빈 칸을 사이에 두고 주어진다. 시각은 시간단위 두 자리, 분 단위 두 자리로 구성되며 오 www.acmicpc.net 💡문제 분석 요약 놀이공원의 오픈 시간, 놀이기구 운행 시간, 마감 시간 사이 가장 쉬는 시간이 큰 시간을 구하라. 놀이기구의 운행 10분 전, 운행 10분 후까지는 쉴 수 없으며, 놀이기구의 운행 시간이 겹치는 경우에도 쉴 수 없다. 💡알고리즘 설계 1. 타임 리스트에 놀이공원의 오픈 시간과 놀이기구 운행 시작 시간, 종료 시간, 놀이공원 마감 시간을 타임스탬프 형식으로 변환하여 저장한다. 2. .. 2024. 2. 23. 이전 1 2 3 4 5 다음
