알고리즘52 [☁️ 구름톤 챌린지] 4주차 학습일지 - 1 문제 16. 연합 전형적인 BFS 문제이다. 이 문제는 BFS에서 queue에 이 다음에 방문할 값을 넣을 때하는 방문 체크에서, 이 다음 값을 방문했는지 확인하는 것이 아닌 현재 값을 방문했는지 계속 확인하는 바람에 틀렸다. 방문 체크하는 값을 바꾸어주니 통과되는 것을 확인할 수 있었다. import java.io.*; import java.util.*; class Main { static int N, M; static int[][] map; static boolean[] visited; static int result; static Queue queue; public static void main(String[] args) throws Exception { BufferedReader br = new .. 2023. 9. 8. P14500. 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 설명 처음 생각한 방법은 테트로미노를 만들 수 있는 경우의 수를 모두 계산하여 풀이하는 방법이다. 하지만 너무 복잡하다. 이 문제는 테트로미노를 만들 수 있는 경우의 수를 두가지로 나누어 풀이할 수 있다. 1. ㅜ 모양이 아닌 경우 👉 dfs로 탐색한다. 2. ㅜ 모양인 경우 👉 직접 좌표를 계산하거나, 조합으로 풀이한다. 1. ㅜ 모양이 아닌 경우 노란 칸: 탐색 시작 칸 파란 칸: dfs로 탐.. 2023. 9. 5. P9375. 패션왕 신해빈 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 설명 처음 시도 조합으로 각 경우의 수를 구하고 만들어진 조합끼리 값을 곱하여 result를 구했다. but! 시간초과 발생⚡️ ➡️ 생각해보면 각 조합을 모두 구할 필요는 없다! 우리는 경우의 수만 구하면 되기 때문이다. 다음 시도 각각의 종류가 가질 수 있는 경우의 수에 NULL(안 입을 경우)을 추가.. 2023. 9. 3. [☁️ 구름톤 챌린지] 3주차 학습일지 - 2 문제 13. 발전기 (2) 바로 앞에서 푼 발전기 문제와 비슷하다고 생각할 수도 있지만, 다르다. 건물 유형 번호를 출력하는 것이기 때문에, count 배열로 건물 유형에 따른 건물 개수를 저장하고 비교를 통해 해당 index를 출력한다. 보통 BFS는 visited 배열을 따로 두어 방문 표시를 하는데, 이 문제에서는 map 배열에 값을 저장해서 새롭게 배열을 생성하지 않고 방문 표시를 한다는 점이 신선했다. import java.io.*; import java.util.*; class Main { static int N, K; static int map[][]; static int result = Integer.MIN_VALUE; static int count[]; static Queue queue;.. 2023. 9. 3. P9019. DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 설명 하나의 경우를 깊이있게 들어가기보다 주변을 탐색하는 BFS 기법을 이용해서 문제를 풀이한다. visit 배열을 생성하고, 방문한 값들은 true로 변경한다. D연산 num을 2배 했을 때 9999보다 크면, %10000을 하는 것과 9999 이하일 때 %10000하는 것은 같다. => num * 2 % 10000 S연산 n == 0이면, 9999를 반환한다. => n == 0 ?.. 2023. 9. 2. P7662. 이중 우선순위 큐(priority queue, treemap) https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 설명 1️⃣ Priority Queue Priority Queue란? 큐(Queue)는 우선순위를 결정하고, 우선순위가 높은 원소가 먼저 나간다. 우선순위 큐는 힙을 이용하여 구현한다. 데이터 삽입: 우선순위를 기준으로 최대힙, 최소힙 구성한다. 데이터 삭제: 루트 노드 제거 후 빈 루트 노드 위치에 맨 마지막 노드를 삽입하고 아래로 내려가면서 적절한 자리를 찾아 옮긴다. 내부 요소는 힙으로 .. 2023. 9. 2. [☁️ 구름톤 챌린지] 3주차 학습일지 - 1 문제 11. 통증 (2) dp문제이다. dp문제는 일단 한번 쭉 써두고 규칙을 찾아서 푸는 경우가 많은데 이 문제도 역시 마찬가지다. 여기서 이해하기 어려웠던 것은 dp[i-A]의 경우다. 예를들어, i가 11이고 통증의 사이즈가 2, 7이라면 11 = 2 * 2 + 7로 해결할 수 있다. 이때, 11 = 2 * 2 + 7 = dp[4] + 1로 나타낼 수 있다. - dp[4]가 의미하는 바는 11에서 7을 뺐을 때, dp[4]로 계산할 수 있는 것을 말하고 - 1은 2*2 + 7에 있는 7을 말한다. import java.io.*; import java.util.*; import java.math.*; class Main { static int N, A, B; static int dp[]; public.. 2023. 8. 31. P6064. 카잉 달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 설명 1️⃣ 번째 풀이 x, y에 도달할 때까지, 모든 경우의 수를 계산하여 시간초과가 발생했다. 2️⃣ 번째 풀이 나머지가 0인 경우를 찾아 풀이한다. 예를들어, k=33이라면 m,n,x,y는 10, 12, 3, 9로 주어졌다. - 33에서 x를 빼고 m으로 나눈 것: (33-3) % 10 = 0 - 33에서 y를 빼고 n으로 나눈 것: (33-9) % 12 = 0 => 모두 나머지가 0이다. 즉 .. 2023. 8. 28. [☁️ 구름톤 챌린지] 2주차 학습일지 - 2 문제 8. 통증 그리디 문제이다. 그리디 문제의 대명사인 '동전' 문제처럼 가장 큰수부터 빼가면서 문제를 풀이하면 된다. import java.io.*; import java.util.*; class Main { static int N; static int[] items = {1, 7, 14}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); int result = 0; int i = items.length-1; while(N > 0) { if(N == .. 2023. 8. 27. 이전 1 2 3 4 5 6 다음
