조준장 개발자 생존기

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 - 백 트래킹을 통해 문제를 수행한다. - 암호를 만들었다면 암호에 모음과 자음의 개수를 체크한다. - 모음이 1개 이상, 자음이 2개 이상이라면 암호를 잘 만든 것으로 출력한다. - 암호는 반복문과 백 트래킹을 통해 만든다. 코드 import sys def back_tracking(cnt, idx): # 암호를 만들었을 때 if cnt == l: # 모음, 자음 체크 vo, co = 0, 0 for i in range(l): if answer[i] i..

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 - 백 트래킹과 bfs 탐색을 한 번에 수행한다. - 벽을 3개 세울 때까지 백 트래킹 후 3개 세웠다면 바이러스 위치에서 bfs 탐색을 한다. - 탐색 후 안전한 위치를 카운트하여 최댓값을 출력한다. 코드 pypy3 통과 import sys from collections import deque import copy # 백 트래킹 def back_tracking(cnt): global answer # 벽을 3개 세웠다면 if cnt == 3: answer = m..

문제 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 알고리즘 - 3진수로 확인하는 방법과 유사하게 문제를 수행한다. - 다른 점이라면 3으로 나누어 떨어졌을 때 0으로 자리 이동을 안 해주기 위해 n-1을 해준다.(0이 없기 때문이다.) 코드 def solution(n): answer = '' numbers = ['4', '1', '2'] # 3진수로 확인 => 다른점은 3으로 나누어 떨어질 때 n - 1를 해준다.(0이 없기 때문.) while n > 0: n, mod = divmod(n, 3) # 몫, 나머지 answer = numbers[mod] + answer # 나머지가 0이라면 3으로 나누어 떨어 진 것으로 자릿수 이동 x if mod == 0: n -= 1 retur..

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 dp[idx] 위치에 수를 카운트한다. - 10001번 반복해서 받은 수에 개수를 출력한다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 10001 # 반복문을 통해 dp[idx] 위치에 수를 카운트한다. for _ in range(n): dp[int(sys.stdin.readline())] += 1 # 10001번 반복해서 받은 수에 개수를 출력한다. for i in range(1, 10001):..

문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 알고리즘 - 반복문을 통해 점프를 확인한다. - 점프로 갈 수 있는 칸을 확인하여 점프한 칸에 점프 횟수에 값을 최솟값으로 초기화한다. - 마지막 칸에 점프 횟수가 바뀌었다면 점프 횟수를 출력하고 아니라면 -1을 출력한다. 코드 # 10:25 => 10:51 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) dp = [sys.maxsize..

문제 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 알고리즘 - 반복문을 통해 입력 값을 확인한다. - 입력 값의 따라서 uid 값의 닉네임을 추가/변경하고 temp에 상태와 uid 값을 추가한다. - 반복문을 통해 상태와 uid의 닉네임을 answer에 추가하여 출력한다. 코드 # 01:12 => 01:27 def solution(record): answer = [] temp = [] uid = {} # 반복문을 통해 입력 값을 확인 for i in record: i = i.split(" ") # 입력 값..

문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 알고리즘 - 반복문을 통해 문자열 압축 길이를 변경한다. - 반복문을 통해 문자열을 확인한다. - 문자열을 압축하여 값을 비교한다. - 값이 같으면 cnt를 카운트한다. - 값이 다르다면 cnt에 따라 res에 문자열을 추가한다. - 문자열을 추가했다면 문자열 압축 길이를 새롭게 초기화한다. - 반복문이 끝나면 문자열 압축 길이가 최소인지 비교한다. 코드 # 16:20 => 17:18 def solution(s): answer = len(s) # 반..

문제 코딩테스트 연습 - 방문 길이 programmers.co.kr 알고리즘 - 반복문을 통해 명령어를 수행한다. - 이동해야 하는 좌표가 범위 내에 있다면 명령어를 수행한다. - 현재 위치와 이동 후 위치, 이동 후 위치와 현재 위치를 answer에 추가한다. - answer는 set()의 자료구조를 갖고 있어 중복을 제거한다. - 명령어를 다 수행하고 answer를 2로 나눴을 때 몫을 출력한다. 코드 # 11:30 => 12:01 def solution(dirs): answer = set() # set()을 통해 중복을 제거 d = {"U" : [1, 0], "D" : [-1, 0], "R" : [0, 1], "L" : [0, -1]} x, y = 0, 0 # 반복문을 통해 명령어를 수행 for i..

문제 코딩테스트 연습 - 스킬트리 programmers.co.kr 알고리즘 - 반복문을 통해 스킬 트리와 스킬을 확인한다. - 스킬 중에 선행 스킬이 있다면 temp에 저장, 이미 있다면 저장하지 않는다. - temp와 선행 스킬을 비교 후 카운트한다. - 카운트 한 값을 출력한다. 코드 # 10:51 => 11:09 def solution(skill, skill_trees): answer = 0 # 반복문을 통해 스킬 트리를 확인 for i in skill_trees: temp = [] # 반복문을 통해 스킬 확인 for j in i: # 스킬이 선행 스킬이라면 temp에 저장, 이미 있다면 저장하지 않는다. if j in skill and j not in temp: temp.append(j) # te..

문제 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 규칙을 찾아보면 4부터 dp[n] = dp[n-3]+dp[n-2]+dp[n-1] 이라는 점화식을 구할 수 있다. - 1000001가지의 dp 값을 구하고 문제에 원하는 위치에 값을 출력한다. 코드 import sys t = int(sys.stdin.readline()) n = [int(sys.stdin.readline()) for _ in range(t)] dp = [0] * 1000001 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in ra..