알고리즘/백준

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net > 의식의 흐름 10일 전에 풀었던 문제를 복습할겸 풀었는데 계속 메모리 초과가 나서 멘탈이 탈탈,,, wDeque에 Location을 추가하는 부분에서 두더지굴만 아니면 될거라는 생각에 if (map[nx][ny] != 'D') { visited[nx][ny] = true; map[nx][ny] = '*'; // 물로 변경시켜주기 wDeque.add(new Location(nx, ny)); } 라고 작성했고 무한루프에 빠져서 메모리 초과가 나온 것 같다. => 아예 비어있..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net > 의식의 흐름 priority queue와 deque을 같이 쓰면 괜찮지 않을까?라는 생각과 함께 시도했으나 시간 초과,,, 시간복잡도가 괜찮은줄 알았는데 "priority queue의 remove(Object o) 시간복잡도 = O(N)" 이었고 결과적으로 O(N*N)의 시간복잡도를 가지게 되어 시간 초과가 난 것이었다. 어떻게 하면 시간복잡도를 줄일 수 있을까 고민고민했지만 결국 포기하고 풀이를 찾아봤당😅 > 풀이 ** deq..

17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 의식의 흐름 돌려야하는 줄들만 이동시키면 될 것 같아서 n이랑 i로 표현해보고 대입시켜줬다. 근데 중간에 반대로 집어넣어서 꼬이는 바람에 헤맸다... 풀이 1. 배열의 크기 n과 각도 d 입력 받기 d가 음수인 경우 360을 더해 양수로 변경함 2. 2차원 배열 2개(originalArr, modifiedArr)를 생성한다. 3. 2차원 배열을 회전 (d/45)번 45도로 회전 한번 회전시킬 때마다 originalArr값을 modifiedArr값으로 변경 코드 import java.io.*; import java.u..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 의식의 흐름 두 포인터 사용해서 배열 다 돌리면 되겠는데? -> 오답 알고보니 두 수를 합할 때 target으로 잡은 수는 두 수에 포함이 안되어야 하는데 그 부분을 확인하지 않았다.. 그것만 고치니까 정답 풀이 1. 배열에 수 담은 후 정렬 2. 배열 0 ~ N까지 차례대로 target으로 잡고 두 수로 나타낼 수 있는지 확인 두 포인터가 가리키는 수들의 합 > target) 큰 수 가리키는 포인터 왼쪽으로 두 포인터가 가리키는 수들의 합 < target) 작은 수 가리키는 포인터 오른쪽..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 의식의 흐름 구간 합이 뭔지 제대로 공부 안하고 무작정 풀어보기 -> (시간제한 안보고) 그냥 인덱스로 for문 돌리면 되는데 왜 실버지? -> 시간초과ㅎ... 풀이 1. 부분 합 배열 만들기 2. 인덱스 받아서 부분 합 적절하게 사용하기 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExcep..

1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 의식의 흐름 (게임을 더하면 이긴 게임(Y)만 늘어나는게 아니라 게임 횟수(X)도 늘어나는걸 생각 못하고,,,) 1~X-Y번 이분 탐색 돌리면 되겠네 라고 했다가 7번의 "틀렸습니다"를 보고 정신차림. 혹시나 하고 end = X로 고쳤더니 바로 통과해버렸당. 근데 아직까지 왜 end = X인지 이유를 명확히 모르겠다👻 풀이 1. Z가 99%인 경우, 게임을 아무리 해도 승률이 100%가 되지 못하므로 해당 경우는 바로 처리 2. 99% 아래인 경우, 이분..

16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 의식의 흐름 A에서 B로 가면 경우의 수가 너무 많을 것 같으니까 B에서 A로 가볼까..? 일의 자리가 1이거나 짝수일 때만 연산 가능하니까 그 경우만 처리해주고 나머지는 -1이겠지! 풀이 B를 A로 만들기 도전 1. B의 일의 자리가 1인 경우 1을 없애주고, B가 짝수인 경우 2로 나누어준다. 만약, 2가지 경우 중 하나에 포함되지 않는 경우(ex. 일의 자리가 3인 경우)는 A로 만들지 못하는 경우이므로 -1 출력 2. 1번 연산을 B