본문 바로가기
반응형

분류 전체보기123

[cs준비] 그리디 알고리즘이란? 그리디 알고리즘이란 여러 경우 중 매 순간 최적이라고 생각되는 선택지를 선택하는 방식으로 진행해서 최종적으로 값을 구하는 방식이다 따라서 특정 문제를 만났을 때 단순히 현재 상황에서 최적이라고 생각하는 답만 골랐을 때에도 문제를 정상적으로 풀 수 있는지를 고려하는 것이 가장 중요하다. 대표적인 예시로는 동전문제, 회의실 문제 등이 있다. 동전 문제는 거스름돈을 거슬러 줄 때 가장 적은 수의 동전을 가지고 거슬러 주는 문제인데 이 때에는 동전들을 내림차순 정렬한 뒤 가장 큰 동전부터 비교해가면서 거슬러 주면 된다. - 현재 기준에서 가장 큰 동전 말고 더 좋은 선택지가 없기 때문에 이런식으로 구하다 보면 거스름돈을 위한 최소한의 동전 개수를 고를 수 있다. - 하지만 배수가 되지않는 금액 [ex)100, .. 2021. 8. 18.
백준 1080. 행렬 🅰 백준 1080. 행렬 ✏️ 문제 풀이 행렬을 변환하는 연산은 3X3 행렬을 뒤집는 것이다. 그러므로 행렬이 3보다 작을 때, 행렬이 3보다 클 때 2가지 경우를 생각하였다. 1. 행렬이 3보다 작을 때 두 행렬이 같으면 0 출력 / drawCnt변수를 이용하여 같으면++ 해주고 drawCnt = N*M이면 같다고 출력 두 행렬이 다르면 -1 출력 2. 행렬이 3보다 클 때 데이터를 입력받을 때 boolean배열을 이용하여 데이터가 두 데이터가 같으면 true, 틀리면 false로 저장을 했다. boolean배열을 탐색하면서 false라면 그 부분부터 시작해서 3*3행렬만큼 true->false, false->true로 변경해주고 cnt를 이용하여 변경한 횟수를 카운트 해주었다. 모든 배열을 변경 완료.. 2021. 8. 18.
백준 1783. 병든 나이트 🅰 백준 1783. 병든 나이트 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net ✏️ 문제 풀이 이동횟수가 4번보다 적지 않다면 이동 방법을 모두 한 번씩 사용해야 한다는 조건이 있다. 무조건 오른쪽으로만 이동할 수 있고 높이가 1,2,3일때로 구분을 해서 문제를 풀었다. 높이가 1일 때 : 한 칸도 이동할 수 없기 때문에 방문한 블록 : 1 높이가 2일 때 가로가 8보다 작거나 같으면 (가로+1)/2 만큼 블록을 방문 가능 가로가 8보다 크면 4가지 블록만 방문 가능 높이가 3일 때 높이가 3이고 넓이가 7미만일 때(이동횟수가 4번보다 적을 때) : 넓이가 4보다 작으면 .. 2021. 8. 18.
백준 2875. 대회 or 인턴 🅰 백준 2875. 대회 or 인턴 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net ✏️ 문제 풀이 대회에 나갈 수 있는 팀을 구하는 문제이다. 팀원은 여자2 + 남자 1 = 한팀으로 구성된다. 먼저 인원중에 대회에 나갈 수 있는 팀을 구한 뒤 남은사람들과 K를 비교하여 남은 사람이 더 크면 팀을 출력하고, K가 더 크면 팀을 해체해서 인원을 채워야 하기 때문에 (K-남은인원)/3을 해줘서 그 값을 올림을 해줘서 계산을 했다. ✏️ 소스코드 package greedy; import java.util.*; /* * 대회에 나갈 수 있는 팀을 구하는 문제 여2 남1 = 한팀 * 먼.. 2021. 8. 18.
백준 1744. 수 묶기 🅰 백준 1744. 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ✏️ 문제 풀이 두 수를 묶기위한 조건으로는 음수일때는 (큰수,큰수)를 묶어서 서로 곱해주고, 0이 있으면 곱해주고, 양수일때는 (큰수,큰수) 묶어서 서로 곱해주고 1은 곱하지 않는게 좋으므로 1이 있다면 따로 개수를 count해서 더해준다. 데이터를 음수와 0, 양수로 따로 나눠서 list에 저장하였다. 음수일때는 오름차순, 양수일때는 내림차순으로 정렬하였다. 음수와 양수일때 반복문을 따로 구성해주었고 데이터를 2개씩 묶어서 다루.. 2021. 8. 17.
백준 1541. 잃어버린 괄호 🅰 백준 1541. 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ✏️ 문제 풀이 식의 값을 최소로 만들려면 +를 먼저 수행하고 -를 수행하면 식의 값이 최소가 된다. 1. 읽어온 문자열을 .split을 이용하여 '-' 단위로 문자열을 나눠서 저장한다. 2. 나눠진 문자열을 다시 '+' 단위로 문자열을 나눠서 각 배열을 더해서 sum에 저장한다. 2-2. i가 0일때 제일 첫 시작이므로 max에 더하고 나머지 sum값들은 max-=sum을 해줘서 연산의 최소값을 구해주었다. ✏️ 소스코드.. 2021. 8. 17.
백준 11399. ATM 🅰 백준 11399. ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ✏️ 문제 풀이 인출에 걸리는 시간을 오름차순으로 정렬 후 시간이 적게 걸리는 사람부터 인출을 하도록 한다. 1번사람의 시간은 2,3,4,5번의 사람들에게 다 적용되므로 각 케이스 마다 *(N-1)을 해서 최소시간을 구해준다. ✏️ 소스코드 package greedy; import java.util.*; import java.io.*; public class Main_실버3_11399_손은성 { public static void main(String[] args) .. 2021. 8. 17.
백준 1931. 회의실 배정 🅰 백준 1931. 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ✏️ 문제 풀이 회의실 배정은 종료시간이 빠른 순서대로 처리를 해야한다. 종료시간 기준으로 오름차순을 정렬하고, 종료시간이 같으면 시작시간 기준으로 오름차순을 정렬하였다. ✏️ 소스코드 package greedy; import java.util.*; import java.io.*; public class Main_실버2_1931_손은성 { private static int conference[][]; private static int minEndTime = Integer.MIN_VALUE; private static int cnt; public .. 2021. 8. 17.
백준 11047. 동전 🅰 백준 11047. 동전 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ✏️ 문제 풀이 동전 문제가 그리디로 성립하기 위해서는 주어진 동전이 배수의 조건을 맞아야 한다. 가장 큰 동전의 가치부터 동전의 개수만큼 가격에서 / 를 해서 나오는 값이 필요한 동전의 개수이므로 계속 더해준다. needCoin = 필요한 동전의 개수 pay[] = 동전 종류의 가격 ✏️ 소스코드 package greedy; import java.util.*; import.. 2021. 8. 17.

티스토리툴바