분류 전체보기112 백준 17822 원판 돌리기 (Java) https://www.acmicpc.net/problem/17822 오래간만에 만나는 구현 문제입니다. 반갑지는 않습니다. 풀이복잡한 단계의 작업을 쪼개서 풀었습니다. 다만 조금 신경을 써줘야 하는 조건들이 있습니다. 1. 돌리기 단계Deque 자료 구조를 활용하였습니다. 시계 방향인 경우 맨 마지막 요소를 맨 앞으로 넣어주었습니다. * x 의 배수인 원판을 모두 돌려야 합니다 2. 중복 찾기탐색이 시작이 가능한 모든 정점에 그래프의 탐색과 다를 것 없이 상하좌우로 탐색을 해주었습니다.* 0번 인덱스와 마지막 인덱스가 서로 붙어있는 것을 주의해야 합니다! 3. 중복이 없는 경우중복이 없는 경우에는 원판에 남아있는 요소의 평균값과 비교를 통해 그 값보다 크면 -1 작으면 +1을 해줘야 합니다. * 평균이.. 2025. 4. 24. 백준 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. 이전 1 2 3 4 ··· 19 다음
