tech.log tech.log

최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불린다. - 대표적으로는1. '한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는' 다익스트라 알고리즘2. '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는' 플로이드 워셜 알고리즘이 있다. - 보통 '그래프' 를 이용해 표현된다.1. 각 지점은 '노드'로 , 연결된 도로는 '간선'으로 표현된다 다익스트라 알고리즘- 특정 노드에서 다른 특정 노드로 가는 각각의 최단 경로를 구해주는 알고리즘- 음의 간선(0보다 작은 값을 가지는 간선) 이 없을 때 사용- 현실 세계의 gps 알고리즘으로 채택된다 -> 현실세계에서는 음의 간선이 없으므로 가능- 매 단계 가장 비용이 적은 노드를 선택해서 과정을 반복하므로..

변수 설명 board = 판 vis = 방문 여부 n,m 각각 행과 열의 개수 dx,dy = 상하좌우 처리 위한 변수 1. (0,0) 방문 처리 후 큐에 추가 2. 상하좌우 살피며 큐에 추가 3. 큐의 front를 cur에 저장 후 pop 4. dx,dy를 활용하여 상하좌우 탐색 (대부분 x가 행 , y 가 열을 의미함) 5. dx,dy 가 범위에 있는지 부터 확인 중요(처리 안 할 시에 런타임 에러남) 자주 하는 실수 1. 시작점에 방문했다는 표시를 남기지 않음 2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남김 -> 시간초과 혹은 메모리 초과 발생 3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못 함 bfs 문제 기본 1926: 그림 더보기 1. 상하좌우로 ..

다음은 코딩 테스트에 빈출되는 탐색의 빈출 유형과 대비 방법이다. 용어 정리 그래프: 여러 개체들이 연결되어 있는 자료구조 탐색: 특정 개체를 찾기 위한 알고리즘 그래프 탐색 알고리즘: 여러 개체들이 연결되어있는 구조에서 특정 개체를 찾는 알고리즘 대표적 문제 유형 밑 3가지의 case가 대표적인 탐색의 문제 유형이며, 2개가 섞여 출제 되는 문제도 있다. 1. 경로탐색 유형(최단거리, 시간) 2. 네트워크 유형(연결): 여러 개체들이 주어진 상태에서 연결되어 있는 개체의 그룹 개수 구하기, 연결 여부 확인하기 3. 조합 유형(모든 조합 만들기): 순열, 조합 방식 구현 방법 DFS: 재귀 함수 => 탈출 조건을 만족 할 때까지 재귀함수를 구현하고, 이후 파라미터 값을 바꾸어가며 정답을 끝까지 도출 ex..

개념 - 문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 의미 - 문자열은 로우 레벨에서 조작하거나, 문자형이 따로 없는 C 같은 경우 조작이 매우 까다로움 - 대부분의 언어에서는 문자열 조작을 위한 다양한 기능을 기본으로 제공하므로 기본 기능들을 잘 활용하는 것이 중요 문자열 처리가 사용되는 분야 1) 정보 처리 분야: 현대의 거의 모든 정보는 문자열로 구성되어 있어, 문자열 처리는 정보 처리에 핵심적인 역할을 한다. 2) 통신 시스템 분야: 메세지, 이메일 전송 시 문자열을 한곳에서 다른 한 곳으로 전송한다. 또한 데이터 전송은 문자열 처리 알고리즘이 탄생한 배경이기도 하다. 3) 프로그래밍 시스템 분야: 프로그램은 자체가 문자열로 구성되어져 있다. 예제1 유효한 팰린드롬_ from l..

Backtracking - 문제의 해결 방법을 탐색하다 가능성이 없다고 판단되는 후보를 즉시 가지치기(Pruning)하는 방식 - bfs 와 같은 방식으로 탐색하는 모든 방법으로, bfs는 backtracking의 골격을 이루는 알고리즘 - bfs 와 같은 재귀 방식으로 구현 - 운이 좋으면 시행착오를 거치지 않고 해답을 얻을 수 있지만, 최악의 경우 모든 경로를 거쳐야 함 - backtracking 에서 사용되는 가지치기(Pruning) 는 트리의 탐색 최적화 문제(제약 충족 문제(constraint satifaction problems))와도 연관 * 제약 충족 문제 : 수많은 제약 조건(constraint)을 충족하는 상태(States)를 찾아내는 수학 문제 : ex) 스토쿠, 8퀸 문제, 4색 문..