728x90 Problem Solving103 [Algorithm] 4-(3). DFS(Depth-First Search) [Algorithm] 4-(3). DFS(Depth-First Search) 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 1. 그래프의 기본구조 노드와 간선으로 표현된다. 노드를 정점이라고도 말한다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있으면 인접하다고 표현한다. + 인접 행렬과 인접 리스트에 대한 개념을 확실히 해야 한다. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 파이썬에서 리스트로 행렬을 표시할 때에는 graph = [ [0, 7, 5], [7, 0, inf], [5, inf, 0] ] 이런 식으로 표현을 한다.. 2022. 4. 27. [Algorithm] 4-(2) 재귀함수 [Algorithm] 4-(2) 재귀함수 1. 개념과 특징 자기 자신을 다시 호출하는 함수다. DFS를 실질적으로 구현하고자 할 때 사용하기도 한다. def recursive_function(): print(‘재귀 함수를 호출한다.’) recursive_function() recursive_function() 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 즉, 다시 자기자신을 부르는 return값 이외에 일정 조건(종료조건)이 되면 return 해주는 식이 있어야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. 파이썬은 최대 재귀 깊이 제한이 있다. 조건을 두지 않고 재귀적으로 함수를 호출하면 무한으로 생성되지 않고 오류가 나면서 종료된.. 2022. 4. 27. [Algorithm] 4. 그래프 탐색 알고리즘 [Algorithm] 4. 그래프 탐색 알고리즘 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다 대표적인 그래프 탐색 알고리즘은 DFS, BFS가 있다. DFS/BFS는 코테에서 매우 자주 등장하는 유형이기에 반드시 숙지해야 한다. 1. 필수 개념 자료구조의 기초 개념으로 스택과 큐가 있으며, 두 핵심적인 함수로 구성된다. Push(삽입) : 데이터를 삽입한다. Pop(삭제) : 데이터를 삭제한다. 스택과 큐는 오버플로우, 언더플로우를 고민해야 한다. 오버플로우는 자료구조가 수용할 수 있는 데이터 크기를 가득 찬 상태에서 삽입 연산할 때 발생 언더플로우는 데이터가 없는 상태에서 삭제 연산을 할 때 발생 2022. 4. 27. [Algorithm] 3. 구현 [Algorithm] 3. 구현 1. 개념과 접근 1) 개념 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. problem - thinking - soultion 문제가 있고, 그것을 생각해서 해결점을 제시하는 것, 모든 문제가 구현 유형의 문제라고 할 수 있다. 모든 문제가 구현의 과정을 거쳐야 한다. 피지컬이 좋다 => 구현을 잘한다. (기초 체력과 같다.) 다만 협의적으로 볼 때, 구현이 어려운 문제를 ‘구현’ 유형의 문제라고 한다. 2) 접근 방법 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제가 이에 해당한다. ex. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 .. 2022. 4. 27. [백준] 10816 숫자 카드 2 python 알고리즘 문제 문제 10816. 숫자 카드 2 1. 나의 코드와 발상 과정 (1) 제출 답안 from bisect import bisect_left, bisect_right import sys n = int(input()) num_list = list(map(int, sys.stdin.readline().split())) m = int(input()) find_list = list(map(int, sys.stdin.readline().split())) num_list.sort() def count_by_range(array, left, right): right_index = bisect_right(array, right) left_index = bisect_left(array, left) return right_ind.. 2022. 4. 25. [백준] 1920 수 찾기 python 알고리즘 문제 문제 1920. 수 찾기 1. 나의 코드와 발상 과정 import sys n = int(input()) num_list = list(map(int, sys.stdin.readline().split())) m = int(input()) find_list = list(map(int, sys.stdin.readline().split())) num_list.sort() def count_by_range(array, target, start, end): if start > end: return 0 mid = (start + end) // 2 if array[mid] == target: return 1 elif array[mid] > target: return(count_by_range(array, target, .. 2022. 4. 25. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음 728x90
