알고리즘 - 백트래킹, 그래프
1.백준 2178 미로 탐색(BFS & DFS 기초)
문제는 2차원 배열에 관한 탐색 기초문제이다.즉, 주어진 이동조건에 따라 mx, my를 만들어야 한다는 점이다.DFS 이용 (시간 초과)
2.백준 25418 정수 a를 k로 만들기(BFS 기초 - 1차원배열)
해당 문제는 1차원 배열에서 많은 경우의 수 중 최단거리를 찾는 문제이다. 이러한 많은 경우의 수에서 최단 거리를 찾는 문제는 보통 BFS를 많이 쓴다.주어진 문제의 규칙은 정수+1, 정수x2 두 가지이다.이 규칙은 2차원 배열에서의 BFS를 풀 때 이동방향을 체크하는
3.백준 24444 알고리즘 수업-너비 우선 탐색1 (BFS 기초 - 2차원배열)
BFS 다시 정리할 겸 기본문제를 풀어보았다.주어진 문제가 양방향인지 단방향인지 판단해야 한다. 양방 일 경우, append를 두 노드 다 해야한다.2차원에 관한 문제일 경우 노드에 연결된 다른 노드를 저장시키는 배열이 필요하다. (예를들어, 1번 노드와 3,4번이 연
4.백준 9663 N-Queen (백트래킹 기초)
문제 이해하는데 거의 3시간 넘게 걸렸다..모든 경우를 탐색하는 문제에서 조건을 걸고 해당 조건 불충족일 시 탐색하지 않음(가지치기) 를 통해 탐색을 줄임이러한 해가될 후보를 뽑는 과정을 유망(promising)이라 함.Queen의 움직임을 가지치기로 제한시켜 탐색시켜
5.백준 14502 연구소
문제는 쉽게 이해가 갔지만, 구현하는데 있어서 조금 어려웠던 문제이다. 벽을 3개 놓는 경우는 해당 인덱스가 0일 때를 기준으로 모든 경우를 탐색해야 하기에, 백트래킹을 통해 놓을 수 있다.또한, BFS로 놓은 벽을 기준으로 바이러스를 퍼뜨리는 과정을 찾았을 때 0의
6.백준 1759 암호 만들기
최소 한 개의 모음과 두 개의 자음을 이용하여 l 만큼의 길이로 단어를 뽑으면 되는 문제이다. 또한 단어를 사전 순으로 출력하면 된다.주어진 단어 리스트 중에서 l 개를 뽑으면 되는 문제로 변환할 수 있다.즉, 백트래킹을 이용한다면 문제를 쉽게 풀 수 있다.