알고리즘
-
[구현] 문제 이름 : 왕실의 나이트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/Programmers 2021. 6. 28. 12:10
문제 : https://programmers.co.kr/learn/courses/30/lessons/42862 1. 사용 알고리즘 그리디 2. 문제 해결 아이디어 체육복을 가진 학생의 수가 최대가 되기 위해서는 체육복을 도난 당한 학생의 앞뒤 학생이 여별 체육복이 있을 때 앞의 학생의 여벌 체육복을 빌리도록 해야한다. 3. 코드 구현방식) 1. lost[]와 reserve[]를 전체 학생의 배열 stu[]에 적용시켜 하나의 배열로 합쳐서 처리하도록 함 --> lost[]와 reserve[] 각각을 탐색하지 않아도 됨, 여벌 체육복을 가져온 학생이 도난당한 경우에 대해서도 한번에 처리 가능함 2. 반환 값 answer(체육 수업을 들을 수 있는 학생 수)를 전체 학생 수의 값 n으로 초기 설정함 --> 0..
-
[그리디] 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)..
-
[그리디] 큰 수의 법칙Algorithm/유형별 문제 풀기 2021. 6. 25. 17:08
1. 사용 알고리즘 그리디 2. 문제 해결 아이디어 주어진 배열의 값 중 가장 큰 수 2개를 선택해 조건에 맞게 더해주면 가장 큰 수를 만들 수 있다. 3. 코드 구현방식) 반복되는 수열을 사용한다. 가장 큰 수를 만들기 위해서는 최대값을 가장 많이 더해줘야 하므로 K값에 따른 반복되는 수열의 크기는 K+1이 된다. 따라서 더해지는 횟수 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 추가로 M이 (K+1)로 나누어 떨어지지 않는 경우가 존재하므로 이때는 M을 (K+1)로 나눈 나머지만큼 최대값이 추가로 더해진다. 최대값이 더해지는 횟수 = M/(K+1) * K + M%(K+1) import java.util.Scanner; import java.util.Arrays; class q1 { pu..