[문제]https://www.acmicpc.net/problem/1600 [문제 풀이]이런 게임 같은 문제가 나오면 풀 때도 재밌는 것 같다. 이 문제는 원숭이가 체스판에 말처럼 움직일 수 있는 횟수가 정해져있고, 그 횟수를 모두 소진하면 평소 원숭이처럼 상하좌우로 밖에 움직일 수 없게된다. 이 문제를 풀 때 키 포인트는 도착지점 말고 중간지점을 먼저 왔다고 해서 그게 최적의 루트가 아닐 수 있다는 것이다. 보통 BFS 문제를 풀 때 2차원 격자판이 주어지면 방문 배열도 2차원으로 했다면 이 문제는기존 2차원 vis[r][c]면 “어떤 남은 말 이동 횟수든 한 번만 방문”으로 처리돼서,나중에 말 이동 횟수가 더 많은 상태로 왔을 때도 “이미 봤으니 패스" 해버린다. 따라서,3차원 vis[r][c][rem..

[문제]https://www.acmicpc.net/problem/1377 [문제 풀이]버블 소트는 인접한 원소끼리 한 번에 한 칸씩만 교환하면서 정렬을 진행한다. 즉, 어떤 값이 제자리(정렬됐을 때의 인덱스)보다 뒤쪽(정렬되기 전의 인덱스가 큰 쪽)에 있다면, 한 패스당 한 칸씩 앞으로(인덱스가 작은 쪽으로) 이동하게 된다. 버블 소트 동작 복기한 패스가 끝나면 가장 큰(혹은 작은) 하나의 원소가 제자리로 간다.각 원소는 본래 위치에서 정렬된 위치까지 ‘인접 교환’으로만 이동하므로, 패스 수 = 그 요소가 이동해야 하는 칸 수 버블 소트는 정렬이 마무리 된 상태에서 정렬이 마무리가 됐는지 확인을 한 번하고 정렬이 됐으면 정렬을 마치므로, 이 문제는 버블 정렬이 몇 번 일어나는지를 묻는 문제이기 때문에 ..

[문제]https://www.acmicpc.net/problem/11286 [문제 풀이]1. 선언 및 생성import java.util.PriorityQueue;// 오름차순(기본) : 작은 값이 우선순위 높음 (최소 힙)PriorityQueue pq = new PriorityQueue();// 내림차순 : 큰 값이 우선순위 높음 (최대 힙)PriorityQueue maxPq = new PriorityQueue(Collections.reverseOrder()); 2. 주요 메서드메서드 설명add(e)요소 추가(예외 발생)offer(e)요소 추가(성공/실패 반환)poll()우선순위 가장 높은 값 꺼냄(없으면 null)peek()우선순위 가장 높은 값 확인(삭제X)isEmpty()비어있는지 확인size(..

[문제]https://www.acmicpc.net/problem/11003 [문제 풀이]이 문제는 처음에 덱을 이용하지 않고 풀었다가 시간초과가 났다..그 후에 최적화할 수단을 도저히 모르겠어서 지선생님의 도움을 좀 받았다. 처음 풀었던 코드는 현재 최솟값이 슬라이딩 윈도우 범위를 넘어설 때만 새로운 최솟값을 찾으므로 시간복잡도가 오버 될거라 생각을 안했는데 최악의 상황에서 계속 최솟값을 찾아야 한다면 O(N*L) 이 나오는 불상사가 발생했다. 이 문제를 해결하기 위해서 필요한게 자료구조 Deque이다.이 문제는 해당 구간의 최솟값을 관리해야 하는데 이 정렬을 Deque으로 관리했다. 수 입력을 받으면서 Deque에다 삽입한다. Deque에는 숫자와 index를 저장하는 Num 클래스를 만들어서 관리했다..

[문제]https://www.acmicpc.net/problem/12891 [문제 풀이]동일한 길이의 구간을 한 칸씩 옮기면서 검사하는 슬리이딩 윈도우 문제이다. 처음에 검사를 할 때 한 칸씩 옮긴 구간을 계속해서 새로 검사했는데 바로 시간초과가 났다. 그 후에 생각했던게 GATA 일 때부분문자열의 길이가 2라면 GA AT TA 이런 식으로 검사를 하게 되는데겹치는 부분이 존재한다. 시간복잡도를 줄이기 위해 겹치는 부분을 다시 검사하는 일을 없애기 위해 add와 delete 메서드를 만들어서 그 부분을 해결했다. 그러고도 틀렸다고 떴는데 그 이유는 A,C,G,T 가 들어가는 개수가 같아야 하는게 아니라 최소의 개수라는 문제 조건을 까먹어서 Arrays.sort(count,current)를 해서..

[문제]https://www.acmicpc.net/problem/1253 [문제 풀이]전에 풀었던 투포인터 문제와 거의 비슷하다.거기에 조건 하나만 추가해주면 되는데문제에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. 라고 했으므로포인터가 N 인덱스와 같아질 때는 그대로 다음 인덱스로 넘기기만 하면 된다.[정답 코드]import java.util.*;import java.io.*;public class Boj_1253 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

[문제]https://www.acmicpc.net/problem/2018 [문제 풀이]이 문제는 연속된 자연수의 합이 N이 되는 경우의 수를 찾아야 한다.자연수 N의 범위가 (1따라서 시간 복잡도를 줄이기 위해 투 포인터라는 알고리즘을 이용해서 풀어야 한다. 해당하는 범위를 찾기 위해 시작 값을 start, 종료 값을 end로 두면 sum (합이 N보다 작기 때문에 다음 큰 값인 end를 +1 한다.) sum > N 일 때, sum-=start, start++(합이 N보다 크기 때문에 구간에서 작은 값인 sum-start를 하고 그 다음 구간으로 옮긴다.) sum == N 일 때, answer++, end++, sum+=end(end++을 안하게 되면 계속 그 자리에 있게 된다. 따라서 answer 값..

[문제]https://www.acmicpc.net/problem/10986 [문제 풀이]일단 여기서 중요하게 짚고 넘어가야 할 것은 int형의 범위는 10⁹ 까지라는 것이다...따라서 answer 또한 long 형으로 바꿨어야 했는데 그것을 못 찾고 애꿎은 풀이과정만 계속 봤다.. 이 문제는 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 경우의 수를 구하는 문제이다. 따라서 맨 처음에 주어지는 수들의 구간 합을 구한다. 그 후 구간 합 배열의 원소 값을 돌면서 M으로 나누었을 때 나머지가 0이라면 arr[0]부터 arr[i]까지 구간 합이 나머지가 0이라는 뜻이므로 answer++을 해준다. 이제 arr[i] ~ arr[j] 등과 같은 중간의 있는 구간 합 중에 나머지가 0이 되는 경우를 찾아야..

[문제]https://www.acmicpc.net/problem/11660 [문제 풀이]첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)문제의 시간 제한을 보면 1초인데 조건을 살펴보면 N이 2¹⁰ 까지이고 N*N이면 최대 2²⁰ 인데 이러면 이미 1초이다. 거기에 합을 구하는 횟수가 100,000이니 구간 합을 구할 때마다 처음부터 일일히 합을 다 구하면 바로 시간초과가 난다. 따라서 이 문제는 구간 합을 이용해서 풀어야 한다. 이 문제는 2차원 배열이기 때문에 2차원 배열의 구간 합을 구할 수 있어야 한다. 또한 (1,1)로 시작하기 때문에 배열의 크기를 [n+1][n+1]로 하는 것을 잊지 말자. 이 문제는 (1,1)부터 시작..