코딩테스트 (66) 썸네일형 리스트형 [Gold4-JAVA] 백준 14499 - 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 🤔 문제 풀이 쉽지 않았던 시뮬레이션/구현 문제였다. 주사위를 굴렸을 때 map과 닿는 각 면의 숫자를 어떻게 채워줄지 막막했었다. 주사위가 다음과 같이 있다고 하고, 윗면을 보이는 주사위가 3이라고 한다면 다음과 같은 방식으로 움직이게 된다. 동쪽이동 서쪽이동 북쪽이동 남쪽이동 2 -> 3 4 -> 3 5 -> 3 1 -> 3 6.. [Gold4-JAVA] 백준 15918 - 랭퍼든 수열쟁이야!! https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 🤔 문제 풀이 수열에 대한 규칙을 알려줬지만 처음에 수열을 어떻게 채워나갈지 막막했다. 하지만 문제에서 주어지는 입력 값 중 수열의 X와 Y위치의 숫자가 같다는 정보를 캐치했고 X와 Y의 숫자가 같으려면 X와 Y 사이의 간격이 X or Y와 같아야 함을 깨달았다. ex) x = 4, y = 10 이라고 주어지면 x와 y 사이엔 5칸의 빈칸이 존재하고 이는 수열 규칙에 의해 x와 y가 5임을 알 수 있는 부분이다. 이는 수열을 담은 배열 seq[x] = seq[.. [Silver1-JAVA] 백준 14888 - 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 🤔 문제 풀이 제법 쉬웠던 완전 탐색 문제였다. 전체 숫자에 대해 수행할 수 있는 모든 연산자를 도입하여 최대와 최소값을 구하면 된다. 아마 별다른 최대, 최소를 구할 수 있는 방법이 없을 것이라 생각하고 고민없이 깊이우선 탐색 알고리즘인 DFS 알고리즘을 사용해 풀었다. 음수와 양수의 나눗셈 같은 경우 문제에서 양수 끼리 몫을 취하고 음.. [Silver3-JAVA] 백준 2407 - 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 🤔 문제풀이 처음 문제를 보고 재귀로 풀으려고 했다가 시간초과가 계속 나서 힘들었었던 문제다. 조합에 관련된 문제가 자주 나오므로 알고있으면 좋을 것 같다. 어떤 n과 m이 주어졌을때 nCm = (n-1)C(m) + (n-1)C(m-1)이다. 또한 nC0 = nCn = 1이며 nCm = nCn-m이다. (ex. 4C3 = 4C1) 데이터의 최대 범위를 입력했을 때 숫자가 매우 크게 나오기 때문에 무한대를 표현할 수 있는 class인 BigInteger을 사용했다. BigInteger 형식의 데이터를 사칙연산하기 .. [Gold3-JAVA] 백준 2638 - 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🤔문제 풀이 상당히 난이도가 있었던 그래프 탐색 문제였다. 전체적인 로직은 어렵지 않았지만 외부공기와 내부공기를 파악해 치즈가 내부에 있는지 외부에 있는지를 판단하는 것이 어려웠다. 본인은 다음과 같은 로직 순서로 풀이를 진행했다. 1. map에 치즈 정보를 받는다. 2. 가장 자리에는 치즈가 놓이지 않기 때문에 0,0 좌표부터 DFS 탐색을 진행하며 외부 공기 위치를 파악했다. 3... [Silver3-JAVA] 백준 2193 - 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 🤔문제 풀이 간단한 DP 문제였다. 이친수는 첫째 자리가 반드시 1로 시작해야하며 1이 연속으로 오지 않는 수인데 자릿수가 증가할때마다 가능한 숫자들의 개수를 구해보니 N=1일때, 1 (1개) N=2일때, 10 (1개) N=3일때, 100, 101 (2개) N=4일때, 1000, 1001, 1010 (3개) ... dp[N] = dp[N-1] + dp[N-2]의 피보나치 수열의 형태를 .. [Silver2-JAVA] 백준 13565 - 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 🤔 문제 풀이 자주 접했던 그래프 탐색 문제들과 비슷한 문제여서 어렵지 않게 풀어냈다. 그래프 탐색 알고리즘은 BFS를 사용했고 map의 정보들 중 inner side 가 0인 곳과 outer side가 0인 곳을 배열을 생성해 담아두고 이후 각 inner side에서 시작하여 탐색이 끝나면 outer side에 도달했는지 여부를 검사했다. 🚨CODE impor.. [Gold4-JAVA] 백준 1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 🤔 문제 풀이 그래프 탐색 문제인 트리의 지름 문제이다. 트리의 연결 정보들 중에서 한 정점에서 다른 정점까지의 거리가 가장 긴 것을 찾으면 되는 문제다. 모든 정점에 대한 연결 정보를 저장하기 위해 Node 클래스를 생성하여 정점과 가중치 정보를 저장하고 이를 ArrayList에 저장하였다. 모든 정점 중, 한 start 정점에서 다른 모든 정점을 이동하며 start정점의 최.. 이전 1 2 3 4 5 6 7 ··· 9 다음
