ULISIA's Developer Life

출처:알고리즘 수업 - 깊이 우선 탐색 1 문제해석 1번 노드를 처음 시작하므로 첫번째 방문으로 visited 되었다고 표현하기 위해 isVisited[1]을 1로 바꿈 1번 노드와 연결된 2번, 4번 노드 중에서 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드를 2번째로 방문하였으므로 isVisited[2]를 2로 변경 2번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드 중에서 작은 값인 3번 노드 방문 -> 3번 노드를 3번째로 방문하였으므로 isVisited[3]을 3으로 변경 4번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드들이 더 이상 없으므로 재귀 종료. 따라서 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 명시 출력은 isVi..

출처:5567번 결혼식 문제해석 N=동기의 수 상근이는 1번이므로 결과에서 포함되지 않음 친구와 친구의친구까지만 포함 1번 노드(상근이)를 시작으로 너비 우선 탐색(BFS)를 진행하면서 거리(dist)가 2 이하인 노드들의 개수만 세주면 된다. 해답코드 # 결혼식 import sys from collections import defaultdict, deque def bfs(start): ans=0 isVisited = [0 for _ in range(n+1)] isVisited[start] = 1 q = deque([[start,0]]) while q: u, dist = q.popleft() if dist

출처:14002번 가장 긴 증가하는 부분 수열 4 문제해석 수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘이라는 알고리즘 문제에서 자주 볼 수 있는 것을 사용하여 길이를 구할 수 있다. 이 문제에서는 길이뿐만 아니라 해당 수열까지도 결과값으로 출력해야 한다. 해답코드 #가장 긴 증가하는 부분 수열 4 import sys input = sys.stdin.readline n = int(input()) array = list(map(int, input().split())) dp = [1] * n #최장 부분 증가 수열 길이를 구하는 for문 for current in range(n): for ..

출처:1748 수 이어 쓰기 1 문제해석 문제를 풀기 전에 딱 보기에도 가장 반복문으로 모든 수의 자릿수를 일일이 더하는 식으로 구현을 진행하면 시간초과가 나올 것 같은 문제였다. 일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다. 코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 또한 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 계산하는 것이 좋다. 응시자가 작성한 프로그램으로 모든 케이스를 통과해야만 합격으로 판단하므로 "최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다. 그렇기에 이번 문제..