본문 바로가기

코드테스트5

[코드테스트]우선탐색(깊이/너비)_DFS/BFS DFS 와 BFS 이란 미뤄두었던 DFS 와 BFS에 대해 공부해 보자. DFS(Depth First Search)는 깊이 우선탐색, BFS(Breath First Search) 너비 우선탐색의 약자로 DFS/BFS를 뭉뚱거려서 그래프 탐색 알고리즘이라고도 말한다. 의미를 하나씩 파혜 해보면 그래프 탐색 알고리즘: 그래프: 여러 개체들이 연결되어 있는 자료구조 탐색: 그래프 자료구조에서 특정개체 A를 찾을 때 사용하는 알고리즘이라 탐색으로 정의한다. 문제유형 코드테스트에서 DFS/BFS로 풀 수 있는 문제유형은 대표적으로 3가지로 요약된다. 경로탐색: A지점~B지점까지 가는데 최단거리 구하기, 최소시간 구하기 와 같은 경로탐색형 문제 네트워크유형: 여러 개체가 주어지고 연결되어있는 그룹의 갯수를 구하는 .. 2023. 12. 27.
[코드테스트]순열과 조합 Permutation & Combination 순열 (Permutation) 순열 (Permutation)은 집합안에 숫자들이 있을때 순서를 고려하여 나열한 경우의 수를 순열이라한다. 즉, 서로 다른 n개중 r 개를 선택해 순서를 정해 나열한 가짓수를 순열이라 정의한다. 기호로는 Permuation의 앞글자를 따서 nPr로 표시한다. 순열은 조합되는 순서가 고려됨으로 [1, 2, 3]의 리스트에서 2개 원소를 골라 순서를 정하는 순열을 고려해 보면 [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]로 순열을 구성할 수 있다. 주의 할 점은 (1,2)와 (2,1)은 다른 것이다. # 순열작성예시 from itertools import permutations arr = [1,2,3] nPr = permutations(arr, 2.. 2023. 12. 19.
[코드테스트]동적계획법_Dynamic Programing 2023. 12. 17.
[코드테스트]탐욕법_그리디_Greedy 2023. 12. 17.