목록Algorithm (28)
Inor
- 설계 스택 두개를 이용하면 큐를 구현할 수 있습니다. 각각의 스택을 enQueue와 deQueue 연산에 맞게 구분해주면 간단하게 구현이 가능합니다. enQueue 연산이 필요하면 먼저 deQueue 스택에서 모든 자료를 enQueue 스택으로 옮기고 enQueue 스택에 데이터를 Push 해줍니다. deQueue 연산이 필요하면 enQueue 슽개에서 모든 자료를 deQueue 스택으로 옮기고 deQueue 스택에서 데이터를 Pop 해주면 두개의 스택으로 큐를 구현할 수 있습니다. 혹시 큐를 여러개 사용하면 스택 구현이 가능할까 생각을 해봤는데 큐는 넣는 순서대로 삭제 되기 때문에 맨 마지막에 있는 데이터를 꺼내는 것이 불가능하기 때문에 구현하지 못했습니다. 여기서 말하는 큐는 양방향큐가 아닌 일반..
- 문제 : https://www.acmicpc.net/problem/2573 rowN x colN 크기의 행렬에 빙산과 바다가 표시됩니다. 빙산은 0 이상의 숫자로 바다는 0으로 표시됩니다. 빙산은 바다와 맞닿아 있는 수 많큼 빠르게 줄어들고 빙하가 두조각 이상으로 나뉠때까지 빙하를 녹이는 문제입니다. 문제가 지난번에 풀었던 안전영역과 비슷합니다. 안전영역 문제 및 풀이 : http://inor.tistory.com/26?category=723636 - 풀이 먼저 빙하를 방문했습니다. 방문을 위해 DFS를 이용했고 DFS를 이용한 이유는 빙산이 몇조각으로 나뉘어져 있는지 확인하기 위해서였습니다. 방문 함수를 2번 이상 호출하면 빙하가 2조각 이상이라는 말이고 2번 이상 호출 됐을 경우에 탐색을 종료했습..
- 문제 : https://www.acmicpc.net/problem/1063 8x8 체스판 위에 킹과 돌멩이가 있는데 주어진 조건에 맞게 킹과 돌을 옮기는 문제입니다. 입력으로 킹과 돌의 위치와 킹을 움직이는 방향에대한 정보가 주어집니다. - 풀이 dRow와 dCol 변수를 선언해서 킹이 다음에 이동할 위치를 설정했습니다. 이동 중에 킹이 체스판 범위를 넘어가면 해당 명령은 무시하도록 했습니다. 그리고 돌의 경우에는 킹과 겹칠 경우에 킹과 같은 방향으로 이동시켰습니다. 조건에 맞게 단순히 이동만 시켜주었습니다. 그러나 처음에 문제를 잘못 이해하고 킹과 돌멩이를 동시에 이동 시켰고 오류가 발생했습니다.(예제로 주어진 조건이 같이 움직이거나 문제의 조건대로 정확히 움직이나 똑같은 결과를 보여줘서 시간이 조..
- 문제 : https://www.acmicpc.net/problem/1932 피라미드 모양으로 구성된 숫자들을 특정 기준에 맞게 더할 경우에 나올 수 있는 최대값을 구하는 문제입니다. 숫자는 아래 방향으로 인접한 두 수를 더할 수 있습니다. 문제에대한 정확한 설명을 링크를 참조해주세요. - 풀이 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 모양으로 구성된 피라미드의 경우에 7은 3과 8을 더할 수 있습니다. 7이 3과 8을 더해서 나온 값들인 10과 15의 경우에 10은 8과 1을 더할 수 있고 15는 1과 0을 더할 수 있습니다. 이렇게 더해가는 과정을 반복하면 마지막에 이르게 되는데 그때 최대값을 찾아주면 됩니다. 처음에는 무조건 위에서 아래로 더해주는 경우를 생각했고 2개의 부모와 더..
- 문제 : https://www.acmicpc.net/problem/14890 지도(2차원 행렬)에 지형의 높이가 나와있고 높이가 다른 지형을 경사로를 설치해서 연결하는 문제입니다. 경사로의 높이는 1이고 높이 차이가 1이 나는 지형에만 경사로를 설치할 수 있습니다. 경사로의 길이는 매번 다르며 경사로 설치를 위해 따라야하는 몇 가지 제약 조건이 있습니다. - 풀이 문제의 제약 사항을 분기하고 프로그램을 구현할 수 있는지 확인하는 문제입니다. 문제의 출처에 가보면 4가지 제약 사항이 나오는데, 그 중에서 경사로를 설치한 위치에 다시 경사로를 설치할 수 없다는 제약을 만족 시키기 위해서 boolean 타입의 isSlope[][]을 선언해서 해당 위치에 이미 경사로가 설치된 상태인지 확인했습니다. 그리고 ..
- 문제 : https://www.acmicpc.net/problem/14889 N명(짝수)의 사람들이 팀을 이루는 경우의 수를 모두 구하는 문제입니다. 모든 사람들은 특정 사람과 팀을 이루었을때 시너지 효과(능력치)가 높아지고 낮아집니다. 공평한 경기를 위해 팀을 구성 했을때, 2팀의 시너지 효과 차이가 가장 적은 경우를 찾는 문제입니다. 경우의 수를 구해서 해당 경우에 두 팀의 시너지 효과를 구하면 됩니다. - 풀이 모든 경우의 수를 탐색하기 위해서 깊이 탐색 알고리즘을 사용했습니다. 재귀를 이용해서 깊이 탐색을 했는데 N이 30이 넘어가면 연산이 안되는 경우가 발생했습니다. 이 부분은 추후에 스택으로 바꿔서 결과가 차이 나는지 확인해보겠습니다. 그리고 조합을 구현하기 위해서 중복을 피하는 방법을 사..