Algorithm with C
-
N - QueenAlgorithm with C/BackTracking 2020. 8. 24. 18:19
0. 참고 문헌 1. 문제 2. 문제 분석 퀸은 8가지 방향으로 움직이며 공격을 할 수 있고, 이동 범위도 체스판 전체이다. 8개의 퀸 문제는 8 X 8 크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스 판으로도 문제의 확장과 축소가 가능하다. 4 X 4 이상의 크기라면 이 문제를 적용할 수 있는데, 그래서 8개의 퀸 문제를 N 개의 퀸 문제라 부르기도 한다. 퀸을 체스판에 배치할 때, 행을 기준으로 배치하는 것으로 약속을 하도록 하자. 그리고 체스판은 4 X 4로 고정하고 문제 풀이에 접근한다. 당연히 퀸은 하나의 행에 하나만 배치가 가능하다. (퀸의 공격 범위가 가능하므로) 아래의 [그림 1 ~ 4]는 체스판의 크기가 4 X 4일 때의 퀸을 놓는 방법을 나타낸 것이다. 별 모양이 퀸이다. [그..
-
경찰차Algorithm with C/DFS 2020. 8. 23. 21:46
1. 문제 어떤 도시의 중심가는 n개의 동서방향 도로와 n개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며, 남북방향 도로는 왼쪽부터 1에서 시작하여 n까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 n까지 번호가 할당되어 있다. 또한, 동서방향 도로 사이의 거리와 남북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 ( 동서방향 도로 번호, 남북방향 도로 번호 )로 나타낸다. n이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며, 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1,1)의 위치에 있고 경찰차2는 (n,n)의 위치에 있다. 경찰 본부에서..
-
연구활동 가는 길( 그래프 방식 )Algorithm with C/BackTracking 2020. 8. 21. 08:49
1. 그래프 방식의 풀이 과정 문제는 앞에 있으니 생략하도록 한다. 우선 자료 구조에서 작업한 그래프를 가지고 와서 구현을 할 것이다. (비용을 포함한 그래프를 그대로 가지고 와서 구현) 첫 작업은 파일에 있는 내용을 그래프에 저장해야 한다. 이는 LoadDataFromFile함수가 한다. 이 작업이 끝나면 아래와 같은 구조가 된다. 정점의 개수는 7개로 고정을 했다. 정점의 개수만큼 pVertexList배열이 동적할당이 된다. 탐색을 할 시작 정점은 앞의 인접 행렬 풀이에서와 마찬가지로 0번 정점이다. 아래는 탐색 함수이다. 2. 구현 프로그램 실행결과 3. 소스 & 헤더 파일
-
연구활동 가는 길( 인접 행렬 풀이 )Algorithm with C/BackTracking 2020. 8. 19. 19:08
1. 문제 2. 문제 분석 위는 SetDataLoadDataFromFile함수가 호출이 되면, 이차원배열g_Path에 cost가 저장이 된다. cost값이 0이라는 의미를 2가지를 포함하고 있다. 1. 자기 자신에서 자기 자신으로 갈 때의 cost값은 0이다. 2. '길'을 갈 수가 없는 경우에 cost값은 0이다. (현재의 정점과의 연결이 안된 경우) 예를 들어서, g_Path[0][0] = 0 의 의미는 자기 자신에서 자기 자신으로 갈 때의 경우이다. g_Path[1][2] = 0 의 의미는 1번 정점과 2번 정점은 서로 연결되지 않았다는 의미이다, 여기서, 탐색을 할 때 이차원 배열의 행과 열은 다음과 같다. 행 요소 = 현재의 정점 열 요소 = 현재의 정점과 연결된 다음 정점 이를 토대로 다시 설..
-
삼각화단 만들기Algorithm with C/DFS 2020. 8. 17. 19:26
1. 문제 2. 문제 분석 이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다. 결론부터 말하면, 이 문제는 재귀를 쓰는 방식보다 for문을 3번 돌려서 구하는 것이 빠르다. 우리는 2가지 방식 전부를 만들어 볼 것 이다. 그리고, 이 문제를 해결하기 전에 한 가지 약속을 하자. 아래와 같은 가정을 하는 이유는 밑에 나온다. 삼각형의 각 변의 길이를 A,B,C라고 두면, C를 가장 긴 변, B는 C다음으로 긴 변, A를 가장 작은 변이라고 가정하자. ( A
-
회문(Palindrome)Algorithm with C/DFS 2020. 8. 14. 18:12
1. 문제 We define a palindrome to be a sequence of characters that reads the same backward as it does forward. For example, “tacocat” and “12221” are palindromes, but, “tacocats” and “8675” are not. We define a subsequence to be a sequence formed by copying a contiguous section of elements from sequence and deleting 0 or more characters from it. Walter wants to improve his understanding of strings..
-
CheeseAlgorithm with C/DFS 2020. 8. 13. 17:55
1. 문제 2. 문제 분석 위의 문제에서 쓰이는 알고리즘이 흡사 스타크래프트에서 저그의 크립이 없어지는 알고리즘과 같을 것이라는 생각이 들지 않는가? 그리고, 이 문제는 앞에서 했던 "두더지 굴" 문제를 응용할 것이다. 아래와 같이 치즈가 놓여져 있는 이차원 배열이 있다고 가정해보자. 치즈가 놓여져있는 공간은 1, 없으면 0 . 첫 번째로 우리는 탐색 지점을 배열의 첫 번째 인덱스라고 가정하겠다. (0,0)이 초기값 탐색 방향은 편의상 "아래->오른쪽->위 -> 왼쪽" 이라고 하겠다. 처음에 시작점에 도착했는데, 치즈가 없는 공간이었다. 이 부분을 -1로 세팅을 한다. 그리고, 탐색을 해보자. 탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.) 다만 탐색을 진행하다가 탐색..