Algorithm
백준[2638] - 치즈
문제: https://www.acmicpc.net/problem/2638분류: 그래프탐색, DFS난이도: G3소요시간: 20m자아성찰:DFS, BFS 등 그래프 탐색을 활용한 풀이가 필요한 문제."치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 간주한다" 를 어떻게 판단할지 고민치즈 내부 공간임을 어떻게 판단할것인가?"모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 문장에서 감을 잡았다.0,0부터 DFS를 통해 거쳐갈 수 있는 모든 칸은 외부 공기로 마킹한다.매 time마다 0,0부터 DFS를 통해 외부 공기를 마킹한 후 -> 다시 map을 돌며 각 위치한 치즈에 대해 4방향 외부공기 확인 (4방향에 마킹된 칸 >= 2일 경우 치즈 녹임)import java.io.Buff..
백준[2583] - 영역 구하기
문제: https://www.acmicpc.net/problem/2583분류: 그래프탐색, DFS난이도: S1소요시간: 15m자아성찰: 요새 그래프 탐색 관련해서 모두 BFS로만 했던 것 같아 DFS 연습을 위해 골라봤다.int[M][N] 순서가 불편해 N, M 순서로 바꾸어도 문제가 없을 것 같아 바꾸어 풀었다.최초 벽의 위치를 1로 마킹 -> 맵을 돌며 마킹 안한 부분부터 DFS 수행 -> dfs 호출 될 때마다 현재 영역 count++정석적인 DFS 풀이로 풀리는 문제이며, 상하좌우 이동에 대해서는 dx, dy 배열을 선언하는 게 편하다. 문득 stream을 써보고 싶어서 Collections.sort 말고 stream().sorted().forEach()로 결과를 출력했다. import jav..
백준[2012] - 등수 매기기
문제: https://www.acmicpc.net/problem/2012분류: 그리디, 정렬난이도: S3소요시간: 10m자아성찰:꽤나 단순한 그리디 문제였다.예상등수와 실제 등수의 차이의 합을 최소화 하는 문제예상등수를 높게 생각한 학생에게 높은 등수를 줄수록 차이의 합이 최소가 된다. (그리디)예상등수를 오름차순 정렬 -> 예상등수 순으로 등수를 매겨 차이 합 구함이 때, 중요한 것은 정답의 최댓값이었다.N = 500000이므로 모두가 1등을 예상할 경우 정답의 최댓값은 int 범위를 훌쩍 넘어가버린다.0 + 1 + 2 + ... + 499,999 = 약 1250억맞왜틀 => 정답의 범위를 확인해보자 public class B_2012 { static int N; static int[] ar..
백준[11509] - 풍선 맞추기
문제: https://www.acmicpc.net/problem/11509 분류: 그리디 난이도: G5 소요시간: 40m 자아성찰: 그리디, DP는 여전히 어렵다. 왼쪽에서 오른쪽으로만 화살을 쏠 수 있다는 조건을 통해 그리디 문제인 걸 알았다. 현재 위치에서 반드시 풍선을 터뜨려야 한다. 배열의 index를 풍선 높이로, index의 값을 해당 높이에 남아있는 화살 수로 접근했다. 현재 위치의 풍선 높이에 해당하는 화살이 존재한다면 (arr[H] > 0), 해당 화살은 사라지고(arr[H] --) 높이 - 1의 화살이 생긴다. (arr[H - 1]++) 현재 위치의 풍선 높이에 해당하는 화살이 존재하지 않는다면(arr[H] = 0) 새 화살을 쏘고 높이 - 1의 화살이 생긴다. (arr[H - 1]++..
백준[15787] - 기차가 어둠을 헤치고 은하수를
문제: https://www.acmicpc.net/problem/15787 분류: 비트마스킹 난이도: S2 소요시간: 20m 자아성찰: 명령 형태를 보고 긴가민가 했는데, "이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다." 조건에서 비트마스킹임을 확신했다. 최대 10만 개의 기차에 대해서 20개의 칸을 모두 비교하는 건 시간복잡도가 용서하지 않으므로, 비트마스킹을 통해 단순히 Integer 값으로 치환해 중복 여부를 판단해 시간복잡도를 줄일 수 있었다. Set를 통해 굳이 List.contains() 메서드를 사용하지 않고 중복을 제거했다. 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 1000..
백준[17352] - 여러분의 다리가 되어 드리겠습니다!
문제: https://www.acmicpc.net/problem/17352 분류: Union-find 난이도: G5 소요시간: 10m 자아성찰: 유니온 파인드 구현 연습 차 풀어보았다. 유니온 파인드의 원리가 생각보다 이해하기 쉬웠어서 union(), find() 메서드를 금방 떠올려 낼 수 있었다. 이래서 이해 >>>> 단순 암기라고 하는 것 같다. N-2개 다리 = 무조건 2개 그룹으로 나누어진다 = 1번 섬과 이어지지 않은 하나의 섬을 찾아서 이어주면 끝이다 시간복잡도는 O(N) find의 경우 경로 압축(parent[a] = find(parent[a])) 을 통해 find 시 parent를 업데이트 하도록 하면 시간복잡도는 상수로 처리된다.
백준[4179] - 불!
문제: https://www.acmicpc.net/problem/4179 분류: BFS 난이도: G4 소요시간: 20m 자아성찰: BFS 사용 접근법은 맞았으나 방문처리를 깜빡해서 79%에서 계속 실패하고 시간이 오래 걸렸다. 접근법 : 불 위치를 큐에 우선으로 넣어 이동 및 방문처리 -> 지훈이 위치 이동 및 방문처리 최초 지훈이 위치(J) 및 불들의 위치(F)에 대해서도 방문처리를 해주었어야 하는데 이걸 놓쳐서 한참 헤맸다. BFS 문제는 구현 자체는 까다롭지 않으나, 문제 조건에 따른 방문처리, 추가적인 플래그 작업 등에 신경쓰도록 하자.! 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 ..
백준[15927] - 회문은 회문아니야!!
문제: https://www.acmicpc.net/problem/15927 분류: 문자열 난이도: G5 소요시간: 10m 자아성찰: 문자열,, 분류의 문제라기보단 팰린드롬의 성질을 알면 쉽게 풀 수 있는 문제가 아니었을까 싶다. 시간복잡도는 문자열의 길이
백준[11060] - 점프 점프
문제: https://www.acmicpc.net/problem/11060 분류: DP 난이도: S2 소요시간: 15m 자아성찰: 브루트포스 느낌이 나는 DP 문제인 것 같다. 이전 계산 기록을 기반으로 불필요한 연산을 하지 않도록 하는 매커니즘은 DP가 맞고, 각 미로에 대해 이동할 수 있는 만큼 최소 점프 횟수를 하나하나 체크하는 매커니즘은 브루트포스 느낌이다. 시간복잡도는 각 미로(N
백준[2776] - 암기왕
문제: https://www.acmicpc.net/problem/2776 분류: 이분탐색, 자료구조 난이도: S4 소요시간: 10m 자아성찰: 문제유형을 이분탐색으로 보고 들어왔는데, 로직 상 Hash 자료구조를 쓰는 방식이 더 빠르고 로직도 간단할 것 같다는 생각이 들었다. 이분탐색 시간복잡도 O(log N) Hash 자료구조 contains 시간 복잡도 O(1) 이분탐색 방식으로도 풀어보고, Hash 자료구조를 통해서도 풀어보았다. 예상대로 이분탐색은 1704ms / Hash 자료구조는 1600ms가 나왔다. 여러 방식으로 풀이가 가능할 때는, 시간적 여유가 된다면 가능한 방식으로 다 풀어보자. 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수..