archive

✏️ 문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net ✏️ 풀이 1번 ~ 5번 과정을 블록그룹이 없을 때까지 수행한다. 은근히 자잘한 조건이 많기 때문에 1번~5번 구현하면서 코드 길어지기 전에 중간중간 정확하게 구현했는지 테스트해야 풀기가 편할 것 같다. 각 좌표에 대해서 BFS 돌면서 최대 크기의 블록그룹을 구한다. 이 때 블록그룹에 일반 블록이 무조건포함되어야 하므로 일반 블록일때만 해당 동작을 수행한다. 격좌를 BFS로 돌면서..

✏️ 문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net ✏️ 풀이 케이스 분류해서 차근차근 풀면 되는 문제..인데 지문 대충 읽어서 중간 중간 빠트린게 너무 많았던 문제 좋아하는 학생 수, 공백 수, 행/열을 차례로 비교해줘야 한다. 즉 2번 조건이 1번 조건에 종속적이기 때문에 이를 주의해야한다. max_like이 갱신되었을 때 max_blank를 함께 갱신해준 것도 그 이유 때문.. (해당 max_like끼리 다시 2번 조건 ..

✏️ 문제 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr ✏️ 풀이 배열을 순차적으로 탐색하면서 더하거나/빼는 두 가지의 경우의 수가 있다. 즉, 트리 구조로 생각할 수 있다. 이 트리를 DFS로 완전 탐색한다. DFS로 각 수를 더하거나 빼서 경우를 재귀적으로 탐색하고, 마지막 depth에 도착하면 target과 같은지 검사한다. ✏️ 코드 count = 0 def dfs(number, depth, target, numbers): global count..

✏️ 문제 코딩테스트 연습 - 위장 programmers.co.kr ✏️ 풀이 종류를 Key, 이름 배열을 Value로 딕셔너리에 저장한다. 그 후, 고를 수 있는 모든 경우의 수를 계산한다. ✏️ 코드 from collections import defaultdict from itertools import combinations def solution(clothes): answer = 0 clothes_dict = defaultdict(list) for name, kind in clothes: clothes_dict[kind].append(name) keys = clothes_dict.keys() for n in range(1, len(clothes_dict)+1): for combi in combina..

✏️ 문제 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net ✏️ 풀이 이 문제는 딱봐도 DFS문제로 보이지만 단순하게 DFS + 완전탐색으로 풀이하면 시간초과가 난다. 경로와 관련해서 고민하다보면 최소 경로를 불필요하게 중복해서 탐색함을 알 수 있다. 따라서 해당 좌표에서의 최소 경로에 대해 Memorization이 필요하다. 따라서 일반적인 DFS로 풀이하되, 이미 해당 좌표에 대해 최소 경로가 구해져있다면 바로 return하도록 한다. ✏️ 코드 import sys sys.setrecursionl..

✏️ 문제 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr ✏️ 풀이 문제 분류가 Hash라는 것을 알고 풀어서, 처음부터 딕셔너리를 사용하는 방법으로 접근했다. phone_book의 모든 원소는 접두어 후보이므로 딕셔너리에 dict[접두어] = True 를 넣는다. 이후 다시 phone_book을 탐색한다. 이 때, 한 전화번호를 "한글자 ~ 길이-1" 만큼 잘라서 해당 값을 인덱스로 가지는 원소가 dict에 있는 지 살펴본다. 만약 있다면 접두어가 존재한다는 뜻이므로 바로 False를 리턴한다. dic..