개발왕 양선규

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

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

기본적인 백트래킹 문제이다.주어진 집합에서 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..

누적 합, DP 문제이다.2차원 리스트를 사용하기 때문에 단일 리스트보단 조금 더 복잡하다. # 실버1 -> 누적 합"""N : 표의 크기M : 합을 구해야 하는 횟수"""import sysinput = sys.stdin.readlineN, M = map(int, input().split())origin = [list(map(int, input().split())) for _ in range(N)]# dp(누적 합)테이블 생성dp = [[0] * (N + 1) for _ in range(N + 1)]for i in range(1, N + 1):    for j in range(1, N + 1):        dp[i][j] = origin[i-1][j-1] + dp[i][j-1] + dp[i-1][j] ..

투 포인터 문제이다.근데 해결방법 고민 하는데 시간복잡도도 그렇고 그냥 구현해도 될 거 같아서 해봤는데 풀려버렸다... 결론은 투 포인터 안 쓰고 그냥 구현으로 풀었다. # 실버1 -> 투 포인터"""N : 회전 초밥 벨트에 놓인 접시의 수D : 초밥의 가짓수(초밥 최대 번호)K : 연속해서 먹어야 하는 접시의 수C : 쿠폰으로 먹을 수 있는 초밥 번호"""import sysinput = sys.stdin.readlineN, D, K, C = map(int, input().split())sushi = [int(input()) for _ in range(N)]count = 0for start in range(N):        choice = [sushi[(start + i) % N] for i in ra..

무난한 분할 정복 문제이다. 재귀함수가 사용된다. # 실버2 -> 분할 정복, 재귀"""N : 1 또는 3의 k승-1, 0, 1 로 이루어진 N * N 행렬하나의 수로 이루어져 있지 않다면 9개로 분할분할을 마친 후, 각 숫자로 이루어진 종이가 몇개인지 출력"""import sysinput = sys.stdin.readlineN = int(input())table = [list(map(int, input().split())) for _ in range(N)]minus, zero, plus = 0, 0, 0def divide(x, y, n):    global minus, zero, plus    prev = table[x][y] # 기준이 될 숫자 설정    for i in range(x, x + n):..

이분 탐색 문제이다. 늘 결과 도출 부분에서 묘하게 헷갈린다. # 실버2 -> 이분 탐색"""K : 이미 가지고 있는 랜선의 개수N : 만들어야 할 랜선의 개수data[] : K개 랜선 리스트start : 1 -> 랜선 최소 길이end : max(data) -> 랜선 최대 길이- 랜선 길이를 기준으로 이분 탐색 실시- 반복할 때 마다 조건 검사    -> 해당 길이로 N개 랜선 제작이 가능한지    -> 모든 랜선을 일일이 길이로 나눠 총 랜선 개수 세기- 최대값을 찾아야 하므로 end 출력"""import sysinput = sys.stdin.readlineK, N = map(int, input().split())data = [int(input()) for _ in range(K)]start = 1en..

DP 문제이다. 언제나 어렵고 새롭고 가장 싫어하는 알고리즘이다. # 실버1 -> DPimport sysinput = sys.stdin.readline# 테스트 케이스 개수T = int(input())for _ in range(T):    N = int(input()) # 스티커 길이    sticker = []    sticker.append(list(map(int, input().split())))    sticker.append(list(map(int, input().split())))    if N == 1:        print(max(sticker[0][0], sticker[1][0]))        continue    dp = [[0] * (N + 1) for _ in range(3)] ..

DFS, 백트래킹 문제이다. 상하좌우 탐색을 요하기 때문에 BFS로도 잠시 생각했었으나 백트래킹이 필요했기에 DFS로 진행했다. 어느정도 정석에 가까운 백트래킹 문제 같다. # DFS, 백트래킹import sysinput = sys.stdin.readline# 입력받기R, C = map(int, input().split())board = []for _ in range(R):    board.append(list(input().strip()))# 사전준비directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]visited = [[False] * C for _ in range(R)]visited[0][0] = Truepath = set() # 집합으로 불필요한 중복 알파벳이 들어..