Algorithm/유형별 문제 풀기
-
[구현] 문제이름 : 게임 개발Algorithm/유형별 문제 풀기 2021. 6. 30. 12:20
문제 설명 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이루어진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동성남북 중 한 곳을 바라본다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 메뉴얼은 다음과 같다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3 만약 네 방향 모두 이미 가본 칸..
-
[구현] 문제 이름 : 왕실의 나이트Algorithm/유형별 문제 풀기 2021. 6. 29. 12:10
문제 설명 8 x 8 좌표 평면이 있고, 나이트는 이동 할 때 L자 형태로만 이동이 가능하다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평을 2칸 이동한 뒤에 수직으로 1칸 이동하기 2. 수직으로 2칸 이동한 뒤에 수평으로 1칸 이동하기 이처럼 8 x 8 좌표 평면 상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램 작성하기 (행 위치 표현은 1~8, 열 위치 표현은 a~h) 1. 사용 알고리즘 구현 - 모든 경우의 수 탐색 2. 문제 해결 아이디어 나이트가 좌표 평면에서 상하좌우로 이동 가능한 모든 경우의 수에 대해 행과 열 각각의 이동 거리를 저장해둔다. 주어진 나이트의 위치를 바탕으로 모든 이동 가능 경우에 대해 좌표 값을 ..
-
[구현] 문제 이름 : 시각Algorithm/유형별 문제 풀기 2021. 6. 29. 11:17
문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나롣 포함되는 경우의 수를 구하는 프로그램 작성하기 1. 사용 알고리즘 구현 - 완전 탐색 2. 문제 해결 아이디어 이 문제의 경우 모든 시각의 경우을 하나씩 탐색하여 3이 포함되는 경우를 찾아서 풀 수 있음. 왜냐하면 00시 00분 00초 ~ 23시 59분 59까지의 모든 경우가 86,400가지만 존재하기 때문임. 이러한 유형은 '완전 탐색(Brute Forcing)' 유형으로 분류됨 → 완전탐색(Brute Forcing) 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법 → 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 ..
-
[그리디] 1이 될 때까지Algorithm/유형별 문제 풀기 2021. 6. 26. 10:18
문제 설명 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택 가능하다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. N이 1이 될 때까지 수행해야 하는 최소 횟수를 구하는 프로그램 작성하기 1. 사용 알고리즘 그리디 2. 문제 해결 아이디어 수행 횟수가 최소가 되기 위해서는 N을 K로 최대한 많이 나누면 된다. N에서 1을 빼는 것보다 숫자가 더 빠르게 줄어들기 때문이다. 3. 코드 구현 방식1) if-else를 통해 조건에 따라 다르게 수행되도록 하기 import java.util.Scanner; public class q3 { public static void main(String[] args)..