728x90
반응형

코딩테스트 20

[프로그래머스 / python / Level 2] 프렌즈4블록

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 시뮬레이션 문제이고 블럭을 떨어뜨리는 로직을 구현하는 것이 핵심이다. def solution(m, n, board): """블럭을 제거하는 함수""" def delete_blocks(m, n, board): # 모든 블럭에 대하여 삭제 조건 검사 deleted_blocks = set() for x in range(m - 1): for y in range(n - 1): point = board[x][y] if point == '': ..

[프로그래머스 / python / Level 3] 자물쇠와 열쇠

2020 KAKAO BLIND RECRUITMENT에 출제된 문제이다.구현, 완전탐색 문제이며 보드 확장 아이디어를 떠올리지 못한다면 풀기 까다로울 수 있는 문제이다. def solution(key, lock): """ 90도 회전시키는 함수 자물쇠가 열리는지 확인하는 함수 -> 열쇠를 보드에 적용 + 자물쇠값 모두 1인지 확인 + 열쇠를 보드에서 제거 확장된 보드를 만든다 자물쇠를 보드 중앙에 배치한다 열쇠를 4방향으로 회전시키며, 모든 가능한 위치에서 열기 시도한다 """ """키를 시계 방향으로 90도 회전하는 함수""" def rotate_key(key): return [list(row) for row in zip(..

[프로그래머스 / python / Level 3] 표 병합

2023 KAKAO BLIND RECRUITMENT에 출제된 문제로써, Union-Find가 사용되는 문제이다.Union-Find는 특정 그룹으로 묶고, 나누고, 그룹을 찾고 하는 것에 특화된 알고리즘이며, 표 병합같은 문제에 딱 맞는 알고리즘이다. def solution(commands): """ find: 대표를 찾는 함수, 재귀 구현 union: 병합 함수, merge 구현 """ """1차원 리스트 사용, 처음엔 자기 자신이 대표""" parent = [i for i in range(2601)] values = ["" for _ in range(2601)] # 처음엔 전부 빈 값 """좌표를 1차원 인덱스로 변환하는 함수""" def..

[프로그래머스 / python / Level 3] 양과 늑대

2022 KAKAO BLIND RECRUITMENT 출제 문제이다.BFS가 메인이고 상태 관리 로직이 필요하다. 카카오 문제들은 자료구조의 선택에 대해서도 많이 생각하게 된다. from collections import defaultdict, dequedef solution(info, edges): """인접 딕셔너리 만들기 (부모 -> 자식 단방향)""" graph = defaultdict(list) for parent, child in edges: graph[parent].append(child) """큐 기본값 설정""" # list는 삭제/탐색연산 느려서 set 쓴다 # 어차피 상태관리 visited로 하고 완전탐색이라 순서 상관없기에 s..

Algorithm/BFS 2025.06.06

[프로그래머스 / python / Level 3] 불량 사용자

2019 카카오 개발자 겨울 인턴십에 출제된 백트래킹 문제이다.주어지는 입력값의 크기가 크지 않아, 완전탐색으로도 풀린다고 들었지만 백트래킹이 정석인 문제라고 생각한다. def solution(user_id, banned_id): def is_match(user, banned_user): if len(user) != len(banned_user): return False for i in range(len(user)): if banned_user[i] != '*' and banned_user[i] != user[i]: return False return True ..

카테고리 없음 2025.06.05

[프로그래머스 / python / Level 2] 순위 검색

2021 KAKAO BLIND RECRUITMENT 출제 문제이다. Level 2이긴 한데 왜 2인지 전혀 모르겠고, 내가 느끼기엔 최소 Level 3이고 백준으로 치면 골드 4이상이 아닌가 싶다. 그냥 개인적 느낌이다. 단순 이분탐색만 사용되는 것이 아니라 해시, 조합, 문자열 파싱 등 다양한 알고리즘이 활용되고 구현요소도 많아서 실수할 부분이 매우 많고 복잡하다. 카카오 문제는 다 이런 거 같다. 하나의 알고리즘만 보는 게 아닌 이런저런 알고리즘을 조합하여 구현처럼 만들어내는 것.. 특히 초보자들에겐 더욱 어려운 것 같다. 나에게도 어렵고. from collections import defaultdictfrom itertools import productimport bisectdef solution(..

[프로그래머스 / python / Level 3] 주사위 고르기

2024 KAKAO WINTER INTERNSHIP 3번 문제이다. 아주 어려운 문제였다. 알고리즘 분류도 애매하다. 완전탐색, 조합, 구현, 이분탐색 정도일까?여러 가지 알고리즘이 복합적으로 쓰이고, 완전탐색 -> 이분탐색 아이디어를 떠올리기도 쉽지 않은 문제였다.개인적으로 Level 3 중에서 가장 어려운 편 아닌가 싶고, 3번 문제로 나온 건 난이도 조절 실패인 것 같다(개인적 의견).백준으로 치면 골드 1 정도 될 거 같은 느낌. from itertools import combinations, productdef binary_search(arr, target): """ 이분 탐색 정렬된 점수 합 리스트를 받아, target보다 작은 요소의 개수를 반환합니다. """ ..

[프로그래머스 / python / Level 2] 도넛과 막대 그래프

그래프 + 구현 문제이고, 2024 KAKAO WINTER INTERNSHIP 2번 문제이다.분명히 Level 2인데, 레벨보다 훨씬 어렵게 느껴진다. 백준으로 치면 최소 골드 이상 정도는 되지 않나 싶다. def solution(edges): """ 차수 0: 고립된 막대 그래프 차수 1: 막대 그래프의 양 끝 정점 차수 4: 8자 그래프의 중심점 입차수가 0이고 출차수가 2 이상: 생성된 정점 생성된 정점과 연결된 정점의 입차수를 1 빼줘야 한다. """ """각 정점의 입/출차수 계산""" in_degree = dict() out_degree = dict() for a, b in edges: in_d..

카테고리 없음 2025.06.01

[프로그래머스 / python / Level 1] 가장 많이 받은 선물

구현 문제이고, 2024 KAKAO WINTER INTERSHIP 1번으로 출제된 문제다.레벨 1이라 정말 가벼운 마음으로 도전했는데 역시 구현이라 그런지 신경쓸 게 꽤 많아서 어디부터 어떻게 구현해야 할지 갈피를 잡는게 어려웠지만, 풀고 나면 언제나 그랬듯 딱히 어렵지 않게 느껴진다. def solution(friends, gifts): # 더 많은 선물을 준 사람이, 다음 달에 선물을 하나 받는다 # 주고받은 수가 같다면, 선물 지수가 큰 사람이 하나 받는다 # 선물 지수: 자신이 친구들에게 준 선물 수 - 받은 선물 수 -> 즉 내가 더 많이 준 선물 수 # 주고받은 수와 선물 지수 모두 같다면 -> 다음 달에 선물 주고받지 않는다 # 가장 많이 받은 사..

[Baekjoon 6603 / Python / 실버2] 로또

기본적인 백트래킹 문제이다.주어진 집합에서 6개 숫자의 조합(순서가 다른 같은 숫자를 중복으로 간주)을 구해야 한다. # 실버2 -> 백트래킹import sysinput = sys.stdin.readlinedef back_tracking(depth, start, result):    # 6개의 숫자가 모이면 출력    if depth == 6:        print(*result)        return        for i in range(start, len(S)):        result.append(S[i])        back_tracking(depth + 1, i + 1, result)        result.pop()while True:    K, *S = map(int, input..

728x90
반응형