코드 주유소 코드 주유소

Greedy

• 백준 24524번: 아름다운 문자열 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 30. 22:18

  https://www.acmicpc.net/problem/24524 24524번: 아름다운 문자열 첫째 줄과 둘째 줄에 영어 알파벳 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. ($1\leq \left|S \right|\leq 10^6$, $1\leq \left|T \right|\leq 26$, $\left|T \right|\leq \left|S \right|$, $\left|S \right|$와 $\left|T \ www.acmicpc.net 접근 만들 수 있는 단어를 찾기 위해 몇 번씩이나 주어진 문자열을 반복 탐색하는 것은 비효율적이고 연산이 늘어난다. 이런 연산을 줄이기 위해 최대한 주어진 문자열 탐색을 줄이도록 하겠다. 이번 풀이에서는 문자열을 딱 한번 탐색할 것이다. 그만큼 아..

  Read More
• 백준 6068번: 시간 관리하기 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 28. 22:33

  https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1= 0){ System.out.println(thisTime); }else{ System.out.println(-1); } } } 후기 포스팅하며 풀이과정을 살펴보다가 생각난 건데, 사실 위 코드에는 굉장히 쓸데없는 정렬이 들어가 있다. 사실 정렬은 '끝내야 하는 시간의 내림차순'으로만 정렬하면 된다. 근데 위 코드에선 끝내야 하는 시간이 같다면 걸리는 시간을 기준으로 다시 내림차순을 해줬다. 전혀 필요 없는 연산이다. 정렬하면 뭐할 거냐, 1+2나 2+1이나 같은 건데 굳이 정렬을...? 왜 그랬냐 물어본다면, 어....

  Read More
• 백준 17828번: 문자열 화폐 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 27. 13:53

  https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 접근 사전 순으로 가장 빠른 문자열을 구하라는 말은 A부터 Z까지 순서대로 문자가 들어가야 한다는 뜻이다. 하지만 문자열 길이는 정해져 있고, 가장 처음에 A 하나 넣고 그 뒤에 조합될 수 있는 모든 경우의 수를 비교하기에는 연산이 비상식적으로 늘어날 것이 분명하다. 때문에 조금 더 과감해졌다. 모든 문자열을 A로 채워 넣었다. 예시를 살펴보자. 만일 길이가 5인 문자열을 통해 가치를 7로 만들어야 한다고 생각해보..

  Read More
• 백준 11497번: 통나무 건너뛰기 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 22. 23:22

  https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 접근 반복 for문을 돌려서 매번 두 수의 차를 구하고 최댓값을 구한 뒤 배열에 집어넣으면 무조건 시간 초과가 날 수밖에 없는 문제. 때문에 수들을 정렬시킬 규칙을 찾아야 한다. 사실 이 부분에서 조금 헷갈리긴 했으나 잘 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 우선 숫자들을 순서대로 정렬한다. 그 뒤 첫 번째에 가장 작은 수, 마지막에 다음 수, 두 번째에 다음 수, 뒤에서 두 번째에 다..

  Read More
• 백준 2036번: 수열의 점수 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 21. 23:23

  https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 접근 그리디 알고리즘의 기본 원리만 생각하며 원론적으로 접근해봤다. '배열에서 가장 큰 숫자를 만들어 더하는 것'이 현재 단계에서 해야 하는 최선의 선택이다. 이 부분을 구현하기 위해 우선 두 가지 경우로 나눠서 생각해봤다. 첫 번째는 홀수인 경우다. 홀수인 경우는 무조건 두 개를 곱해야 최종 값이 가장 큰 값이 나온다. 홀수 숫자의 개수가 홀수개인 경우에는 두 개씩 곱하다가 마지막 홀수를 더해야..

  Read More
• 백준 12931번: 두 배 더하기(Python/Java)

  Algorithm/Algorithm Problem 2022. 2. 13. 14:00

  https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 접근 이런 형식의 문제는 여러 문제들을 통해서 몸소 확인했듯이, 0이 나열된 배열에서 목표 배열까지 만드는 것이 아니라, 목표 배열에서 역으로 연산해 0이 나열된 배열을 만드는 것이 훨씬 좋은 풀이 방법이다. 그렇다면 목표 배열을 기준으로 0으로 이루어진 배열을 만들어보자. 우선 주어진 연산을 반대로 생각해야 한다. 1을 더하는 것은 1을 빼는 것으로, 배열 전체를 2배로 만드는 ..

  Read More
• 백준 17939번: Gazzzua(Python/Java)

  Algorithm/Algorithm Problem 2022. 2. 11. 10:32

  https://www.acmicpc.net/problem/17939 17939번: Gazzzua 최대의 수익을 얻으려면, 일단 가격이 1, 5일 때 1개씩 사서 10일 때 샀던 코인 2개를 다 팔고, 이어서 가격이 2일 때 1개를 사고 4일 때 판다. 이 경우, 총 (10-1) + (10-5) + (4-2) = 16의 수익을 얻을 수 있 www.acmicpc.net 접근 실제 가상화폐든, 그리디 알고리즘의 가상화폐든 이득을 얻는 방법은 간단하다. 저점에서 사고 고점에서 파는 것이다. 만고불변의 진리. 그렇다면 이 문제는 어떻게 해결해야 할까? 저점에서 사고 고점에서 팔면 되지!! 우선 현재 주어진 값들 중에서 높은 값이 어디 있는지 확인한다. 그 고점이 나오기 전까지는 무조건 매입한다. 왜냐? 해당 고점..

  Read More
• 백준 11509번: 풍선 맞추기 (Python/Java)

  Algorithm/Algorithm Problem 2022. 1. 28. 12:02

  https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 접근 이 문제의 키포인트는 현재 높이의 화살과 이 화살이 풍선을 만날 수 있도록 체크하는 방법이다. 이 부분만 구현한다면 문제는 굉장히 쉽다. 우선 문제 조건을 확인해보자. 문제 조건에서 높이는 1에서 1000000까지다. 우리는 배열을 통해서 높이에 있는 화살 개수를 체크할 것이다. 이 경우에는 설정을 어떻게 해야 할까? 높이를 인덱스 번호로 두고 해당 인덱스에 들어있는 값을 화살의 개수로 두면 될 것이다. 물론 배열의 인덱스는 0부터 시작하니 정..

  Read More