전체 글111 백준 2109번 : 순회 강연 https://www.acmicpc.net/problem/2109 저명한 학자가 가장 많은 페이를 받을 수 있도록 도와드려야 합니다. 풀이 이 문제가 그리디적인 해결이 가능할까 라고 고민이 될 때가 많습니다. 그때 저 나름에 비법이 있습니다. 비밀인데 "선택을 해야하는 과정에서 다른 경우를 배제하고 선택할 수 있으면 그리디"입니다. 네? 그게 그리디 알고리즘의 기본 아니냐고요? 그럼 조금 더 설명을 해보겠습니다 이 문제에서, 학자는 돈을 최대한 많이 벌고 싶습니다. 오직 돈. 이러한 욕심을 채우기 위해서는 어떤 강의를 선택해야 할까요? 당연히 돈을 많이 주는 강의를 선택해야 합니다. 그럼 가장 많은 돈을 벌기위한 강의 스케줄을 구성하면서, 가장 페이가 많은 강의를 포기할 수 없습니다. 위 말을 좀 정.. 2025. 4. 7. 백준 9007번 : 카누 선수 문제 : https://www.acmicpc.net/problem/9007 카누 선수입니다. 경주에서는 얼마나 빠르게 결승선에 도달했는지 시간이 중요합니다. 하지만 분명 완주했다는 것도 박수를 받아야 합니다. 하지만 코테에서는 그렇지 않습니다. 정말 슬픈 일이죠. 시간이 중요합니다. N명의 학생이 있는 4개의 반에서 한명씩 뽑아 그 합이 K와 가장 가까운 값을 구해야 합니다. 최적화 문제입니다. 3초라는 낭낭한 시간에 혹시나 하는 마음으로 모든 경우를 확인하면 시간초과가 반겨줍니다. 처음에 제가 생각한 방법은 방문 숫자에 대한 최적화 방법이었습니다. Set [4]을 사용하여, 각 단계에서 이미 방문한 적 있는 숫자를 체크하여 중복을 제거하는 방향으로 구현했었습니다. 메모리 초과가 나왔습니다. 메.. 2025. 3. 23. 백준 22861번 : 폴더 정리(Large) 문제 : https://www.acmicpc.net/problem/22861 문제의 조건을 이해하는 것이 문제입니다. 저는 천천히 문제를 읽으면서, 어떤 기능이 필요할지 정리를 먼저 했습니다. 1. 폴더와 파일의 처음 입력값에 대해.초기 폴더 계층 구조를 문제에서 주어질 때, 2가지의 경우가 있습니다. 1) 폴더에 파일 넣기, 2) 폴더에 폴더 넣기 2. 특정 폴더를 다른 폴더의 하위로 옮기기이 과정에서 주요한 조건은 "하나의 폴더에 동일한 파일의 이름이 존재할 수 없다"입니다. 3. 특정 폴더의 파일의 수 및 파일의 종류를 구하기 이를 바탕으로, 폴더라는 클래스를 생성했습니다. Class Folder- Set subFolder- Set subFiles "하나의 폴더에 동일한 파일(폴더)의 이름이.. 2025. 3. 23. 백준 10597번 : 순열장난 문제 : https://www.acmicpc.net/problem/10597 요소에 대한 모든 케이스를 하나씩 확인해 간다면 쉽게 정답을 향해 갈 수 있습니다. 심지어 친절하게도 수열의 형태가 다양한 경우 그중 아무거나 하나만 출력해도 됩니다. 다만, 위 과정의 시간복잡도에 대해 생각을 해보니, 생각이 많아지기 시작했습니다. 우선 입력값을 보면.. - N은 최대 50개의 수- 1초 입력받는 값이 최대 50개의 수로 이뤄져있다는 것을 통해 문자열의 길이가 최대 9 +(50 - 9 ) * 2 = 91이라는 것을 알 수 있습니다. 하지만 앞서 말한 "모든 케이스의 확인" 에 대해 저는 아래와 같이 생각을 했습니다. input : ... abc..(a, b, c a를 기준으로 수를 선택 할 수 있는 경.. 2025. 3. 18. [문제 풀이] 백준 2616 소형기관차 문 제 : https://www.acmicpc.net/problem/2616 처음에는 그리디로 문제인 줄 바로 코딩할까 생각하다가, 오랜만에 코테를 푸는 거라 의심하면서 조심스럽게 다시 생각해 봤습니다. "그리디 문제인가? " 에 대해서는 "매 순간 최적의 해가 정답으로 이어지는가?" 에 대해 생각을 해보면 된다는 것을 알지만 쉽지는 않죠. 만일 기차가 5 10 6 8 1 1 1 인 경우, 그리디로 접근하면 1번 객차에는 가장 합이 큰 10,6 객실을 선택할 것입니다. 하지만 문제의 정답은 10 과 6이 동시에 선택되서는 안됩니다. -> 노 그리디 문제 브루트 포스 접근은 시간 복잡도를 어림잡아보면 안 된다는 사실을 알 수 있습니다. 제가 알고있는 시간을 절약하면서 모든 경우를 확인하는 알고리.. 2025. 1. 3. [문제 풀이] 백준 1167번 트리의 지름 문제 링크 : https://www.acmicpc.net/problem/1167 문제를 풀기 전, 트리의 정의를 먼저 보고 가겠습니다. https://velog.io/@kjh107704/%ED%8A%B8%EB%A6%AC-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B8%B0%EC%B4%88 [ 트리 ] 트리의 기초트리.. 그래프에 이어 많이 들어보고 많이 안다고 생각하는 친구이나, 사실상 아무것도 아는 게 없었던 친구. 오늘 이후로 트리 까먹지 말자velog.io 간단하게 요약하면, 사이클이 없는 그래프입니다. 풀이문제에서 구하라는 트리의 지름이 무엇인지에 대해 먼저 보고 가겠습니다. 트리 1에서 서로 가장 먼 두 노드 간의 거리를 트리의 지름이라고 문제에서 말해주고 있습니다. 만일 .. 2024. 11. 15. 이전 1 2 3 4 ··· 19 다음
