archive

✏️ 문제 코딩테스트 연습 - 타겟 넘버 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..

✏️ 문제 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr ✏️ 풀이 조건 그대로 구현하는 문제이다. 배열 인덱싱만 주의하면 크게 어려울 것은 없지만 조건이 구구절절 써있다보니 처음엔 다소 이해하기가 어려웠다. 문자열을 3개씩 자르고 만약 옵션이 없는 경우 / 숫자가 10인 경우를 각각 예외처리 해주었다. ✏️ 코드 def solution(dartResult): total = [] cur = 0 while True: if cur == len(dartResult): break cmd = dartResult[cur:cur + 3] if cmd[0]=='1' and cmd[1]=='0': cmd = dartResult[cur:cur+4] if cmd[3:] != '*' and cmd[3..

✏️ 문제 코딩테스트 연습 - 위장 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..

해싱(Hashing)이란, 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업이다. 해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블이라고 한다. 이진 탐색 트리나 배열에 비해서 빠른 속도로 탐색/삽입/삭제가 가능하다. 해시함수를 사용하여 변환한 값을 index로 삼아, key-value를 저장한다. 기본연산으로는 Search, Insert, Delete가 있다. ● Direct Address Table 키 값을 주소(인덱스)로 사용하는 테이블이다. - 장점 탐색, 삽입, 삭제가 O(1)에 가능하다. - 한계점 최대 키 값을 알고 있어야 한다. 키 값이 퍼져있다면 메모리 낭비됨. ● Hash Table 해쉬함수를 이용해 특정 해쉬값을 알아내고 이를 인덱스로 변환하여 해당 위..