전체 글
-
백준 20365번: 블로그2 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 5. 21:56
https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 접근 문제로 주어지는 글자의 최대 길이는 50만이다. 때문에 모든 경우의 수를 탐색해 가장 적은 작업 횟수를 구하는 방법은 당연하게도 시간 초과가 뜬다. 어떤 선택이 가장 적은 작업 횟수를 구할 수 있는지 그 최선의 방법을 확인해봐야 한다. 사실 어려운 조건이 아니라 방법을 쉽게 파악할 수 있을 것이다. 처음에서 마지막까지 전부 하나의 색깔로 칠하고 중간중간 다른 색깔이 들어가있는 것을 파악하는..
-
백준 12018번: Yonsei TOTO (Python/Java)Algorithm/Algorithm Problem 2022. 1. 4. 21:48
https://www.acmicpc.net/problem/12018 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 접근 문제를 보고 가장 먼저 생각한 것은 '현재 입력한 과목을 신청할 때, 내가 최소로 투자할 마일리지'였다. 마일리지를 최소로 사용해야 다른 과목에 투자할 마일리지가 많아지는 건 너무 당연한 사실이니까. 우선 내가 각 과목마다 투자할 '최소 마일리지 배열'을 만든 뒤 본격적으로 문제 풀이에 들어갔다. 문제 조건에 따르면 마일리지는 총 100점까지 주어진다. 즉, 학생들이 배팅할 마일리지..
-
백준 1343번: 폴리오미노 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 3. 20:58
https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 접근 이 문제 또한 기본적인 형태의 그리디 알고리즘 문제였다. 해당 문제에서 주의깊게 살펴봐야 할 조건은 '사전 순으로 가장 앞서는 답'이다. 사전 순으로 가장 앞선다는 이야기는 AAAA와 BB 둘 다 동시에 들어갈 수 있을 때, AAAA가 들어가는 것을 출력해야 한다는 뜻이다. 즉, 해당 문제에서 답을 구하기 위해 해야하는 최선의 선택은 'BB보다 AAAA가 먼저 나오는 조합'이다. 우선 입력된 문자열을 for문으로 돌려, '.'이 나올 때까지의 문자 수를 구했다. 예를 들어 예제 3번처럼 'XXX..
-
백준 16435번: 스네이크 버드 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 2. 18:32
https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 접근 그리디 알고리즘의 개념을 익히는 단계에서 풀어볼 만한 아주 간단한 문제였다. 그리디 알고리즘은 현재 단계에서 최선의 선택을 해야 한다. 이 문제에서 최선의 선택이란, 자신이 먹을 수 있는 가장 낮은 높이의 과일부터 순서대로 하나씩 먹으며 길이를 늘리는 것이다. 이를 위해 과일 리스트들을 높이가 낮은 순서대로 정렬한 뒤, 현재 스네이크버드의 ..
-
그리디 알고리즘(Greedy Algorithm)Algorithm/Algorithm Categories 2022. 1. 1. 19:35
기본 개념 그리디 알고리즘(greedy algorigthm, 탐욕 알고리즘)이란 선택의 상황에서 현재 가장 최선이라고 생각되는 것을 선택해 나가 결과를 도출하는 알고리즘이다. 현재 최적인 값만 탐색하면 되기 때문에 계산 속도가 빨라 실용적이라는 장점이 있으나, 최종 값이 최적 값이라는 보장이 없다는 단점이 존재한다. 그리디 알고리즘을 사용할 때에는 두 가지 조건이 만족되어야 한다. 탐욕 선택 속성(greedy choice property) 최적 부분 구조(optimal substructure) '탐욕 선택 속성'은 현재 선택이 다음 선택과 무관해야 한다는 조건이고, '최적 부분 구조'는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 두 조건을 만족하지 않다면 그리디 알고리즘을 사용했을 때 ..