Algorithm
-
백준 5557번: 1학년 (Python/Java)Algorithm/Algorithm Problem 2022. 4. 9. 17:45
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 접근 점화식만 제대로 찾는다면 어렵지 않게 풀 수 있는 문제다. 예제를 통해 풀이를 생각해보자. 총 열한 개의 숫자가 주어지고, 숫자 배열은 [8, 3, 2, 4, 8, 7, 2, 4, 0, 8, 8]이다. 여기서 배열의 가장 마지막 수는 연산을 통해서 '만들어야 하는 숫자'지 실제 연산에 쓰이는 숫자가 아니다. 즉, 우리가 실제로 쓸 숫자 배열은 마지막 인덱스 숫자를 뺀 [8, 3, 2,..
-
백준 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 접근 만들 수 있는 단어를 찾기 위해 몇 번씩이나 주어진 문자열을 반복 탐색하는 것은 비효율적이고 연산이 늘어난다. 이런 연산을 줄이기 위해 최대한 주어진 문자열 탐색을 줄이도록 하겠다. 이번 풀이에서는 문자열을 딱 한번 탐색할 것이다. 그만큼 아..
-
백준 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이나 같은 건데 굳이 정렬을...? 왜 그랬냐 물어본다면, 어....
-
이분탐색 (Binary Search)Algorithm/Algorithm Categories 2022. 3. 27. 18:06
기본 개념 배열 내의 특정 값을 찾는 기초적인 알고리즘이다. 특정 값을 찾기 위해 모든 데이터를 순차 탐색을 하는 것이 아니라 탐색 범위를 반씩 줄여나가며 탐색을 진행한다는 특징을 가지고 있다. 여기서 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. 특정 조건을 토대로 범위를 절반씩 줄여나가기 때문에 정렬되지 않은 배열에서 이분 탐색은 사용할 수 없다. 이분 탐색을 구현할 때 변수를 보통 세 가지를 사용한다. start, mid, end 세 가지 변수를 통해 현재 탐색 범위의 시작은 start, 탐색 범위의 끝은 end, 그 중간 값은 mid로 사용한다.(물론 변수 명은 개인에 따라 바뀔 수 있다). 이 세 변수를 통해 찾으려는 데이터와 중간 값 위체에 있는 데이터를 반복적으로 비교해서 특정 값을 찾..
-
백준 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로 만들어야 한다고 생각해보..
-
백준 11497번: 통나무 건너뛰기 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 22. 23:22
https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 접근 반복 for문을 돌려서 매번 두 수의 차를 구하고 최댓값을 구한 뒤 배열에 집어넣으면 무조건 시간 초과가 날 수밖에 없는 문제. 때문에 수들을 정렬시킬 규칙을 찾아야 한다. 사실 이 부분에서 조금 헷갈리긴 했으나 잘 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 우선 숫자들을 순서대로 정렬한다. 그 뒤 첫 번째에 가장 작은 수, 마지막에 다음 수, 두 번째에 다음 수, 뒤에서 두 번째에 다..
-
백준 2036번: 수열의 점수 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 21. 23:23
https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 접근 그리디 알고리즘의 기본 원리만 생각하며 원론적으로 접근해봤다. '배열에서 가장 큰 숫자를 만들어 더하는 것'이 현재 단계에서 해야 하는 최선의 선택이다. 이 부분을 구현하기 위해 우선 두 가지 경우로 나눠서 생각해봤다. 첫 번째는 홀수인 경우다. 홀수인 경우는 무조건 두 개를 곱해야 최종 값이 가장 큰 값이 나온다. 홀수 숫자의 개수가 홀수개인 경우에는 두 개씩 곱하다가 마지막 홀수를 더해야..
-
다이나믹 프로그래밍 (Dynamic Programming, DP)Algorithm/Algorithm Categories 2022. 3. 13. 01:50
기본 개념 다이나믹 프로그래밍(동적 계획법)은 큰 문제를 여러 작은 문제들의 해결을 통해 풀어가는 알고리즘을 뜻한다. 쉽게 말해 하나의 큰 문제를 쪼개 작은 여러 개의 문제로 만들고, 이 작은 문제들을 해결하다 보면 큰 문제를 해결할 수 있게 된다는 개념이다. (작은 문제들은 큰 문제의 조각들이니까) 언뜻 보면 분할 정복(Divide and Conquer)과 비슷하게 생각할 수 있지만 다이나믹 프로그래밍이 가진 다음 두 가지 조건으로 분할 정복과 구별된다. 최적 부분 구조(optimal substructure) 중복된 하위 구조(overlapping subproblems) 최적 부분 구조는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 큰 문제를 여러 작은 문제들로 나눠놨으니 이는 당연한 ..