본문 바로가기

전체 글108

[☁️ 구름톤 챌린지] 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.
P5525. IOIOI 문제: https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 설명 50점 풀이 첫번째 풀이는 부분 문자열(P)를 만들고, I와 O로만 이루어진 문자열(S)와 비교하였다. 이 경우에 제한 조건에 걸려서(시간초과로 예상) 50점 풀이에 그쳤다. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IO.. 2023. 8. 24.
P1389. 케빈 베이컨의 6단계 법칙 - 문제: https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 설명 1. 모든 정점사이의 최단거리를 구한다. 2차원 배열의 모든 값을 INF로 초기화하고, (1,1), (2,2), ... (i,i)인 값을 0으로 초기화한다. 2. 간선은 양방향으로 초기화한다. arr[1][3] = arr[3][1] = 1 3. 플로이드 와샬 알고리즘을 실행하여, 최단 경로를 찾는다. arr[i][j] > arr[i].. 2023. 8. 24.
[☁️ 구름톤 챌린지] 2주차 학습일지 - 1 문제 6. 문자열 나누기 이번 문제는 각 단계마다 해당 자료형을 어떻게 사용하면 좋을지 생각하면 좋을 것 같다. import java.io.*; import java.util.*; import java.lang.*; class Main { static int N; static String S; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); S = br.readLine(); int result = 0; // 나올 수 있는 조합 리스트 List wordLi.. 2023. 8. 23.

티스토리툴바