조준장 개발자 생존기

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 - 0 - 1 bfs 탐색을 통해 문제를 수행한다. - 동생의 위치에 도달했다면 리턴하고 도달하지 못했다면 이동한다. - 이동은 3가지 방법을 반복문을 통해 수행한다. - 이동하는 곳이 범위 내에 있고 이동하지 않은 곳이라면 이동한다. - 순간이동이라면 이전에 초로 갱신하고 appendleft()로 탐색한다. - 순간이동이 아니라면 이전에 초에 +1 해주고 append()로 탐색한다. - 위 탐색과정이 다른 것이 0..

문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 알고리즘 - 0번째 idx를 기준으로 오름차순 정렬을 한다. - 정렬된 전깃줄에 가장 길게 증가하는 부분 수열을 찾는다. - 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다. - 길이를 구할 때 i번의 수와 그전에 수들을 비교한다. - 0번째 idx를 기준으로 오름차순 정렬을 했기 때문에 1번째 idx를 기준으로 수들을 비교한다. - 이때 가장 길게 증가하는 부분 수열이 겹치지 않는 전깃줄이므로 전체에서 빼준 값을 출력한다. 코드 import sys n ..

문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 알고리즘 - 반복문을 통해 미로를 확인한다. - 현재 좌표에 올 수 있는 모든 경우의 수의 최댓값과 현재 좌표에 사탕 수를 더한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] dp = [[0 for _ in range(m + 1)] for _ in ra..

문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 알고리즘 - 반복문을 통해 이동해야 하는 채널로 가기 위한 방법을 확인한다. - 반복문을 통해 채널로 이동하기 위해 눌러야 하는 번호가 고장이 났는지 확인하고 고장이 났다면 그 번호를 눌러서는 이동할 수 없다. - 채널로 이동 가능하다면 원래 cnt, 채널을 누른 개수와 +/- 를 누른 개수를 더한 값을 비교하여 cnt에 담는다. - 마지막 cnt 값이 채널로 가기 위한 최소 개수가 된다. 코드 import sys n = int(sys.st..

문제 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 알고리즘 - 재귀 함수를 통해 제일 작은 알파벳의 앞 배열과 뒷 배열을 확인한다. - answer에 제일 작은 알파벳 위치에 제일 작은 알파벳을 입력하고 "".Join()을 통해 출력한다. 코드 import sys def solution(s, start): global answer # 배열이 없으면 리턴 if not s: return # 현재 배열의 제일 작은 알파벳을 찾는다. target = min(s) idx = s.index(target) # ..

문제 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 알고리즘 - 반복문을 통해 시간과 닉네임을 입력받는다. - 개총 시작시간보다 일찍 들어온 사람을 dic에 입력한다. - 개총 종료시간과 스트리밍 종료시간 사이에 들어온 사람을 확인하여 개총 시작시간보다 일찍 들어온 사람이라면 answer에 입력한다. - answer에 길이를 출력한다. 코드 import sys s, e, q = map(str, sys.stdin.readline().split()) dic = {} answe..

문제 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 그룹을 확인한다. - 0으로만 이루어진 그룹이 있다면 idx에 저장한다. - 0으로만 이루어지지 않은 그룹은 0을 추가한다. - 0으로만 이루어진 그룹은 반복문을 통해 IPv6의 길이가 8이 될 때까지 "0000"을 추가한다. 코드 import sys IPv6 = list(map(str, sys.stdin.readline().strip("\n").split(":"))) idx = [] # 반복문을 통해 각 그룹을 확인 for i in range(len(IPv6)):..

문제 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net 알고리즘 - 반복문을 통해 문자를 확인한다. - 문자가 "("라면 stack에 추가한다. - 문자가 ")"라면 while문과 .pop()을 통해 stack의 괄호 안에 있는 수를 모두 더하여 stack에 추가한다. - 문자가 원자라면 stack 수를 추가한다. - 문자가 괄호도 아니고 원자도 아니라면 숫자이므로 stack에 마지막 숫자를 입력받은 숫자로 곱한다. - 위 4가지 조건을 통해 반복하여 stack에 값을 추가해준 뒤 stack을 모두 더하여 출력한다. 코드 import sy..

문제 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 알고리즘 - 문자열 길이가 n일 때와 n-1일 때 회문이 되는지 확인한다. - 문자열의 길이가 n일 때 회문이면서, n-1일 때도 회문이라면 그 문자열은 하나의 문자로 연속되어 있는 문자열인 회문이다. - 문자열이 짝수인지 홀수인지, 길이가 n일 때인지 n-1일 때인지에 따라서 왼쪽 문자열과 오른쪽 문자열을 나눈다. - 나눈 문자열이 회문인지 판단하여 문제를 수행한다. 코드 import sys # 회문인지 판단 def so..

문제 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 알고리즘 - 백 트래킹을 통해 완성된 문자열로 시작 문자열을 만들 수 있는지 확인한다. - 백 트래킹은 2가지 조건을 통해 수행한다. 코드 import sys # 백 트래킹을 통해 완성된 문자열로 시작 문자열을 만들 수 있는지 확인 def solution(c): global flag if len(c) == len(s): if c == s: flag = True return if c[0] == "B": c.reverse..