728x90
반응형

그래프 31

[프로그래머스 / 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] 도넛과 막대 그래프

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

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

[Baekjoon 1012 / python / 실버2] 유기농 배추

무난한 BFS 문제이다.상하좌우로 연결된 영역이 몇개인지를 출력하면 된다. # 실버2 -> BFS"""T : 테스트 케이스 개수M : 열 ( 가로길이 )N : 행 ( 세로길이 )K : 심어진 배추 개수table : 1은 배추, 2는 방문한 곳"""from collections import dequeimport sysinput = sys.stdin.readlineT = int(input())dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]# 테이블 내에 있고, 배추인지 확인하는 함수def going_no_going(nx, ny, table):    if 0 nx N and 0 ny M and table[nx][ny] == 1:        return True    return Fa..

Algorithm/BFS 2025.02.07

[Baekjoon 1987 / Python / 골드4] 알파벳

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() # 집합으로 불필요한 중복 알파벳이 들어..

[Baekjoon 2668 / Python / 골드5] 숫자고르기

DFS 문제이다. 진짜 최근에 푼 문제중 가장 어렵고 헷갈렸다.그래프의 싸이클을 찾는 문제이며, 문제만 읽고 싸이클을 찾아야 겠다는 유추를 해내기가 힘들다. 그래프로 옮기는 과정도 힘들고, 싸이클 찾는 로직도 매우 헷갈리고, 단방향인지 양방향인지, 역방향은 결과에 영향을 미치는지, 싸이클을 찾으면 해당 거쳐온 노드를 모두 추가하는 건 안되는지 판단해야 했고.. 하여튼 여러 방향으로 미치는 줄 알았다. # DFSimport sysinput = sys.stdin.readline# 입력받기N = int(input())graph = [[] for _ in range(N + 1)]for i in range(1, N + 1):    graph[i].append(int(input()))def DFS(node, sta..

Algorithm/DFS 2024.10.05

[Baekjoon 2573 / Python / 골드4] 빙산

DFS, BFS 문제이다. 처음에 DFS로 풀어보려 했지만 도저히 머리를 싸매도 감이 안 와서 다른 풀이를 참고해 BFS로 풀었다. 근데 풀고 나니 별로 어렵게 느껴지지가 않는다. 뭐든 그런 것 같다. 해내기 전엔 어렵고 해내고 나면 당연한 게 되고 말이다. # BFSfrom collections import dequeimport sysinput = sys.stdin.readlineN, M = map(int, input().split()) # 행, 열ice = [list(map(int, input().split())) for _ in range(N)]dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def iceBreaker():    # 빙산을 녹이고 개수를 세는 작업이 1번의 반복   ..

Algorithm/BFS 2024.10.04

[Baekjoon 21606 / Python / 골드3] 아침 산책

DFS 문제이다. 트리가 주어지며, 각 노드는 실외/실내의 특성을 갖는다.산책 루트는 반드시 실내로 시작해서 실내로 끝나야 한다. 그 사이에 실외가 몇개 있든 상관 없다. 이러한 산책 루트가 최대 몇개인지를 출력하면 되는 문제이다. 방향만 바꾼 것도 포함이다. 1->3 , 3->1 이 루트는 별개의 루트이다.  처음엔 문제 지문 그대로 코드로 옮겨 풀었었다.import sysinput = sys.stdin.readlineN = int(input()) # 노드 개수inout = input().strip()inout = [''] + [int(x) for x in inout] # 실내여부, 노드번호와 동기화를 위해 맨앞 빈값 추가graph = [[] for _ in range(N + 1)] # 노드 연결정보,..

Algorithm/DFS 2024.09.11

[Baekjoon 15666 / Python / 실버2] N과 M (12)

import sysinput = sys.stdin.readlineN, M = map(int, input().split())numbers = list(map(int, input().split()))numbers.sort()result = [-1] * Mdef compare(a, b):    if a > b:        return False    return Truedef backTracking(depth):    if depth == M:        print(' '.join(map(str, result)))        return        temp = 0    for i in range(N):        if temp != numbers[i] and (depth == 0 or compare(..

728x90
반응형