문제 코드 def solution(N, number): if N == number: return 1 answer = -1 arr = [set() for _ in range(8)] for i in range(len(arr)): arr[i].add(int(str(N)*(i+1))) for i in range(1,8): for j in range(i): for op1 in arr[j]: for op2 in arr[i-j-1]: arr[i].add(op1+op2) arr[i].add(op1-op2) arr[i].add(op1*op2) if op2 != 0: arr[i].add(op1//op2) if number in arr[i]: answer = i+1 break return answer 풀이방법 이 문제는 동..

이 문제는 얼핏하면 dfs, bfs처럼 보여서 나도 처음에는 dfs로만 구현을 했었다. 하지만 dfs로 구현하면 값이 커질수록 반복되는 구간이 증가하기때문에 당연히 시간초과가 났었고 이를 고치기 위해 dp를 이용한 방법을 추가시켰다. 처음에는 dp를 어떻게 적용해야하는지가 감이 안와서 주변 친구들에게 도움을 받아서 이해를 하게 되었다. 이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다. 이 관점으로 코드를 구현해보자. 우선 처음에 dfs만 구현해서 시간초과가 난 코드이다. from sys import stdin as s..

이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을 깨달았습니다.. bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다. #N,K의 입력을 받음 N,K = map(int,s.readline().split()) #각 행을 graph 이중배열에 저장 graph=[list(map(int,s.readline().split()))for _ in range(N)] # S,X,Y의 값 입력 받음 S,X,Y = map(int,s.re..

위상 정렬💡 - 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다. - 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다. 비순환 방향 그래프(DAG) - 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다. - 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다. 위상 정렬 동작 과정 진입차수(in_degree)가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 1) 모든 정점의 in_degree를 표시합니다...

위의 문제는 bfs를 활용해서 고슴도치가 비버의 집을 찾아가는 시간을 출력하는 문제입니다. 이 문제를 풀 때 고슴도치를 먼저 이동할지 물을 이동할지 고민을 하다가 저는 고슴도치를 먼저 이동하고 물을 이동하는 방식으로 풀어봤습니다. 이렇게 하면 물이 다음에 이동할 거리를 생각안해도되므로 고슴도치의 조건이 하나 줄어듭니다. R,C = map(int,s.readline().split()) graph = [list(map(str,s.readline().strip())) for _ in range(R)] v = [[0]*C for _ in range(R)] q = deque() 우선 진행에 필요한 데이터들을 미리 생성해두고 bfs함수와 조건들을 생성합니다. #비버 집 위치 저장 for i in range(R): ..

위의 문제는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용해서 푸는 대표적인 문제입니다. 먼저 다익스트라 알고리즘의 동작 과정을 간단하게 소개하면 다음과 같습니다. 출발 노드와, 도착 노드를 설정 알고 있는 모든 거리 값을 부여 (모를 경우 무한(아주 큰 값)으로 설정) 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리르 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다. 우선 순위 큐를 사용하여 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리고 ..

먼저 위의 문제는 그래프 탐색 문제로 dfs, bfs 방법으로 풀 수 있습니다. 저는 dfs를 활용해서 문제를 풀어봤습니다. 처음에는 접근하는 방법이 잘못됐는지 얼음의 개수를 판단하는 함수와 dfs 함수를 구현하고나서 연도를 구하는데 한참 헤맸습니다.. 우선 메인부분부터 작성을 하면 아래와 같습니다. N,M = map(int,s.readline().split()) year = 0 arr = [list(map(int,s.readline().split())) for _ in range(N)] dx =[0,1,0,-1] dy =[1,0,-1,0] ice_cnt=0 N과 M 입력을 받고 연도를 구할 때 필요한 year와 arr 배열을 이중행렬로 받아서 표시합니다. 얼음 주변의 0의 개수를 파악하기 위해 dx, ..

스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..