SY DevLog

백준 17136번 : 색종이 붙이기(삼성 SW 역량 테스트) 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 그리디 + 백트래킹으로 해결할 수 있는 문제 나는 재귀를 이용하여 문제를 풀었다. 배열을 돌면서 큰 색종이부터 붙일 수 있는지 확인한다.(그리드 방식) 현재 위치에서 5x5 크기의 색종이를 붙일 수 있으면 붙인다. 다음 위치로 이동해서, 5x5 크기의 색종이를 붙일 수 있으면 붙인다. ... 배열의 마지막 위치로 이동해서 5x5 크기의 색종이를 붙일 수 있으면 붙인다. 마지막 위치에서 색종이 크..

백준 15904번 : UCPC는 무엇의 약자일까? 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 알고리즘 : 그리드 알고리즘, 문자열 어렵지 않은 문제 String 메서드만 적절히 사용하면 쉽게 풀 수 있는 문제다. 입력 받은 문자열의 첫번째 위치부터 시작하여 차레대로 indexOf(찾으려는 문자, 시작 인덱스) 메서드를 이용한다. 'U', 'C', 'P', 'C' 문자가 존재하는지 하나씩 검사한다. 'U' 문자를 찾으면 'U'의 위치 인덱스 +1 부터 'C' 문자가 있는지 확인한다. ..

백준 15903번 : 카드 합체 놀이 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 크게 어렵지 않은 문제. 문제를 보자마자 우선순위 큐를 사용해야겠다는 생각이 들었다. 카드 중에서 제일 작은 수 두 개를 뽑아서 합을 구하는 과정을 반복하면 되기 때문이다. 우선순위 큐는 매번 제일 작은 값을 찾을 때 유용하게 쓰일 수 있다. 알고리즘 : 1. 우선순위 큐에 카드를 모두 넣는다. 2. 카드 중에서 제일 작은 두 수를 뽑은 뒤, 그 합을 구한 다음, 다시 우선순위 큐에 합을 ..

알고리즘 : 그리디 알고리즘, 정렬, 우선순위 큐 처음에 시간초과가 나서 다른 블로그를 참고해 해결하였다. 개인적으로 어려웠던 문제였다. 백준 : 1931번 회의실 배정 문제 와 달리 이번 문제는 시작시간 기준으로 정렬을 해야한다. 시작시간과 종료시간을 강의정보로 갖는 갖는 Lecture 라는 클래스를 만들어줬다. 그리고 강의들을 저장하는 lectures 배열이 필요하다. lectures 배열에 강의들을 시작시간을 기준으로 오름차순 정렬을 한다. (위의 예제로 예를 들면 lectures 배열에는 (1,3) -> (2,4) -> (3,5) 순으로 정렬됨) 이 문제에서 구하고자 하는 것은 최소 사용할 수 있는 '강의실 수' 이다. 이 문제에서 중요한건 우선순위 큐를 사용한다는 것이다. 우선순위 큐는 강의실에..

사용한 방법 : BFS 1차 시도 1번 노드부터 12번 노드까지 차례대로 시작노드로 잡고 BFS를 통해 각각의 길이가 최대가 되는 max값을 구하였다. 1번 노드가 시작점인 경우의 최대값 2번 노드가 시작점인 경우의 최대값 3번 노드가 시작점인 경우의 최대값 ... 12번 노드가 시작점인 경우의 최대값 그 후, 각각의 최대값들을 또 비교하여 그 중에서 최대가 되는 값이 최종 트리의 지름이 된다. 결과 : 메모리 초과 2차 시도 트리의 지름을 구하는 간단한 방법을 구글에서 찾아 적용하였다. 1. 먼저, 루트 노드를 시작노드로하여 가중치의 합이 가장 큰, 즉 가장 긴 곳의 노드를 maxDistNode로 지정한다. 2. 그 후, maxDistNode 노드를 다시 시작노드로 하여 가장 긴 곳의 노드까지가 트리의..

사용한 방법 : DFS, BFS 풀이 1. 반복문을 통해 2차원 배열 map에서 1(대륙)인 위치(n,m)를 찾는다. for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map[i][j] == 1) { isvisited = new boolean[N][N]; sameLand(i, j); // 같은 섬에 속하는 위치들의 isvisited를 true로 변경 bfs(i, j); } } } 2. 해당 지점을 포함하는 섬을 dfs방법으로 탐색한 후에 해당 위치들을 isvisited[i][j]=true로 변경한다. 여기서 isvisited[i][j]=true이며 map[i][j]=1인 위치는 (n,m)위치의 대륙과 동일한 섬에 속함을 의미한다. publi..

사용한 방법 : DFS, DP 문제 1. 처음에는 DFS만으로 문제를 풀었는데 메모리 초과가 나왔다. 생각을 해보니 DFS만으로 문제를 풀면 이미 지나갔던 경로를 다시 지나가야 한다는 문제점이 생기게 된다. 예를 들어 32 -> 30 -> 25 -> 20 -> 17 -> 15 -> 10 경로를 먼저 거친 후 재귀를 끝내고 다시 32로 돌아와서 32 -> 20 -> 17 -> 15 -> 10 경로를 구해야 할 때, 그 이전에 20 -> 17 -> 15 -> 10 으로 향하는 경로의 수를 구한 상태임에도 불구하고 갔던 경로를 또 탐색하게 된다. public static int dfs(int sm,int sn) { int count=0; for (int i = 0; i < 4; i++) { int m = sm..

사용한 방법 : DP i번째 수가 포함된 감소하는 수열의 길이 : dp[i] 전체코드 package num11722; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new ..

사용한 방법 : Stack 풀이 : 1. 왼쪽 소괄호 혹은 왼쪽 대괄호를 만나면 스택에 push한다. 2. 오른쪽 소괄호(오른쪽 대괄호)를 만났을 때, 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)가 아니면 균형잡힌 문자열이 아니다. - 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)이면 pop한다. - 스택의 맨 위의 문자가 왼쪽 소괄호(왼쪽 대괄호)가 아니면 균형잡힌 문자열이 아니므로 반복문을 빠져나간다. - 스택이 비어있으면 오른쪽 소괄호(오른쪽 대괄호)를 넣는다. 3. 문자열의 길이만큼 반복문을 마쳤을 때 스택이 비어있으면 균형잡힌 문자열이고, 스택이 비어있지 않으면 균형잡힌 문자열이 아니다. 전체코드 package num4949; import java.io.BufferedReader; im..

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제를 풀기 위해 다음과 같은 두개의 배열을 생성했다. dp[i] : 0부터 i번째 위치까지 팰린드롬 분할의 최소 개수 palindrome[j][i] : j번째부터 i번째까지의 문자열이 팰린드롬이면 true, 팰린드롬이 아니면 false 0번째부터 i번째까지 팰린드롬 분할의 최수 개수(dp[i])를 구하기 위해서는 0