1. 💎 문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다. 3. 💡로직 1. 지도를 입력 및 시작점 받기 이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..

1. 📄 문제 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 2. 🤔 어떻게 접근할까 문제가 길어 차근 차근 그림으로 그리니 짝수와 홀수번으로 나누어졌다. 그래서 짝수와 홀수번 로직을 따로 구현한다로 생각했다. 또한 폭탄이 터지는 기준은 폭탄이 있는 위치에서 상하좌우 4개의 폭탄이 터져 없어지기 떄문에, 폭탄의 위치를 큐에 넣어 터질 시간이 되면 큐에서 꺼내어 상하좌우를 알아보기로 생각했다. 이 정도만 생각하고 바로 풀었는데 몇 몇 막히는 부분이 있었다. 3. 💡 생각해야 할 점 먼저, 폭탄은 설치 후 3초가 지나야 터진다는 ..

1. 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 2. 문제 풀이 해당 문제는 입력받은 간선의 정보대로 리스트(graph)에 담고 DFS 탐색을 진행하면 되는 문제이다. 결과는 연결 요소의 개수. 즉 노드의 집합이 몇개이냐 문제이다. 그러므로 DFS 탐색을 진행하다 해당 그래프의 탐색이 완료되면, Count를 1 더해주고 다른 노들 집합을 찾아 탐색을 진행한다. 2.1 그래프 구성 간선이 Nx(N-1)/2라면 무방향 그래프이다. 무방향 그..

코드를 짜면서 느낀 거는 지금 내 코드 스타일은 아주 옛날에나 썼을 방식이라는 것이다.(옛날에도 안 썼을 수도...) 그래서 다른 사람들의 코드를 보면서 흥미로운 것들, 배우고 싶은 것들을 정리해 볼 것이다!! ++ 피드백 리뷰 1. 입력 메세지는 모두 상수로 코드 도중에 문자열을 넣으니 깔끔하지 않다는 느낌이 있었다. 아래와 같이 모두 상수로 선언하고 코드에 작성하니 보기도 깔끔하고, 수정도 쉬워지는 장점이 있다.`final`:값이 변경될 수 없음. 상수, `static` : 메모리가 한 번 할당됨 private static final String GAME_START_MESSAGE = "숫자 야구 게임을 시작합니다."; private static final String INPUT_NUMBERS_MESS..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 흐름 이 문제는 테스트 케이스의 제한이 없는데 N은 100,000이다. 그러므로 최대한 O(n)으로 풀어야 겠다고 생각했다. 어떻게 최대값을 찾는냐! 스티커는 총 2줄이고 인접한 스티커는 뜯으면 안된다. 만약 열의 수가 짝수이면 지그재그 방법뿐이다. 그래서 2개의 경우의 수 밖에 없지만 문제는 열의 수가 홀수일 때 이다. 예제를 분석해보면 현재 위치에서 갈 수 있는 방법은 2가지이다. 인접한 변으로 못가니, 대각선으로만 이동이 가능하다. 대..

문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 생각 흐름 우선 최소가 되는 상황을 생각했다. 최소가 되는 상황은 -기호가 나오고 + 기호가 나오면 빼줄 때 최소 값이 된다. -기호가 나오고 -기호가 나오면 마찬가지로 빼준다. 우선 로직은 이 정도로 생각했다. 구체적인 해결 로직 입력 데이터 처리 입력은 한줄로 +, - 기호와 숫자가 섞여 주어진다. 이 데이터를 어떻게 처리할 지 고민하다 char[] 을 이용하여 구별 한 후, 숫자와 기호 리스트를 생성하여 데이터를 추가했다. br = new Buf..

문제 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 접근 문제를 딱 읽었을 때 대체 어떻게 풀어야 하지..? 감이 안 잡히는 문제였다. 처음 수에서 마지막 수로 가는 규칙을 발견할 수 없었다. 그렇게 여러 고민을 해보다 마지막 수를 기준으로 돌아 가볼까! 생각했더니 쉽게 풀렸다. 알고리즘 B가 짝수라는 것은 직전 단계에서 X2 연산을 했다는 것이므로 나누기 2를 해준다. B가 홀수라는 것은 직전 단계에서 마지막 자리에 1을 더했다는 것이므로 1를 빼고 10으로 나눈다. 이 과정을 B가 A보다 클 때까지 반복한다. A, B를 입력 받는다. while( B가 A보다 클 때까지) if(B가 짝수) B를 2로 나눈다 else (B가 홀..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 생각 n을 5와 2로만 채울 때 가장 최소 동전의 개수를 구해야 하므로, 5를 기준으로 5 동전의 크기를 줄여나가면서 구한다. 코드 1. input() n을 입력 받는다. public void getInput() throws Exception { n = Integer.parseInt(br.readLine()); } 2. solution() 예를 들어 18일 때 18 ÷ 5 = 3이므로 최대 5 동전의 개수는 3이다. 그 후 18 - (5 X 3) = 3(나머지수)을 2 동전으로 채울 수 있는지 확인한다. 만약 나머지 수를 2로 채울 수 있다면 결과에 3 ÷ 2 = 1 의 ..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떻게 풀것인가? 트리 형태를 만든 다음 삭제 노드를 부모 노드와 끊어준다. 노드의 부모는 무조건 1개이기 때문에, 끊어주면 탐색을 할 수 없다. 트리를 DFS 탐색으로 탐색을 진행한다. BFS나 DFS 둘다 되겠지만 구현이 쉬운 BFS를 선택했다. 문제 알고리즘 parent 배열에 각 노드의 parent 값을 저장한다. parent 배열 이용하여 삭제할 노드를 부모 노드에서 제거 한다. BFS 탐색을 진행하면서 leaf 노드를 찾는다. 주의할 점 루..

시도 방법 방법 1 : 위로 올라가면서 비교 (실패) 1. 전위 탐색으로 노드 값이 주어진다 2. 마지막 삽입 노드를 기준으로 추가 해야지 3. 마지막으로 삽입된 노드를 기준으로 점점 올라가면서 비교를 하자 4. "틀렸습니다" 방법 2 : 루트를 기준으로 아래로 내려가면서 적절한 위치에 삽입 (성공) 1. 모든 트리의 왼쪽은 무조건 자기보다 작아야 하고 오른쪽은 무조건 커야하는 규칙이 존재 2. 루트를 기준으로 내려가면서 적절한 위치에 노드를 추가하면 되지 않을까 3. "맞았습니다" 의문점 왜 하나씩 추가해도 문제가 되지 않는지 이해가 안되어서 찾아봄 의문점 1 : 이진 탐색트리는 값에 따라 위치가 무조건 같나? 삽입 순서에 따라 달라지는 건가? 답 : 삽입 순서에 따라 위치는 물론 트리 모양도 달라짐 ..