갑갑이의 개발세상

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 3차원 배열의 그래프 탐색 문제였다. 특별한 알고리즘은 없었고 차원 하나만 더해주면 되는 단순한 탐색 문제였다. 문제푸는데 넘 오래걸린다,, package BOJ; import java.io.*; import java.util.*; public class BOJ6593 { private static final char WALL = '#'; private static final char ESCAPE = ..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 재귀 문제를 풀어보았다. 문제는 길지만 정리하면 완전 이진 트리의 값이 주어지고, 이 트리를 레벨별로 출력하는 문제였다. 입력이 항상 완전 이진트리임이 보장되기 때문에, 전위 순회를 진행시키고 방문 순서대로 StringBuilder에 append하는 방식으로 풀어주었다. 높이가 4인 완전 이진 트리를 예시로 생각해보자 전체 노드의 개수는 2^4 - 1 개이다. 루트 노드의..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 어제 재귀를 풀고 맛이 들렸다. 첨엔 S에 문자열을 붙여가면서 T를 찾아갔는데, 시간초과가 났다. A개수 B개수 세가면서 플래그를 주다가,, 그냥 T에서 조건절에 따라서 문자열을 제거하며 S를 찾아주면 불필요한 문자열의 탐색 없이 빠르게 찾을 수 있겠구나를 깨달았다. package BOJ; import java.util.*; public class BOJ1..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 조건 제대로 안보고 풀어서,,, 겁나 틀렸다 ㅠ 오랜만에 재귀 푸니까 재밌당 package BOJ; import java.io.*; import java.util.*; public class BOJ9184 { private static int[][][] arr = new int[21][21][21]; public static void main(String[] args) throws IOExcep..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 구현 문제이니만큼 flow와 함수형 코딩을 중심으로 풀어봤다... 1. 변수 초기화 2. 지훈이가 이동 3. 불이 이동 -> 이 때 지훈이가 있는곳을 불이 덮는다면 지훈이는.... 😵 4. 지훈이가 이동할 곳이 없어지거나, 탈출에 성공하면 종료! 불과 지훈이가 이동하는 방식이 같기 때문에 재사용 가능한 함수를 만드는걸 좀 고민했다. 소스코드 package BOJ; import ja..

재밌는 문제 발견 https://www.acmicpc.net/problem/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net n, m, k가 주어졌을 때 가능한 순서의 총 경우의 수는 전체 경우의 수를 중복되는 a와 z의 수로 나눈 (n+m)!/(n!m!)이다. 이를 바탕으로 n+m자리의 문자열을 만들 때, dp방식으로 접근. 예를 들어서 첫 번째 문자열의 경우의 수는 총 (n+m)!/(n!m!) 첫 번째 문자가 a였다고 가정했을 때, 그 다음은 a + (n+m-1)!/((n-1)!m!) 두 번째 문자도 a라고 가정하면 aa + ..

https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 문제의 입력은 무조건 트리 형태로 주어집니다. = 순환 사이클이 없다 = 무조건 루트가 1인 트리 형태로 재배열할 수 있다. 주어진 예제의 경우 다음과 같다. 이렇게 트리 형태로 만들었을 때, 어떻게 가장 차이가 적게 나눌 수 있는가? 자신을 포함한 서브트리의 크기를 계산해서 비교해주면 됩니다. 서브트리의 크기는 dfs로 구할 수 있습니다. 일단 노드가 n개 주어..

https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N 1) { if (visit[tmp]) { ground = tmp; } tmp /= 2; } if (ground == 0) { visit[duck] = true; } sb.append(ground + "\n"); } System.out.println(sb); } private static int parse(String s) { return Integer.parseInt(s); } }

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 이것 또한 유니온파인드 응용문제이나, 기초가 탄탄하다면 쉽게 풀 수 있는 문제이다. int[] parent 배열로 그룹번호를 관리해주고 int[] min 배열로 해당 그룹의 최소 친구비를 관리해주면 된다. import java.io.*; import java.util.*; public class Main { private static int[] par..