1. DFS 구현DFS는 stack으로 구현되며 재귀 함수를 통해 구현할 수 있다.import sysinput = sys.stdin.readlinedef dfs(now, graph, visited): visited[now] = True print(now, end=' ') for next in graph[now]: if not visited[next]: dfs(next, graph, visited)n, m, start_node = map(int, input().rstrip().split()) graph = [[] for _ in range(n+1)] ..
Algorithm
1. 풀이from collections import dequedef solution(edges): answer = [] max_num = 0 graph = [[] for _ in range(1000001)] # 만들어진 노드는 들어오는 edge가 없다. 이를 체크하기 위한 노드다. not_end_list = [True for _ in range(1000001)] # graph를 생성한다. for edge in edges: start, end = edge graph[start].append(end) not_end_list[end] = False max_num = max(max_num, start, end)..
1. 문제 정의큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰수를 만드는 법칙이다. 이때 특정 인덱스에 해당하는 수가 K번 연속해서 더해줄 수 없다. 입력: 첫째 줄에 N(2이상 1000이하), M(1이상 10000이하), K(1이상 10000이하)가 주어진다. 둘째 줄에는 N개의 자연수(1이상 10000이하)가 주어진다. 이때 입력으로 주어지는 K는 항상 M 이하다.출력: 큰 수의 법칙에 따라 더해진 답을 출력한다.2. 풀이# 입력n, m, k = map(int, input().split())num_list = list(map(int, input().split()))# 첫 번째로 큰 수와 두 번째로 큰 수 뽑아냄max_num = max(num_list)num_li..
1. 풀이풀이는 다음과 같이 Brute Force로 풀었다. 다른 사람들 풀이도 비슷하게 Brute Force로 풀었기에 다른 풀이는 따로 포스팅하지 않았다.# friends: 친구들의 이름을 담은 1차원 문자열 배열# gifts: 이번 달까지 주고받은 선물 기록을 담은 1차원 문자열 배열def solution(friends, gifts): ''' friends_dict: gifts_count_list에 활용하기 위해 각 이름을 key로, 인덱스를 value로 가지는 dictionary gifts_index: 선물 지수를 담는 1차원 리스트 gifts_result: 다음 달 받을 선물의 개수를 담는 1차원 리스트 gifts_count_list: 선물을 준 사람은 행, 선물을 받..
해당 문제는 아래와 같은 알고리즘으로 풀이했다.입력받은 수식을 문자열로 저장하고, 문자 하나씩 탐색한다.피연산자의 경우 해당 피연산자에 해당하는 값으로 변환하여 리스트에 순서대로 저장한다. (값으로 변환하기 위해 values 리스트를 사용하고, 해당 값들은 stack에 담긴다.)만약 연산자를 만나는 경우, stack에서 두 값을 꺼내고 해당 연산자에 해당하는 연산을 수행한다.코드는 다음과 같다.import sysinput = sys.stdin.readlinen = int(input())formula = input().rstrip()values = list()stack = list()for i in range(n): values.append(int(input()))for i in formula: ..
해당 문제는 이전에 풀었던 오큰수(17298)과 비슷한 문제다. 단지 while문의 조건만 바꾸어주면 된다. 알고리즘은 다음과 같다.결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)각 원소가 몇 번 나왔는지 카운트한 숫자를 담은 dict를 선언한다. (count_dict) 단, 현재 코드에서는 defaultdict를 사용했지만, 그냥 (모든 원소가 0인) 100만까지의 숫자를 담을 수 있는 리스트를 선언해도 된다.stack은 아직 자기보다 많이 나온 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하..
해당 문제는 다음과 같은 알고리즘으로 풀이했다.결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)stack은 아직 자기보다 큰 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하자.)stack에 남아있는 원소가 있고(자기보다 큰 수를 찾지 못한 원소가 있고), 그 원소들 중 가장 오른쪽의 원소와 current_value를 비교했을 때 current_value가 더 크다면, stack에서 가장 오른쪽의 원소를 빼내고, 해당 원소의 NGE값은 current_value로 설정한다. 해당 코드는 다음과 같다...
해당 문제는 다음과 같은 알고리즘으로 풀이했다.레이저는 ()로 표시되어 있다. 따라서 ()부분을 모두 문자 L로 바꾼다. (.replace() 메서드 사용)주어진 문자열(formula)를 탐색한다. 이때 '('부분은 막대가 시작하는 부분으로 막대가 시작하는 부분이 나오면 num_stick에 1을 더해준다. (num_stick은 현재 구간에 있는 막대 개수다.)문자열 탐색 도중 ')'를 만난다면 가장 짧은 막대기 하나가 끝나는 부분이다. 따라서 num_stick에 -1을 해주고, 지금까지 세어준 막대기(result)에 +1을 한다.만약 'L'을 만나면 result에 num_stick을 더해주면 된다. (현재 구간에 쌓여있는 막대 개수만큼 레이저로 잘리기 때문이다.)코드는 다음과 같다.formula = in..
