bigkite

탐색 알고리즘 DFS / BFS DFS(Depth First Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 = 최대한 멀리 있는 노드를 우선으로 탐색 그래프 : 노드(정점)와 간선으로 표현됨! → 그래프: 하나의 노드를 시작으로 다수의 노드를 방문하는 것 → 두 노드가 간선으로 연결되어 있으면 “두 노드는 인접하다”고 표현 프로그래밍에서 그래프는 2가지 방식으로 표현할 수 있음 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 → 파이썬에서는 2차원 리스트로 구현! INF = 99999999999 # 연결이 되어 있지 않은 노드끼리는 무한의 비용 # 2차원 리스트를 이용해 인접행렬 표현 graph = [ [0,7,5], [7,0,INF], [5..

구현 : ‘ 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정’ → 결국 모든 범위의 코딩테스트 문제 유형을 포함하는 개념! ⁂ 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제! 피지컬이 중요! ex) 크게 2가지 유형으로 나눌 수 있음 완전 탐색 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행해야 하는 문제 구현 시 고려해야 할 메모리 제약 사항 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요X 매우 큰 수의 연산 또한 기본으로 지원 but, 실수형 변수는 다른 언어와 마찬가지로 유효 숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있음! 파이썬에서 리스트 크기 리스트 이용시 코딩테스트의 메모리 제한을 고려해야 함!..

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 보텀업 방식과 탑다운 방식 2가지로 나눌 수 있음! Top-Down 방식 큰 문제를 해결하기 위해 작은 문제를 호출 재귀함수 이용 메모이제이션 Bottom-Up 방식 작은 문제부터 차근차근 답을 도출 반복문을 이용해 소스코드를 작성 DP 테이블 🤓 ⭐ 다음 조건을 만족할 때, DP를 사용할 수 있다! 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 문제풀이 단계! 다이나믹 프로그래밍 유형임을 파악 - 완전 탐색 알고리즘으로 접근했을 때, 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 확인해보기! 재귀함수로 비효율적인 프로그램 작성한 뒤, 메모이제이션을 ..