전체 글
-
[구현] 문제 이름 : 시각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) 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법 → 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 ..
-
[그리디] 문제 이름 : 체육복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. 18:45
문제 설명 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 1장을 뽑는 게임이다. 단, 주어진 게임의 룰을 지키며 카드를 뽑아야 한다. 게임 룰 : 1. 뽑고자 하는 카드가 포함되어 있는 행을 선택함 2. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함 3. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함 1. 사용 알고리즘 그리디 2. 문제 해결 아이디어 주어진 2차원 배열의 각 행마다 최소값을 찾고, 최소값들 중 가장 큰 값이 속한 행을 선택해 해당 값을 반환해주면 된다. 3. 코드 구현방식1) 각 행을 오름차순 정렬시킨 후, 각 행의 첫 번째 원소들..