전체 글
-
연구활동 가는 길( 인접 행렬 풀이 )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로 세팅을 한다. 그리고, 탐색을 해보자. 탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.) 다만 탐색을 진행하다가 탐색..
-
두더지 굴Algorithm with C/DFS 2020. 8. 11. 17:59
1. 들어가기에 앞서 아래의 두더지 굴 문제에 들어가는 알고리즘을 Floud Fill 알고리즘이라 한다. 이 방식은 우리가 많이 한 "지뢰찾기"게임에서 쓰인다. 아래의 문제에서도 나왔다시피 "1이 상하좌우로 연결되어 있으면" 이라는 표현이 나오는데, 상하좌우란 의미가 곧, 탐색 방향이 네방향이다라는 사실을 알 수 있다. 2. 문제 3. 문제 분석 주어진 문제에서 가장 첫 번째로 해야할 일은 두더지 굴을 하나 찾아내는 함수를 만들어야 한다. 이 함수의 이름을 SearchDFS라고 하겠다. 함수 이름처럼 "이 우선 탐색"을 해서 하나의 굴을 찾는 함수이다. 하나의 굴을 찾았으면, 처음에 할 일은 두더지굴의 넘버링을 붙여주는 것이다. 그리고, 이 함수의 리턴형을 결정해주어야 하는데, 하나의 굴을 찾아서 알게되..
-
Select Sort (version2)C 자료구조/Sort Basic 2020. 8. 10. 17:44
1. 설명 정렬의 기준은 오름차순이다. 정렬을 할 배열을 A[n]이라 한다. 배열 A[1...n]에서 가장 큰 원소를 찾아, 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉, 가장 큰 원소는 자기 자리를 찾았으므로, 더 이상 신경 안써도 된다. 이 원소는 정렬이 끝났다고 볼 수있으므로, 이제 이 원소를 제외한 나머지 원소들도 같은 작업을 반복하면 된다. 아래는 선택 정렬 알고리즘 의사코드 위의 알고리즘을 풀어서 쓴 의사코드 알고리즘의 입력은 정렬해야할 배열 A[1...n]이다. 위의 알고리즘 식 알파에서 변수last는 정렬할 배열의 맨 마지막 인덱스, 즉, 배열의 크기를 나타낸다. 처음에는 배열의 크기가 n으로 시작하므로, A[1...n]을 정렬 대..