Algorithms/백준(BOJ)

동전링크: https://www.acmicpc.net/problem/9084문제 해결 과정1. 문제를 읽고 이해하기테스트 케이스의 개수 T (1 동전 종류의 수: N (1 만들어야 하는 금액: M (1 N가지의 동전을 가지고 M을 만들어야 한다. 만약 10원과 20원을 가지고 50원을 만드는 경우의 수는 3가지가 있다.1. 10 10 10 10 102. 10 10 10 203. 10 20 202. 재정의와 추상화N 개의 수를 사용하여 어떤 수 M를 만들 수 있는 경우의 수를 구해야 한다.3. 계획 세우기각 상황에 대한 모든 경우의 수를 나열하다보면 감을 잡을 수 있다. 10과 20으로 50을 만드는 경우의 수10원과 20원으로 50원을 만드는 경우의 수를 다시 확인해보자1. 10 10 10 10 102...

카드 구매하기링크: https://www.acmicpc.net/problem/11052 문제 해결 과정1. 문제를 읽고 이해하기N개의 카드 팩이 있고 입력값의 순서에 따라 i 장의 카드가 들어있다.N장의 카드를 얻기 위해 지불해야 하는 카드 값의 최댓값을 구하라. N이 4이고 1, 5, 6, 7이 각 카드 팩의 가격으로 주어졌다면 1장 팩 가격: 12장 팩 가격: 53장 팩 가격: 64장 팩 가격: 7 카드의 수가 4장이 되는 모든 경우의 수의 가격을 살펴보자. 편의상 N장의 카드가 담긴 팩을 팩N, 값단위를 $로 표기하겠다.팩1 * 4개 = 4$팩1 * 2개 + 팩2 = $7팩2 * 2 = $10팩3 + 팩1 = $7팩4 = $7 ∴ 4장을 구매하기 위한 최댓값은 2장 팩을 2개 구매하는 것이다.2. ..

극장 좌석링크: https://www.acmicpc.net/problem/2302 2024.10.23 - [Algorithms/알고리즘 문제 해결 전략] - [종만북] 알고리즘 문제를 해결하는 과정 [종만북] 알고리즘 문제를 해결하는 과정※ 구종만 저자님의 『알고리즘 문제 해결 전략』에서 발췌한 내용입니다.기본적인 문제 해결 과정1. 문제를 읽고 이해한다.2. 문제를 익숙한 용어로 재정의한다.3. 어떻게 해결할지 계획bitbit-merry-go-round.tistory.com회고의 방식을 위 포스팅의 내용을 반영하여 진행할 생각입니다😊문제 해결 과정1. 문제를 읽고 이해하기1. 1번 부터 N번까지 번호를 매긴 좌석이 있다.2. k번의 번호표를 가지고 있는 사람들은 k-1, k, k+1 세 좌석 중 한 ..

택배링크: https://www.acmicpc.net/problem/8980 문제문제 접근각 마을에서 적재할 수 있는 박스의 최댓값을 구해야한다고 생각했다. 따라서 마을의 번호를 오름차순으로 정렬해서 풀이를 시도했다.문제는 현재의 최댓값이 전체의 최적해일 수 없다는 점이다.200의 용량을 가진 택배가 마을 1에서 7마을로 가는 200의 상자를 실어버리면 2마을과 4마을의 400을 놓치게 된다.현재 위치에서의 최적해를 판단하기 위해서는 잠재적으로 얻을 수 있는 값을 알고 있어야 한다.이 문제를 해결할 수 있는 방법을 생각해보자.최대 적재량이 200이기 때문에 2마을과 4마을에서 180을 싣더라도 20의 여유 공간이 생긴다.따라서 1마을에서 1마을에서 7마을까지의 여유 공간, 20을 구할 수 있어야 한다.이..

최솟값 찾기링크: https://www.acmicpc.net/problem/11003문제문제 접근문제의 흐름을 예제를 통해 살펴보자.가장 직관 적인 방식으로는 요소를 순서대로 주어진 길이만큼 보며 그때그때 정렬하여 최솟값을 구할 수 있다.시간 제한은 2.4초이고 수열의 크기와 길이는 5,000,000개 제한이다. N개의 범위에 대해서 정렬을하면 LlogL의 시간복잡도를 가질 것이므로, NLlogL의 최악의 경우는 N과 L이 각각 5백만일 경우 NL만 계산해도 25조 이다.어떻게든 시간복잡도를 줄일 수 있는 방법을 찾아야 한다. 자료구조를 적절히 사용하여 해당 구간의 최솟값을 구해야 한다.먼저 deque을 사용하는 문제라는 것을 이미 알고 있었기 때문에 front와 back에서 일어나는 연산을 통해 deq..

큐빙링크: https://www.acmicpc.net/problem/5373문제문제 접근문제 자체의 이해가 그다지 어렵지는 않았다.큐브의 각 면이 w(white), y(yellow), r(red), o(orange), g(green), b(blue)로 주어져있다.각 테스트 케이스 별로 면을 돌린 뒤에 top의 큐브가 어떤 패턴인지 출력하는 문제이다.큐브의 각 면을 저장할 배열과 적절하게 시계방향 또는 반시계 방향으로 돌리는 함수만 만들면 된다. 너무 간단하다!라고 생각했다.풀이 힌트큐브의 각 면 저장각 면은 2차원 배열 char side[3][4]로 표현할 수 있다. 문자열(char 배열)이기 때문에 null 자리 포함각 면을 회전시키는 함수각 면의 돌리는 방향은 + 또는 -으로 주어진다.시계방향의 경..

히스토그램에서 가장 큰 직사각형링크: https://www.acmicpc.net/problem/6549문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.문제 접근예제에서 주어진 요소를 하나씩 보며 높이별로 구해야 하는 최댓값을 살펴보자.높이가 1인 직사각형: 가장 작은 값은 1으로 7개의 요소가 모두 공유하기 때문에 길이가 7까지 증가한다.높이가 2인 직사각형: 2 다음 1이 옴으로써 길이가 1인 직사각형을 구할 수 있다. ..

자두나무링크: https://www.acmicpc.net/problem/2240문제자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 ..