전체 글 (118) 썸네일형 리스트형 [Gold4-JAVA] 백준 11657 - 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 🤔문제 풀이 문제에서 음의 가중치가 존재하는 것, 그리고 1번 도시에서 어떤도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다 는 것에서 음의 사이클이 존재할 수도 있다는 정보를 얻어 한 정점에서 다른 정점까지 최단 거리를 구하고 음의 사이클 존재 여부를 확인할 수 있는 벨만 포드 알고리즘을 적용해 풀어야겠다고 생각했다. 🚨C.. [Gold5-JAVA] 백준 21278 - 호석이 두 마리 치킨 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 🤔 초기 문제 접근 초기에 이 문제를 완전탐색으로 풀고자 했다. 전체 건물들 중에서 두개의 건물을 치킨집으로 선택한 뒤 다른 모든 건물들에서 깊이 우선 탐색을 진행하여 치킨 건물로의 최소 거리를 구하고자 했다. 하지만 전체 19개의 테스트 케이스 중 5개 밖에 맞히지 못했다. 또한 위와같은 풀이법으로 접근하고자 했다면 다른 건물들이 아닌 치킨 건물에서 다른 건물로의 .. [Silver2-JAVA] 백준 1780 - 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 🤔 문제 풀이 쉽지 않았던 분할 정복 문제였다. 처음 문제를 풀었을 때 계속된 재귀호출을 통해 종이들을 분할하여 풀어나가는 방법임은 짐작했으나 종이들을 나누는 과정을 생각해내는 것이 무척 어려웠다. 첫 종이의 전체 요소들이 전부 같은지 검사하고 만약 다르다면 row/3 col/3 하여 9칸으로 나누고 나뉜 종이들을 다시 검사하고... 이런 과정의 반복이었다. 종이들을 분할하기 위해 필요.. [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 형식의 데이터를 사칙연산하기 .. [JAVA] 자료구조 - 배열 🤔 배열이란? 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 자료구조를 말한다. 만약 배열이 없었다면 우리는 하나하나 변수들을 선언했어야 했을 것이다. 하지만 우리는 배열이 존재하기 때문에 보다 쉽게 여러 데이터를 저장할 수 있게되었다. // No 배열 int a = 1; int b = 2; int c = 3; int d = 4; int f = 5; // Yes 배열 int[] abc = new int[5]; for(int i = 1; i 이전 1 2 3 4 5 6 7 8 ··· 15 다음
