본문 바로가기

Algorithm

백준 2110 공유기 설치 Java 2019. 5. 24. 이분탐색 문제인 공유기 설치 문제이다. 난 문제를 이해하는 것도 헷갈렸다.. 요즘 문제 이해하기가 넘 힘들다.. 문제의 요점은 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하는 것인데 예제에서는 3개의 공유기를 설치하고 1 2 8 4 9 에서 최대 거리가 3이다. 나는 1 4 9 에 설치하면 최대 거리가 5인데?.. 이러고 있었다. 문제는 그게 아니라 공유기 3개를 설치할 때 최대 거리가 3인 이유는 1에 설치 4에 설치 7이상에 설치가 가능한데 8과 9가 있으니 3개가 설치가 가능하고 그 최대 거리가 3인 것이다. 만약 최대 거리가 4이면 1 -> 설치 2 -> 설치 불가 4 -> 설치 불가 8 -> 설치 9 -> 설치 불가(8에서 설치했으니 13이상의 수만 설치가능) 정리하자면 마..
백준 1654 랜선 자르기 Java 2019. 5. 23. 이분 탐색 문제인 랜선 자르기 문제이다. 이미 가지고 있는 랜선 개수 인 k와 만들어야 하는 랜선 개수 n 그리고 k개 만큼의 랜선 길이가 주어진다. 모두 똑같은 길이로 n개의 개수만큼 랜선을 자르려고 할때 최대 길이를 출력하면 된다. 랜선 길이의 최대값이 2^31 -1 이기 때문에 길이를 1부터 최대 길이까지 다 잘라보고 n이상인 것 중 최대값을 찾는 방식으로 풀면 시간 초과가 나올 것이다 어쨌든 길이를 정하고 잘라보면서 개수를 n과 비교하며 찾아야 하는것은 맞다. 범위를 줄여나가는게 중요한 것 같다. 찾아볼 범위의 시작을 start라고 하고 범위의 끝은 end라고 하겠다. 처음에는 당연히 start = 1 일 것이고, end는 랜선길이중 최대값 일 것이다. 그리고 일단 start와 end의 중간값으로..
백준 2261 가장 가까운 두 점 Java 2019. 5. 23. 정답률 15퍼센트의 가장 가까운 두 점 문제이다. 정답률에서도 알 수 있듯이 굉장히 어려운 문제인 것 같다.. n의 최댓값이 100000, 십만으로 O(n^2)으로 비교하는 간단한 알고리즘으로는 절대 풀 수 없다. 당연히 나도 풀 수 없었고, 백준님의 강의를 토대로 '분할 정복'으로 푼 가장 가까운 두 점 문제를 정리하려고 한다. 푸는 방법은 이렇다. x좌표 순으로 정렬을 한다. 그리고 중간 인덱스를 기준으로 왼쪽에서 가장 가까운 두점 사이의 거리를 찾고 오른쪽에서 가장 가까운 두점 사이의 거리를 찾는다. 왼쪽에서 구한 값과 오른쪽에서 구한 값 중 더 작은 값을 저장한다. 중간값을 기준으로 왼쪽, 오른쪽에서 가장 가까운 두점 사이의 거리는 찾았다. 남은 것은 중간값을 지나는 왼쪽 점과 오른쪽 점 사이의 ..
백준 7571 점 모으기 Java 2019. 5. 22. 정보올림피아드 easy 문제집에서 만난 점모으기 문제이다. n * n의 배열에 점의 좌표가 주어지고 점이 상 하 좌 우로 움직일 수 있을 때 점들이 한곳에 모이는 가장 최단 거리를 출력하는 문제이다. 최단거리면 당연히 BFS라고 생각하고 BFS로 풀었다가 메모리 초과, 시간초과의 늪에 빠졌다. 다시 문제를 보니까 거리를 구할 때 굳이 BFS로 가지 않아도 점의 좌표값과 모일 곳의 좌표값을 뺀 후 절대값으로 만들면 거리를 구할 수 있는 것을 발견한 후 n*n의 배열의 모든 경우에 m만큼의 좌표만큼 거리를 더하고 최솟값을 출력했다. 결과는 시간초과였다. 어떻게보면 당연히 시간초과인데 이 방법말고는 생각이 나질 않았다. 그렇게 포기하고 답을 찾아봤는데 해결법은 중앙값을 구하는 것이였다. 좌표값이 주어질 때 x..
백준 1517 버블 소트 Java 2019. 5. 22. 정답률 26퍼센트의 분할정복 문제이다. 내 티스토리 sort카테고리에도 있는 코드를 주고 더이상 정렬할 게 없을 때 몇단계인지 출력하는 그 버블 소트 문제와는 다른 문제이다. 다들 알겠지만 N의 최대값이 500,000 오십만이기 때문에 진짜 버블소트 코드로 swap의 횟수를 세면 시간 초과가 나온다. 버블소트는 O(n^2)이고 N이 오십만 이기 때문에 연산 횟수가 너무 많아진다. 당연 나와 같은 초보들은 해결법을 떠올릴 수 없을 것이다.. 이 문제는 머지소트를 이용해서 해결한다. 머지소트에서는 배열을 middle값 기준으로 나눠서 merge를 통해 정렬한다. merge는 하나의 배열을 middle 인덱스를 기준으로 반 반 나누어서 값이 더 작은 쪽이 임시 배열에 순서대로 저장된다. 이 문제는 이 merg..
백준 2631 & 7570 줄 세우기 Java 2019. 5. 22. 문제는 간단하면서도 나에게는 어려운 문제들이다. dp로 풀지않더라도 풀 수 있는 문제들이지만 dp로 푸는 것이 더 간단하다고 생각이 들어 정리 하려고 한다. 2631번 문제와 7570문제는 같은 듯 하면서도 다른 문제이다. 2631번 문제의 경우엔 5 2 4 1 3 등 마구잡이로 주어진 수에서 수를 아무렇게나 옮겨서 정렬된 배열을 만들 때 최소 횟수이고 7570번 문제의 경우엔 5 2 4 1 3 등 마구잡이로 주어진 수에서 수를 맨 앞이나 맨 뒤로만 옮겨서 정렬된 배열을 만들 때 최소 횟수이다. 이 문제 들은 가장 긴 증가수열 알고리즘(LIS)을 활용해서 해결하면 된다. 사실 문제들을 보고 가장 긴 증가수열 알고리즘을 활용해서 풀어야 된다는 사실을 깨닫지 못했다. 2631번 문제의 경우엔 수를 아무곳으로..
백준 1074 Z Java 2019. 5. 20. 정답률 42퍼센트의 분할정복문제 Z이다. 배열을 만들어서 재귀호출로 숫자를 일일이 셌더니 바로 메모리초과가 나왔고 배열을 안만들고 재귀호출로 숫자를 일일이 세서 r과 c가 되면 멈추도록 했더니 시간 초과가 나왔다. 재귀호출로 숫자를 세서 시간초과가 안나왔다는 사람들도 있지만 내가 짠 코드는 시간초과가 계속 나왔다.. 쨋든 성공한 사람들의 코드를 보니 일일이 세지 않고 r과 c를 보고 영역을 찾아가는 식으로 짰다. x와 y를 현재 위치라고 생각하고 계속 해서 r과 c를 비교하며 영역을 찾아간다. 2영역 인경우엔 2영역에서 또 4분할 하여 영역을 찾아가야 하므로 n+x 또는 n+y로 비교한다.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..
백준 2263 트리의 순회 Java 2019. 5. 20. 트리문제이기도 하지만 분할정복으로 문제를 해결하므로 분할정복 카테고리에 삽입한 정답률 37퍼센트의 트리의 순회 문제이다, 문제는 1부터n까지 번호의 트리가 있을 때 인오더와 포스트오더가 주어지고 프리오더로 출력하면 되는 문제이다. 트리의 탐색 방법인 프리오더, 인오더, 포스트오더에 대해 까먹었었는데 이번엔 정말 외워야 겠다. preOrder(프리오더) - Root, Left, Right순으로 방문한다. inOrder(인오더) - Left, Root, Rigth순으로 방문한다. postOrder(포스트오더) - Left, Rigth, Root순으로 방문한다. 이런 자료구조가 있을 때 프리오더는 1 2 4 5 7 3 6 인오더는 4 2 7 5 1 3 6 포스트오더는 4 7 5 2 6 3 1 인 것이다. 문제..

티스토리툴바