곽로그

문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class..

문제 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Shark{ int x; int y; int size; int eatCount; static int totalEatCount = 0; static int totalMoveCount =0; Shark(int x, int y, int size, int eatCount){ this.x = x; thi..

문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 현재 토마토의 위치를 기준으로 북, 동, 남, 서쪽을 차례로 탐색한 후 익지 않은 토마토가 있으면 익은 토마토로 만든다. 북동남서 방향으로 동시에 확산 되는 것이므로 bfs를 통해 탐색을 한다. 처음 입력을 받을 때 값이 1인 좌표를 queue에 add한다. 이 queue가 빌 때까지 bfs로 탐색을 한다. 익지 않은 토마토가 있을 때 map을 업데이트 하는데, 업데이트 하는 값의 의..

문제 www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net 풀이 2차원 배열을 활용하면 쉽게 풀 수 있다. 문제 예시에 나와 있는 것 처럼 studentArray[n][m] ( 학년이 n학년이고 성별이 m인 학생의 수)인 2차원 배열을 선언한 뒤 배열을 순회하면서 각 학생수를 K로 나눈 몫과 나머지를 구한다. n학년이고 성별이 m인 학생들이 필요한 방의 갯수는, n학년이고 성별이 m인 총 학생수를 K로 나눈 몫을 구한다. 이때 나머지가 ..

문제 www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 잘못한 생각 애너그램의 정의는 "두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다." 이다. 처음에 '순서를 뒤바꾸어'를 한 단어의 순서를 거꾸로 뒤집은 다음 다른 단어와 같아지는지를 확인하는 것으로 생각했다. 즉 asdf 와 fdsa가 있을 때 asdf 의 순서를 뒤집은 단어가 fdsa와 같으면 애너그램이라고 생각했다..

문제 www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 코드로 설명이 되어서 풀이는 패스. 주의해야 할 점은 출력하는 피보나치 수의 자료형은 long 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main ..

문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 map을 순회하면서 칸이 비어있으면 넘어가고, 집인 경우 탐색을 한다. 한번 탐색을 할 때 방문처리를 한 것이 다음 탐색에도 쓰이기 때문에 그 칸을 다시 탐색하는 경우는 없다. 따라서 bfs로도 풀 수 있고, dfs로도 풀 수 있다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamRead..

문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 (0,0)에서 (N-1,M-1)까지 이동할 때 최단거리를 구하는 문제이다. 탐색이므로 dfs로도 풀 수 있지만, dfs로 풀경우 모든 경우를 탐색하게 되므로 시간복잡도는 O(4^MN)가 된다. 이 경우 시간초과가 나므로 dfs로 풀면 안된다. 최단거리라고 했으므로 bfs로 풀어야한다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.Inp..