Inor

- 문제 : https://www.codeground.org/practice/practiceProblemView (codeground에 로그인 해야지 열람 가능합니다.) 최소 비용을 찾는 문제입니다. 전체 경로와 각 경로마다 비용과 할인권이 주어집니다. 시작 위치에서 도착 위치까지 이동하는 모든 경로 중, 가장 비용이 적게 드는 경로에서 지불해야하는 비용이 할인권보다 많으면 할인권을 구매합니다. P(1

- 합병 정렬 분할 정복 기법을 사용한 정렬 알고리즘 입니다. 분할 정복 기법은 분할하면서 정복하는 방법과 분할이 끝날때 까지 분할 하고 합치면서 정복하는 방법이 있습니다. 합병 정렬은 분할이 안될때까지 분할 한 후에 합병하며 정렬하는 방식입니다. 분할하는 방법과 병합하는 방법을 그림으로 설명하겠습니다. 1. 분할 4 7 6 2 5 3 1 8 먼저 전체 배열을 반으로 나눕니다. 4762 531 8 이후에 반으로 분할이 안될때까지 분할을 반복합니다. 2. 정복 정복하면서 분할된 공간끼리 정렬을 합니다. 47625 31 8 먼저 파란색 영역의 4와 7 값을 비교해서 4를 7의 앞에 위치하도록 해줍니다. 6과 2의 경우에는 2가 6보다 작으니 2를 6의 앞에 위치 시켜줍니다. 이러한 방법으로 (5,3)과 (1..

- 문제 : 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를 공부 했습니다. 그리고 분할/정복 방식의 문제 풀이는 분할이 안될때까지 분할하고 정복(문제를 해결)하면서 문제를 풀어가는 방법과 분할 하기 전에 정복할 수 있는지 확인하고 다음 분할로 넘어가는 방식이 있는데 저는 분할을 하기 전에 정복할 수 있는지 확인..