알고리즘
코드트리 사용해보면서 느꼈던 점들!
코드트리 사용해보면서 느꼈던 점들!
2025.02.02이 포스팅은 코드트리 x 글또 블로그 챌린지 2기를 통해 코드트리 체험권을 받아 작성한 후기입니다 코딩테스트의 필요성간만에, 코딩테스트 준비를 해야할 필요성을 좀 느꼈다. 문제를 푸는 실력이 많이 죽어서, 문제를 푸는 실력을 다시 한번 살려보고자. 글또에서 관련한 체험권 나눔 행사에 참가했다. 아무래도 코드트리라는 플랫폼을 몰랐던 나로써는 매번 풀었던 백준이나 프로그래머스와 같은 사이트외에 다른 곳에서 도움이 될까라는 생각을 많이 했었다. 코드 트리 사이트에서 제공하는 형태타 사이트와의 다른 점이라면, 개인적으로 Codetrails 라는 방식이 가장 특이했는데, 일종의 이 방식대로 따라해보고 열심히 해봅시다~ 하는 형태의 문제집형태의 커리큘럼이 개인적으로 마음에 제일 들었다. 특히 난이도 별로 결정되어있..
[백준 - 4179번] 불! - 자바(JAVA) 정리 및 해설
[백준 - 4179번] 불! - 자바(JAVA) 정리 및 해설
2020.07.301. 개요 이 문제는 BFS를 활용하여 빠르게 미로를 탈출하는 문제이다. 특히 불과 함께 사람이 미로를 동시에 탈출하는 문제로써 이것을 어떤식으로 해결하는 가에 따라서 문제가 많이 달라진다. https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리�� www.acmicpc.net 2. 설명 이런 문제에서 결국 중요한 포인트는 "같은 시점에 불과 사람을 동시에 움직이는 것"이 가장 중요하다. 결국 이문제에서 핵심으로 문제를 풀려면 불과 사람이 동시간에 움직이여야 한다는 조건이 붙는다. 그 조건을 만..
[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설
[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설
2020.05.03이번에 풀어볼 문제는 DP문제인 동물원입니다. 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이문제는 오르막수와 비슷한 문제 양상을 띄고 있어서, 비슷한 문제 풀이를 이용했습니다. 이차원배열을 통해서 총 3가지의 경우를 나타냈는데 각각의 의미는 이렇습니다 Dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우 Dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우 Dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우 즉, 이전 방의 경우의 수를 계속 취합해서 더할 수 있는습니다. 문제는 주어져있는 조건 "사자를 넣은 방에는 오른쪽방과 아랫방에는 넣을 수 없다" 라는 조건때문에, 사자를 넣지 않은 경우..
[백준 - 11057번] 오르막 수 - 자바(JAVA) 정리 및 해설
[백준 - 11057번] 오르막 수 - 자바(JAVA) 정리 및 해설
2020.05.03이번에 풀어볼 문제는 DP문제인 오르막 수입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제에서 핵심적으로 봐야할 것은 이차원 배열을 통해서 이 문제를 이해하는 방식이라고 생각합니다. 제가 이 문제에서 사용한 방식은 DP[][] 이렇게 있을때 앞의 [] 배열은 N을 뜻하고 뒤의 배열은 [] N에 따라 붙는 한자리 숫자를 뜻합니다. 글로 표현하기가 어려워서 ..
[백준 - 16194번] 카드 구매하기 2 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 10일차
[백준 - 16194번] 카드 구매하기 2 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 10일차
2020.02.2916194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 어떤식으로 접근했는지? 이문제는 카드 구매하기 1에 이어 같은문제인데, 이번에는 최소값을 구하는 게 문제이다. 문제는 최소값을 찾으려면 각 N에 대해서 경우를 다 따져서 확인을 해봐야하는데, 이 최대값의 경우 경우의 수가 1개의 경우만 생기는데, 최소값의 경우 각 경우마다 최소값이 될 경우가 늘어난다고 생각했습니다. 그래서 N의 최소값을 구하기위해서 N-1~ 0 의 최소값을 최대로 더해주고, 부족한 카드를 실제로 남은 걸 더하는 방식으로 모든 카드를 채워 최소값을 만..
[백준 - 2225번] 합분해 - 자바(JAVA) 정리 및 해설 - 1일 1DP 9일차
[백준 - 2225번] 합분해 - 자바(JAVA) 정리 및 해설 - 1일 1DP 9일차
2020.02.272225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떤식으로 풀었나? 일단 이문제는 N의 정수를 K개를 가지고 만드는 경우를 찾아야합니다. 가장 쉽게 생각할 경우는 정수 1개를가지고 N을 만드는 경우와 정수 2개를 가지고 N을 만드는 경우인데요. 정수 1개를가지고 N을 만드는 경우는 무슨 정수든간에 1개 정수 2개를 가지고 N을 만드는 경우는 0~N까지 한가지 경우씩 있기때문에 N+1가지가 존재합니다. 이런 N과 K를 동시에 가지고 있어야하기때문에 DP배열을 2차원 배열로 만들어야합니다. 저의 경우 DP[K][N]식으로 배열을 만들어줬습니다. 즉 DP[1][3] 이라면, 3을 만들기위해서 정수 1개가지고 만드는 경우의 수라고 생각하면 됩..
[백준 - 2302번] 극장 좌석 - 자바(JAVA) 정리 & 1일 1DP - 8일차
[백준 - 2302번] 극장 좌석 - 자바(JAVA) 정리 & 1일 1DP - 8일차
2020.02.272302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 어떤식으로 풀었는지? 이번 문제 역시 DP문제이다. 핵심은 결국에 고정된 VIP석을 제외한 나머지 가짓수에 대해서 곱으로 전체 경우를 구한다는 것. 두번째는 Vip좌석을 통해서 남겨진 좌석을 지정된 방법으로 섞었을때 가능한 경우의 수 찾는 것. 완벽하게 이문제를 풀지를 못했고, 이분의 블로그를 많이 참고해서 풀었다 http://blog.naver.com/occidere/220854811310 [백준] 2302 - 극장 좌석 문제 링크 : https://www.acmicpc...
[백준 - 1904번] 01타일 - 자바(JAVA) 정리 및 해설 &1일 1DP- 7일차
[백준 - 1904번] 01타일 - 자바(JAVA) 정리 및 해설 &1일 1DP- 7일차
2020.02.271904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 어떤식으로 풀었는가? 01타일은 동적계획법으로 푸는 문제이다. 01타일의 특이한 점은 n에따른 증가폭이 어디서 본것 같은 모양새로 증가합니다. N = 1일때 1개 (1) N =2 일때 2개 (00, 11..
[백준 - 6359번] 만취한 상범 - 자바(JAVA) 정리 및 해설 & 1일 1DP -6일차
[백준 - 6359번] 만취한 상범 - 자바(JAVA) 정리 및 해설 & 1일 1DP -6일차
2020.02.27안녕하세요. 오늘 풀어 볼 문제는 만취한 상범입니다. 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net DP라고 하기에는 애매한 부분이 있긴하지만, 그래도 처음에 풀기에 무난한 문제입니다. 어떤식으로 풀었는지? 방을 int로 만들고 (물론, int로..
[백준 - 1699번] 제곱수의 합 - 자바(JAVA) 정리 & 1일 1 DP - 5일차
[백준 - 1699번] 제곱수의 합 - 자바(JAVA) 정리 & 1일 1 DP - 5일차
2020.02.24안녕하세요 이번에 풀어볼 문제는 제곱수의 합입니다. https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 어떤식으로 풀었었나? 처음에 문제를 풀었을때는 단순하게 N-1의 값 +1 이라고 생..
[백준 - 11727번] 2*N 타일링 2 - 자바(JAVA) 정리 & 1일 1DP - 4 일차
[백준 - 11727번] 2*N 타일링 2 - 자바(JAVA) 정리 & 1일 1DP - 4 일차
2020.02.22안녕하세요. 이번에 풀어볼 문제는 2N 타일링 2입니다. 다이나믹 프로그래밍 문제입니다. 이문제는 참고해서 풀었기 때문에, 코드만 적어 놓도록 하겠습니다. 차후에 다시 한번 더 풀어보고 해설을 올리겠습니다. /** 2020. 2. 22. 오후 8:03:38 * @author ventulus95 */ package codeBaekJoon; import java.io.BufferedReader; import java.io.InputStreamReader; public class No11727_2nTitle { static int cache[] = new int [1001]; public static void main(String[] args) throws Exception { BufferedReader br..
[백준 - 11052번] 카드구매하기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 3일차
[백준 - 11052번] 카드구매하기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 3일차
2020.02.19안녕하세요 오늘 풀어볼 문제는 카드 구매하기입니다. Dynamic Programming 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 개요 이문제에서 가장 중요한 포인트는 "금액의 최대값"을 맞춰줘야하기때문에 각 N개의 카드를 샀을의 금액이 최대가 되는 경우를 찾아야합니다. 즉, 각 경우마다의 카드를 살 수 있는 최대 금액을 찾아서 그 값을 저장을 해야합니다. N 만큼의 카드를 사야한다면, N = N-1개를 샀을때..