본문 바로가기

알고리즘15

[백준] 1654번 랜선 자르기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1654 어렵지 않은 이분 탐색 문제였다. [문제] 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되.. 2023. 2. 15.
알고리즘을 배우는 이유 및 커리큘럼 알고리즘을 배우는 이유라고 썼지만 사실 알고리즘을 "다시" 배우는 이유이다. 사실 2022년 여름방학 두 달 동안 친구들과 스터디를 만들어 스터디 장으로서 활동하였고, 그 스터디를 하면서 알고리즘을 공부한 적이 있다. 그 때 하루에 2~8시간정도씩 꾸준히 알고리즘 공부를 했었던 걸로 기억한다. 그 정도로 알고리즘을 열심히 하였다. 그래서 재귀는 기본이고 다이나믹 프로그래밍, 그래프도 충분히 익혔다. 그리고 학기가 시작하면서 42서울한다고 바빴고, 학교 공부 따라간다고 바빠서 알고리즘에는 아예 손을 놨었다. 그리고 이번에 UOSPC라는 교내 알고리즘 대회에 출전하였고, 1, 2학년 40여명 중 6등을 하게 되었다. 상금도 받고 기분은 좋았지만 조금 아쉬운 성적이었다. 그렇지만 근래에 알고리즘을 전혀 공부하.. 2023. 1. 3.
그리디 알고리즘 - 1이 될 때까지 난이도 : 하 [문제] 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 구하는 프로그램 작성하시오. [입력 조건] 첫째 줄에 N(2 2023. 1. 3.
그리디 알고리즘 - 숫자 카드 게임 난이도 : 하 [문제] 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 카드들이 N X M 형태로 놓여 있을 때, 게임의.. 2023. 1. 3.
그리디 알고리즘 - 큰 수의 법칙 난이도 : 하 [문제] 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 방법이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 .. 2023. 1. 1.
그리디 알고리즘 이론 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것을 고르는 방법이다. (탐욕법이라고도 한다.) 합이 21인 5 - 7 - 9 루트가 아닌, 합이 19인 5 - 10 - 4 루트를 선택하게 된다. 즉, 최적의 해를 보장할 수 없는 경우도 있다. 하지만 코딩테스트에서 그리디 문제가 출제가 된다면, 그리디로 얻은 결과가 최적의 해인 경우가 많다. 따라서, 그리디로 풀면 최적의 해가 나오는지 판단하는 능력이 필요하다. 만약 화폐단위가 500, 400, 100이라면 그리디 알고리즘은 적용될 수 없다. 예를 들어, 800원은 그리디 알고리즘에 의해 500+100+100+100로 구성되지만, 실제 해는 400+400이다. 2023. 1. 1.

티스토리툴바