목록Algorithm/백준 (21)
Inor
- 문제 : https://www.acmicpc.net/problem/10814 주어진 회원들의 나이 순으로 정렬하고 나이가 같을 경우에는 먼저 등록한 순서로 정렬하는 문제 입니다. 등록한 순서는 입력 순서와 동일합니다. - 풀이 단순하게 나이 순서로 정렬 해주고 입력 순서를 저장했다가 입력 순서대로 정렬해주면 되는 문제인줄 알았습니다. 그래서 퀵 정렬을 2번 사용해서 나이순으로 먼저 정렬해주고, 나이가 같은 배열을 전체 배열에서 left와 right 인덱스로 나눠서 등록 순서로 배열해주었습니다. 그런데 문제를 풀다보니 계속 틀렸다고해서 인터넷을 찾아봤습니다. 알고보니 stable sort라는 것이 있었고 stable sort는 같은 값일 경우에 순서를 바꾸지 않고 정렬해주는 방법이었습니다. 3 2 1 ..
- 문제 : https://www.acmicpc.net/problem/10798 가로로 쓰여진 단어를 세로로 변경하고 빈칸인 부분은 무시해서 이어 붙여주면 되는 문제 입니다. - 풀이 경사로 문제와 비슷하게 해결했습니다. for문에서 row와 col의 위치를 변경해주는 것이 아니라 애초에 위치가 변경된 배열을 선언하고 위치를 재배열 해줬습니다. 그 이후에는 비어있는 공간을 특정 문자로 채우고 특정 문자가 있을 경우에는 건너 뛰어서 계산하도록 했습니다. - 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Reading..
- 문제 : https://www.acmicpc.net/problem/12761 이동 가능한 방법이 총 8개 주어지고 방법에 맞게 동규를 이동 시키는 문제 입니다. 동규가 도착 지점까지 이동한 횟수의 최솟값을 출력하면 됩니다. - 풀이 처음에는 DP 방식으로 문제에 접근했습니다. 만약 앞으로만 이동할 수 있다면 DP를 이용해서 도착지점에서 가장 가까운 위치(도착지점 - 1)에서부터 값을 감소 시키며 시작지점에서 도착지점까지 이동한 횟수를 찾을 수 있다고 생각했습니다. 그러나 뒤로 이동하는 경우에 DP를 이용해서 문제 해결이 불가능했습니다. 예를 들어서 앞으로만 이동 가능하고 도착 지점이 20이고 현재 11번째에서 20까지 갈 수 있는 최단거리를 찾으려고 할때 11과 20 사이의 위치에서 최단으로 20까지..
- 문제 : https://www.acmicpc.net/problem/1992 쿼드트리를 이용해서 4등분된 영역을 압축하는 알고리즘 문제 입니다. - 풀이 처음에는 괄호와 0, 1 값들을 스택에 넣어두고 pop 하면서 압축을 검사하고 다시 스택에 넣는 방법으로 풀려고 했지만 실패했습니다. 애초에 조금 돌아가는 방법으로 판단했고 분할/정복 방식으로 재귀호출하여 문제를 해결했습니다. 이 문제를 풀기에 앞서서 분할 정복에대한 개념을 잡고자 Merge Sort를 공부 했습니다. 그리고 분할/정복 방식의 문제 풀이는 분할이 안될때까지 분할하고 정복(문제를 해결)하면서 문제를 풀어가는 방법과 분할 하기 전에 정복할 수 있는지 확인하고 다음 분할로 넘어가는 방식이 있는데 저는 분할을 하기 전에 정복할 수 있는지 확인..
- 문제 : 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 변수를 선언해서 킹이 다음에 이동할 위치를 설정했습니다. 이동 중에 킹이 체스판 범위를 넘어가면 해당 명령은 무시하도록 했습니다. 그리고 돌의 경우에는 킹과 겹칠 경우에 킹과 같은 방향으로 이동시켰습니다. 조건에 맞게 단순히 이동만 시켜주었습니다. 그러나 처음에 문제를 잘못 이해하고 킹과 돌멩이를 동시에 이동 시켰고 오류가 발생했습니다.(예제로 주어진 조건이 같이 움직이거나 문제의 조건대로 정확히 움직이나 똑같은 결과를 보여줘서 시간이 조..