해킹왕 양선규

[백준 10431 / Python / 실버5] 줄세우기

구현, 정렬, 시뮬레이션 문제이다. 모든 학생이 각자 물러선 총 횟수를 구해야 한다. import sysinput = sys.stdin.readlinedef binary_search(child, arr): start = 0 end = len(arr) - 1 result = len(arr) while start end: mid = (start + end) // 2 if arr[mid] > child: result = mid end = mid - 1 else: start = mid + 1 return len(arr) - resultP = int(input())for _ in r..

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 문자열 문제이고 문제 조건이 크게 어려운 건 아닌데, 구현 문제다 보니까 디테일한 부분에서의 실수가 없도록 주의해야 하는 문제이다. def solution(msg): """인덱스 -> 문자열, 문자열 -> 인덱스 사전 제작""" idx_to_str = [''] + [chr(i) for i in range(ord('A'), ord('Z') + 1)] str_to_idx = dict() for i in range(26): char = chr(ord('A') + i) str_to_idx[char] = i + 1 """메인 로직, 문자열을 전부 압축할 때..

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 == '': ..

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

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..

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..

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 ..

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

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

그래프 + 구현 문제이고, 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..