문제요약 ( 22868. 산책 (small) ) 22868번: 산책 (small) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 풀이를 위한 부연 설명 최단 경로를 확인해야하므로 BFS를 사용해야한다. 인접 행렬을 이용해 그래프 형태로 바꾼다 S에서 E로 갔다가, 경로가 겹치지 않게 E에서 S로 돌아와야한다. 구글링 해보니 이 방법이 여러가지가 있다. BFS 함수를 따로 구현 매개변수로 S_TO_E인지 E_TO_S인지 구분 필자는 구글링해서 나오지 않던(아마...), 문자열로 지나왔던 경로를 저장하고 새로운 visited ..

문제요약 (19637. IF문 좀 대신 써줘) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 풀이를 위한 부연 설명 두 가지 방법으로 풀 수 있는 문제이기에 나눠서 작성하겠다. 이분탐색 각 칭호의 이름과 기준을 받아온다. 이때 중복되지 않는 값을 받아오도록 처리를 해야한다. 이후 입력받은 캐릭터의 힘이 기준치 어디에 포함되는지 확인한다. 인덱스 값을 기준으로 하여 이분탐색을 진행한다. bisect 이용 훨씬 간결하고 빠른 코드이다. bisect 이진 탐색을 쉽게 구현..

문제요약 (2343번. 기타 레슨) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이를 위한 부연 설명 블루레이 크기가 모두 같고, 녹화 순서가 바뀌지 않아야한다를 통해 이진 탐색임을 알아야함 강의 순서대로 차례로 저장하면서 해당하는 크기의 블루레이로 모든 강의가 저장되는지 확인하는 방식 가능하다면 블루레이의 크기를 줄이고, 불가능하다면 블루레이의 크기를 늘임. 이진 탐색의 시작은 레슨의 가장 큰 강의 길이로 하여 각각 담는 경우와 끝은 모든 강의의 합으로 하여 모든 강의를 한 번에 담는 경우를 고려 해당하는 크..

문제요약 (13164번. 행복 유치원) 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 풀이를 위한 부연 설명 아이디어를 떠올리는 것이 중요한 문제이다. 먼저 유치원생들 간의 키 차이를 diff에 저장한다. 인덱스 에러에 주의한다. n-k개의 diff 값을 더하면 구하려는 값이 나온다. 그리디와 정렬에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [코테 알고리즘] 그리디 / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직..

문제요약 (1654. 랜선 자르기) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이를 위한 부연 설명 이분탐색을 이용하는 정석적인 문제이다. 원하는 개수의 랜선이 나왔다면 해당하는 길이보다 더 작게 잘라도 원하는 개수만큼의 랜선이 나오는지 탐색하고 아니라면 자르려는 길이를 수정한다. 코드 import sys input = sys.stdin.readline k, n = map(int, input().split()) lines = [int(input()) for _ in rang..

문제요약 (2800. 괄호 제거) 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이를 위한 부연 설명 괄호의 위치를 스택을 통해 구현한다 각 괄호의 쌍을 뽑아내야하므로 스택을 사용한다. 괄호 쌍을 "포함한다/포함하지 않는다" 이 두 가지 경우에 대한 모든 수를 알아보기 위해 조합을 사용한다. 파이썬 itertools의 combinations를 이용해 경우의 수를 구한다. 여러 가지 같은 경우가 나올 수 있으므로 set()으로 답을 넣는다. 조합에 대한 자세한 개념 설명과 연..

문제요약 (1918. 후위표기식) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이를 위한 부연 설명 연산자의 우선순위를 기준으로 스택에 쌓아야한다. 괄호 처리에 유의해야한다. 스택에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [구버전] [Python] 03. 스택과 큐 📌 스택이란? 📚 스택 알아보기 📃 스택 (stack) 데이터를 임시 저장할 때 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식 푸시(push) : 스택에 데이터를 넣는 작업 팝(pop) ..

문제요약 (16113. 시그널) 1. 시그널은 "."과 "#"으로 이루어져 있다. 2. 시그널을 해독한 결과에는 반드시 숫자가 1개 이상 있다. 3. 시그널에 등장하는 모든 "#"은 올바른 숫자 패턴에 포함되어 있다. 4. 숫자와 숫자 사이에는 1열 이상의 공백이 있다. 여기서 공백은, 열의 성분이 모두 "."인 열을 의미한다. 5. 0부터 9는 아래와 같이 나타난다. 역시 "#"을 검은색, "."을 흰색으로 표시했다. 여러가지 예제들을 넣어보면서 구현이 맞는지 확인해봐야한다. 스스로 반례를 찾는게 중요하지만 시간이 없거나 정말 모르겠다면 (https://www.acmicpc.net/board/view/64923) 이 링크를 참고하길 바란다. 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자..

문제요약 (1931. 회의실 배정) 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 그리디 알고리즘을 사용해야한다는 생각을 반드시 해야한다. 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이를 위한 부연 설명 회의..

문제요약 (11286.절대값 힙) 배열에서 절댓값이 가장 작은 값을 출력한다. 절대값이 같은 경우에는 가장 작은 수(음수)를 먼저 출력한다. 파이썬에서 절댓값을 구하는 함수는 abs()이다. 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이를 위한 부연 설명 우선순위 큐 ( Priority Queue ) 원소들의 우선순위별로 정렬한다. 원소의 우선순위를 설정하여 값을 추가하는 put과, 값을 반환하는 get이 있습니다. 우선순위 큐를 이용하면 문제에서 해당하는 값을 넣을 수 있습니다. ..