코딩테스트 문제풀이/beakjoon64 [백준] 11725 트리의 부모 찾기 [백준] 11725 트리의 부모 찾기 dfs&bfs / 파이썬 [문제] bfs나 dfs를 사용하는 문제 입력값) n:노드 a,b: 연결된 두 노드 인접 리스트방식으로 입력값이 주어짐. 백준은 이런형태가 많은 듯 하다. [과정] 기본적인 dfs탐색 부모-자식노드를 저장할 딕셔너리(parent)를 생성하고 bfs를 돌때 마지막부분에 부모-자식노드를 연결 [소스코드] # 트리의 부모 찾기 from collections import deque n = int(input()) graph = [[] for _ in range(n+1)] visited = [False] * (n+1) for i in range(n-1): a,b = map(int, input().split()) graph[a].append(b) grap.. 2021. 8. 5. [백준] 18352 특정 거리의 도시 찾기 [백준] 18352 특정 거리의 도시 찾기 dfs / 파이썬 [문제] 모든 도로의 거리가 1로 동일하므로 bfs를 사용하는 문제임을 알 수 있음 입력값) n: 도시의 개수 m: 도로의 개수 k: 거리정보 x: 출발 도시의 번호 노드와 간선정보가 인접 행렬방식과 인접 리스트방식중 인접 리스트 방식으로 입력됨을 확인하고 넘어가자 [과정] 1. bfs를 돌리기에 앞서 필요한 배열과 정보들을 저장 1.1) graph: 인접 리스트 방식으로 해당노드(graph[a])에 연결된 노드와 간선정보를 저장(.append(b,1)) 1.2) visited: 노드의 방문여부를 담은 배열 1.3) distance: 특정 노드(start)에서 해당 노드까지 가는 거리비용을 담은 배열 2. start(시작노드)에서 bfs 실행 .. 2021. 7. 30. [백준] 1439 뒤집기 [백준] 1439 뒤집기 그리디 알고리즘 / 파이썬 [문제] [과정] 1. 문자열의 길이만큼 반복 2. 각각 0으로 바꾸는 경우, 1로 바꾸는 경우 세기 3. 숫자가 바뀌는 경우 cnt(현재의 숫자)도 바꿔줌 4. 0으로 바꾸는 경우와 1로 바꾸는 경우 중 더 작은것을 출력 [소스코드] # 문자열 뒤집기 s = input() cnt_0 = 0 cnt_1 = 0 if s[0] == '0': cnt_1 += 1 else: cnt_0 += 1 for idx, v in enumerate(s): if idx == 0: cnt = v else: if v != cnt: if v == '0': cnt_1 += 1 cnt = v else: cnt_0 += 1 cnt = v print(min(cnt_0, cnt_1)) [.. 2021. 4. 4. [백준] 13305 주유소 [백준] 13305번 주유소 그리디 알고리즘 [문제] 최소비용 구하기문제 [과정] 1. 처음 정류장 -> 2번 정류장 까지의 거리*가격 ->변수(result)에 저장 2. 반복시작 -> 기존가격보다 싸면 p갱신 3. result += 갱신된가격 * p [소스코드] n = int(input()) d = list(map(int, input().split())) p = list(map(int, input().split())) result = p[0]*d[0] temp_p = p[0] for i in range(1, len(d)): if temp_p 2021. 2. 10. [백준] 1541 잃어버린 괄호 [백준] 1541 잃어버린 괄호 그리디 알고리즘 [문제] [과정] 1. '-' 부호를 기준으로 분할하여 입력받아 리스트로 만들기 2. 리스트를 반복하는데 첫 인덱스의 경우 '+' 기호가 있으면 '+'를 기준으로 분할하여 num에 더해줌 3. '+' 기호가 없을 경우 리스트의 첫인덱스를 num에 저장 4. 이후 나머지는 '+'를 기준으로 분할하여 모두 더한값을 num에서 빼줌 5. 출력 [소스코드] # 잃어버린괄호 n = input().split('-') num=0 for i, e in enumerate(n): if i == 0: if '+' in e: # 처음으로 나오는 부호가 '-'가 아닐경우 array = e.split('+') for j in array: num += int(j) else: num .. 2021. 2. 10. [백준] 11399 ATM [백준] 11399번 ATM 그리디 알고리즘 [문제] 이 문제는 리스트를 받고 정렬을 해준다. 이후 이전의 값을 모두 더한 변수 하나를 생성하고, 순차적으로 증가시켜준 후 결과를 담을 변수에 차곡차곡 더하면 끝난다. [소스코드] n = int(input()) person = list(map(int, input().split())) person.sort() p = 0 result = 0 for i in person: p+=i result += p print(result) [통과] // 알고리즘 스터디 그리디과제3 2021. 2. 9. [백준] 1931 회의실 배정 [백준] 1931 회의실배정 그리디 알고리즘 [문제] [소스코드] n = int(input()) meet_list = [] for _ in range(n): meet_list.append(list(map(int, input().split()))) meet_list.sort(key=lambda meet: [meet[1], meet[0]]) result_meet_cnt = 1 booked_end_time = meet_list[0][1] for idx in range(1, len(meet_list)): if meet_list[idx][0] >= booked_end_time: booked_end_time = meet_list[idx][1] result_meet_cnt += 1 print(result_meet_c.. 2021. 2. 9. [백준] 11047 동전 0 [백준] 11047번문제 동전0 그리디알고리즘 [문제] [소스코드] n,k = map(int, input().split()) coins_list = [] sum_min_coin_cnt = 0 for _ in range(n): coins_list.append(int(input())) for coin in reversed(coins_list): sum_min_coin_cnt += k // coin k %= coin print(sum_min_coin_cnt) [통과] // 알고리즘 스터디 그리디과제1 2021. 2. 9. 이전 1 ··· 5 6 7 8 다음 반응형
