Algorithm
백준[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번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수..
백준[7569] - 토마토
문제: https://www.acmicpc.net/problem/7569 분류: 그래프 탐색, BFS 난이도: G5 소요시간: 20m 자아성찰: N, M, H 3차원 배열에 대해 BFS을 이용해 풀 수 있는 문제로, 모두
백준[16173] - 점프왕 쩰리 (Small)
문제: https://www.acmicpc.net/problem/16173 분류: 그래프 이론, BFS, DFS, 브루트포스 난이도: S4 소요시간: 10m 자아성찰: 맵의 크기가 N x N (N 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import ..
백준[16435] - 스네이크버드
문제: https://www.acmicpc.net/problem/16435 분류: 정렬, 그리디 난이도: S5 소요시간: 5m 자아성찰: 이전에 알고리즘을 풀었을 때에도 그리디에 많이 약했었다. 가장 기초적인 그리디에 대해 다시 이해하고자 쉬운 문제로 골랐다. 내 기준 그리디의 핵심은 '문제를 스스로 꼬아 풀지 말자' 인데, 이 문제가 그 핵심을 잘 적용할 수 있었던 문제인 것 같다. N 단순하게 정렬로 가장 높이가 낮은 과일부터 차례대로 먹어가며 길이를 늘린다. 문제가 아무리 어려워보여도 일단 단순하게 생각하는 습관을 길러보자. (브루트포스, 그리디) 단순함을 잘 사용하면 생각보다 쉽게 풀린다! 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기..