김머성 블로그

가치 그래프를 활용해서 문제 풀기 - 순한맛

전에 설명했었던 그래프에 가치망을 더해서 문제풀이를 해보겠다. 특히 넓이우선 탐색의 문제 풀이에서는 다른 풀이방법들(그리디, 백트래킹)로는 정상적인 답 도출이 어려운 문제들을 그래프로 풀어보겠다. 간단한 가치망을 가지고 있는 깊이 우선 탐색문제부터 풀어보도록하자. [문제 출처] jungol.co.kr ...더보기 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생..

깊이 우선 탐색 / 넓이 우선 탐색 + 그래프를 알고리즘상으로 표현하기

++참고 인프런 이재규님 강의 깊이 우선 탐색은 depth first search라고 해서 DFS라고 불리우는 탐색법이다. 그래프의 모든 정점들을 효율적으로 방문하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다. 현재 방문한 정점에 연결된 정점 중 방문하지 않은 정점을 방문한다. 재귀적인 특성을 가지고 있고 스택을 활용해서 재귀호출을 제거 할 수 있다. 넓이 우선 탐색은 breadth first search라고 해서 BFS라고 불리우는 탐색법이다. 깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다. 현재 방문한 정점에 연결된 모든 정점을 한번씩 방문한다. 더 이상 현재 정점에 연결된 정점 중 방문하지 않은 정점이 없을 때, 다음 정점으로 이동해서 ..

그래프 개념

참고: 인프런 이재규님 강의 그래프란, 정점과 간선으로 이루어진 객체간의 연결 상태를 표현하는 방법을 의미한다. 정점과 간선의 절대적인 위치는 중요하지 않고 오직 연결 상태만이 중요하다는 특징이 있다. 즉, 위상적인 표현 방법이다. 위상적 : 좀 추상적인 개념이다. 절대적인 위치보다 객체간의 상대적인 위치와 상태가 중요하다는 의미로 이해하면 된다. 경로 : 말 그대로 정점 v1에서 v2로 가는 경로의 모든 순서 집합 단순 경로 : 같은 정점을 2번 지나지 않는 경로 부분 그래프 : 그래프 a가 그래프 b의 교집합이라면 a를 b의 부분 그래프라고 한다. 싸이클(회로) : 시작과 끝 정점이 같은 경로 신장트리 : 회로가 없는 그래프 완전 그래프 : 모든 정점이 간선으로 이어져있는 그래프. 정점의 갯수가 v개..

Backtracking - Sudoku

제일 일상에서 써먹기 좋은(?) 알고리즘이다. 예전에 학교에서 시험끝나고 수학선생님이 스도쿠 문제를 나눠주고 빨리 푸는 사람한테 먹을것을 나눠주는 이벤트를 많이 했는데 그 때 이 알고리즘만 알았으면 내가 싹 쓸어먹지 않았을까 ㅋ.ㅋ 심지어 그 때 시험 끝나고 딱 1달 즈음 뒤에 이 문제를 풀어서 더 아쉬웠다. #include #include #define n 9 // 스도쿠판은 9 x 9 int arr[10][10];int zero[100][2];int cnt = 0; int garo[100][100];int sero[100][100];int box[5][5][10]; void r(int x){int i, j;if(x == cnt) { //만약 모든 빈칸을 채웠다면 출력하고 프로그램을 종료한다.print..