분류 전체보기
-
삼각화단 만들기Algorithm with C/ETC 2020. 8. 31. 08:43
1. 문제 문제는 아래에서 볼 수 있다. DFS를 이용해서 만들 수도 있지만, 선형 탐색을 이용해서 구현할 수 있다. https://designatedroom87.tistory.com/65?category=881035 삼각화단 만들기 1. 문제 2. 문제 분석 이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다. 결론부터 말하면, 이 문제는 재귀 designatedroom87.tistory.com 2. 구현 프로그램 실행결과 3. 소스 파일
-
회문(Palindrome)Algorithm with C/BFS 2020. 8. 31. 07:46
1. 문제 문제는 아래에 정의되어 있다. DFS로 만든 것을 BFS로 구현할 것이다. https://designatedroom87.tistory.com/63?category=881035 회문(Palindrome) 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”.. designatedroom87.tistory.com 2. 자료 구조 정의 큐는 앞에서 만든 것을 이용한다. 그리고 큐에 저장할 정보는 탐색할 인덱스의 범위이다...
-
두더지 굴Algorithm with C/BFS 2020. 8. 30. 23:32
1. 문제 DFS에서 만든 두더지 굴을 BFS로 구현한 것이다. 문제는 아래의 글에서 보자. https://designatedroom87.tistory.com/61 큐에 저장할 데이터는 위치 정보이므로 아래와 같이 변경한다. 3. 구현 프로그램 실행결과 4. 소스 파일 & 헤더 파일 5. 두더지 굴의 수와 굴의 크기를 추가 그런데, 문제에서 보면 두더지 굴의 수와 그리고, 각 두더지 굴의 크기를 내림차순으로 출력을 해야한다. 기본적인 정렬 알고리즘은 버블 정렬을 이용하겠다. 그리고 각 두더지 굴의 크기를 저장할 변수를 배열로 선언하고 이는 전역 변수로 두겠다. DFS에서 만든 방식과 같다. 위의 함수를 호출하는 부분은 main함수에서 한다. 프로그램 실행결과 6. 소스 파일 & 헤더..
-
4종류 동전으로 N 센트를 표현하는 경우의 수Algorithm with C/DFS 2020. 8. 27. 19:22
1. 문제 쿼터( 25센트 ), 다임( 10센트 ), 니켈( 5센트 ), 페니( 1센트 ) 의 네 가지 동전이 무한히 주어진다고 했을 때, N 센트를 표현하는 모든 경우의 수를 구하라. 2. 문제 분석 이 문제는 재귀 문제이다. 함수 makeChange(N)을 부분 문제들의 답을 통해 계산하는 법을 알아내 보도록 하자. N = 100 이라고 해보자. 도합 100 센트의 잔돈을 만드는 방법을 계산해야 한다. 이 문제와 부분 문제들은 어떤 연관성을 가지는가? 100센트의 잔돈에는 쿼터가 0개, 1개, 2개, 3개, 4개 있을 수 있다는 것을 알고 있다. ( 쿼터는 25센트니까, 25 * 5 = 125센트가 되어서, 쿼터는 5개가 될 수 없다. ) 그러므로, 위의 관계가 성립한다. 이 결과를 좀 더 들여다보면..
-
미로 탐색Algorithm with C/BackTracking 2020. 8. 26. 19:26
0. 참고 문헌 1. 개념 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데, 이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다. 여기에서 부분 문제의 답은 어느 것이라도 될 수 있다. 선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로. 게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고, 그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다. 백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있..
-
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. 소스 & 헤더 파일