알고리즘

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net > 의식의 흐름 해시맵 써서 정렬하고 어찌저찌,, > 풀이 1. HashMap(key = 종 이름, value = 입력된 횟수)을 이용하여 종 이름이 몇 번 입력되었는지 저장한다. 2. 1번 과정을 입력 끝날 때까지 반복 // 입력 끝날 때까지 반복 while((type=br.readLine())!=null && !type.isEmpty()){ //... } 3. HashMap의 키값들(종 이름)을 사전순으로 정렬한다. 4. 정렬된 순서대로 해당 종이..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net > 의식의 흐름 한 칸에 대한 주변 8칸에 겹치는 수가 있으면 안되는 것이라고 착각하고 풀었다가 틀렸습니다가 잔뜩,,, 한 칸에 대한 주변 8칸이 아니라 특정 영역의 정사각형 내에 겹치는 수가 있으면 안된다는 것을 깨닫고 로직을 고쳤더니 통과했다 > 풀이 1. map[][] 입력 받는다. 이때, 빈 칸의 위치를 ArrayList에 담아둔다. 2. 백트래킹 활용 Location loc = blanks.get(idx); for(int i=1;i 코드 import j..

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..

# 최소 공통 조상 (LCA) 정점 A와 정점 B가 각각 자신을 포함하여 초상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 구하기 처음 아이디어 = 정점의 부모를 따라 1칸씩 올라가자 시간 복잡도 = O(N) => 어떻게 더 빠르게 찾을 수 있을까? 1칸씩 올라가는 것이 아닌 2^K씩 올라가자 => 시간 복잡도 = O(logN) 이때 다른 수도 아닌 2^K인 이유는??? 모든 수는 이진수로 나타낼 수 있기 때문에 parent[0][V] = 정점 V의 1(=2^0)번째 부모 parent[1][V] = 정점 V의 2(=2^1)번째 부모 ★ = 정점 V의 1번째 부모의 1번째 부모 ★ => parent[1][V] = parent[0][ parent[0][V] ] ★★ parent[K][V] = p..

# 플로이드-워셜 알고리즘 모든 정점 사이의 최단 경로를 구하는 알고리즘 순환만 없다면 음수 가중치도 가능 동적계획법으로 접근 dist[i][j] = Math.min( ~ , ~ ) 형태를 가짐 N개의 정점을 가진다고 할 때, 모든 정점으로 가는 최단 거리를 확인하므로 시간복잡도 = O(N^3) N이 200~300 이하인 경우에만 가능 # 코드 1. INF 값으로 세팅 public static final int INF = 1_000_000_000; INF 값을 Integer.MAX_VALUE로 설정하는 경우, 연산 과정에서 overflow 발생하는 문제 종종 있음 => 잘 확인해서 INF 값 적당히 크게 설정하기 for(int i=1;i

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..