반응형 전체 글103 [이취코] 음료수 얼려 먹기 출처 : 이것이 취업을 위한 코딩 테스트다 with python P. 149 유형 : DFS 1. 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다. 4 5 # N, M 00110 00011 11111 00000 2. 문제 설명 3 3 001 010 101 3. 코드 N, M = map(int,input().split()) graph = [] for _ in range(N): g.. 2022. 2. 8. [해커랭크] Journey to the Moon 문제 링크 : https://hackerrank.com/challenges/journey-to-the-moon 참고 : https://www.snoopybox.co.kr/1766 유형 : Algorithms > Graph Theory 난이도 : Medium 1. 문제 설명 문제는 링크타고 들어가면 자세히 볼 수 있고, 나중에 다시 볼 나를 위해 대략 설명하겠다. 4 1 0 2 위와 같은 예시가 있다고 했을 때, 결과는 5가 나와야 하는데 왜 5가 나와야 하는지 알아보자! 첫 번째 줄에 있는 숫자 2개 중 첫 번째(4)는 우주비행사 수를 나타내고, 두 번째(1)는 그 다음 줄을 몇 번 입력받을 지를 알려준다. 먼저 우주비행사 수가 4이므로 우주비행사가 [0,1,2,3] 이렇게(?) 있다. 첫 번째 줄을 제.. 2022. 2. 8. [백준] 1715번 : 카드 정렬하기 유형 : 힙, 자료구조, 그리디 [예제 입력] 3 10 20 40 [예제 출력] 100 1. 아이디어 처음에 예제를 잘못 이해했다. 2개씩 묶어서 결국 가장 적은 비교 횟수를 구하고자 하기 위해 작은 크기부터 정렬을 해야 한다고 생각했다. 여기까지는 방향을 맞게 왔으나.. 카드 묶음을 비교하고 난 결과값을 다시 카드 더미에 넣는 부분을 빼먹었다. 그래서 테스트케이스 값이 계속 다르게 나와 어디서 틀린지조차 몰랐었다. 알고리즘은 다음과 같다. (풀이 참고) ① 총 비교 횟수(result)를 0으로 둔다. ② 현재 카드 더미(card) 중 가장 작은 2개의 카드 묶음(first, second)을 고른다. ③ _sum = first + second 값이 현재 단계에서 비교한 횟수를 의미한다. ④ _sum 값을.. 2022. 1. 25. [백준] 1927번 : 최소 힙 유형 : 힙, 자료구조 [예제 입력] 9 0 12345678 1 2 0 0 0 0 32 [예제 출력] 0 1 2 12345678 0 1. 내 풀이 1) 첫 번째 풀이 import sys n = int(sys.stdin.readline()) list = [] for i in range(n): x = int(sys.stdin.readline()) if x == 0: # 가장 작은 값 출력 if len(list) == 0: print(0) else: print(min(list)) list.remove(min(list)) # min 제거 else: list.append(x) ▷ 시간초과가 발생하길래, sys.stdin.readline()을 이용하였다. ▷ heapq라는 라이브러리를 몰라서 못 썼는데, 내가 알고.. 2022. 1. 24. [백준] 2250번 : 트리의 높이와 너비☆ 유형 : 트리, 구현 난이도 : 중(상) [예제 입력] 19 1 2 3 2 4 5 3 6 7 4 8 -1 5 9 10 6 11 12 7 13 -1 8 -1 -1 9 14 15 10 -1 -1 11 16 -1 12 -1 -1 13 17 -1 14 -1 -1 15 18 -1 16 -1 -1 17 -1 19 18 -1 -1 19 -1 -1 [예제 출력] 3 18 1. 내 풀이(미완성) class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node self.col = 0 self.level = 0 array = [] def in_orde.. 2022. 1. 10. [백준] 1991번 : 트리 순회 ☆ 유형 : 트리, 구현 [예시 입력] 7 A B C B D . C E F E . . F . G D . . G . . [예시 출력] ABDCEFG DBAECFG DBEGFCA 1. 내 풀이 더보기 N = int(input()) value_list = [] key_list = [] for _ in range(N): tmp = input().split(' ') key_list.append(tmp[0]) value_list.append(tmp[1:]) graph = dict(zip(key_list,value_list)) start_node = 'A' visited, need_visit = list(), list() need_visit.append(start_node) # 전위 순회 while need_visit:.. 2022. 1. 9. BFS(Breadth-First Search), DFS(Depth-First Search) 1. 그래프 탐색 알고리즘 1) 대표적인 알고리즘 ① 너비우선탐색(BFS; Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 ② 깊이우선탐색(DFS; Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 2) 예제 - 그래프가 아래 그림처럼 있을 경우, 그래프를 BFS와 DFS로 탐색하는 순서를 알아보자. ① BFS : A → B → C → D → E → F ② DFS : A → B → D → C → E → F 2. 그래프 표현 - 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 있다. - 노드들을 key로 만들어주고, 해당 노드에 간선으로 연결된 인접 정점을 values에 추가한다. key values A.. 2022. 1. 5. [백준] 1939번 : 중량제한 ☆ 유형 : 이진탐색, BFS [예제] 3 3 1 2 2 3 1 3 2 3 2 1 3 [출력] 3 1. 풀이 출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online ** 핵심 아이디어 1. 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000이다. - 중량 제한이 값이 크기 때문에 이진 탐색으로 풀 수 있을 것이라 의심 - log나 √로 풀 수 있을 것 같은 생각 - 중량 제한 c를 찾고자 하기 때문에, 찾고자 하는 값을 이진 탐색을 수행 - BFS 이용 : 그래프 간선, 노드가 주어졌을 때 특정 노드에서 다른 노드로 이동이 가능한지 판단 - BFS는 다리(간선)의 개수만큼 수행하기 때문에 시간복잡도는 O(M)이다. → 이진탐색 시간복잡도 : .. 2022. 1. 5. [백준] 2110번 : 공유기 설치 ☆ 유형 : 이진탐색 [예제] 5 3 1 2 8 4 9 [출력] 3 1. 풀이 출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online ** 핵심 아이디어 1. 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000이다. - 값이 10억이상으로 설정된 경우 이진탐색을 고려해보아야 한다. → logX나 √X의 시간복잡도를 가진다고 생각하고 방법을 생각해야 한다. 2. 이진 탐색으로 O(N*logX)에 문제를 해결할 수 있다. - 20만 * 30 = 600만 3. 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾는다. - 이진탐색을 재귀적 방법이나 반복적 방법으로 풀 수 있는데, 여기서는 반복적 방법으로 하는 게 편하다. ex. 1 2 4 .. 2022. 1. 4. 이전 1 2 3 4 5 6 ··· 12 다음 반응형
