백준 9007번 : 카누 선수
문제 : https://www.acmicpc.net/problem/9007 카누 선수입니다. 경주에서는 얼마나 빠르게 결승선에 도달했는지 시간이 중요합니다. 하지만 분명 완주했다는 것도 박수를 받아야 합니다. 하지만 코테에서는 그렇지 않습니다. 정말 슬픈 일이죠. 시간이 중요합니다. N명의 학생이 있는 4개의 반에서 한명씩 뽑아 그 합이 K와 가장 가까운 값을 구해야 합니다. 최적화 문제입니다. 3초라는 낭낭한 시간에 혹시나 하는 마음으로 모든 경우를 확인하면 시간초과가 반겨줍니다. 처음에 제가 생각한 방법은 방문 숫자에 대한 최적화 방법이었습니다. Set [4]을 사용하여, 각 단계에서 이미 방문한 적 있는 숫자를 체크하여 중복을 제거하는 방향으로 구현했었습니다. 메모리 초과가 나왔습니다. 메..
문제 : https://www.acmicpc.net/problem/22861 문제의 조건을 이해하는 것이 문제입니다. 저는 천천히 문제를 읽으면서, 어떤 기능이 필요할지 정리를 먼저 했습니다. 1. 폴더와 파일의 처음 입력값에 대해.초기 폴더 계층 구조를 문제에서 주어질 때, 2가지의 경우가 있습니다. 1) 폴더에 파일 넣기, 2) 폴더에 폴더 넣기 2. 특정 폴더를 다른 폴더의 하위로 옮기기이 과정에서 주요한 조건은 "하나의 폴더에 동일한 파일의 이름이 존재할 수 없다"입니다. 3. 특정 폴더의 파일의 수 및 파일의 종류를 구하기 이를 바탕으로, 폴더라는 클래스를 생성했습니다. Class Folder- Set subFolder- Set subFiles "하나의 폴더에 동일한 파일(폴더)의 이름이..
문제 : https://www.acmicpc.net/problem/10597 요소에 대한 모든 케이스를 하나씩 확인해 간다면 쉽게 정답을 향해 갈 수 있습니다. 심지어 친절하게도 수열의 형태가 다양한 경우 그중 아무거나 하나만 출력해도 됩니다. 다만, 위 과정의 시간복잡도에 대해 생각을 해보니, 생각이 많아지기 시작했습니다. 우선 입력값을 보면.. - N은 최대 50개의 수- 1초 입력받는 값이 최대 50개의 수로 이뤄져있다는 것을 통해 문자열의 길이가 최대 9 +(50 - 9 ) * 2 = 91이라는 것을 알 수 있습니다. 하지만 앞서 말한 "모든 케이스의 확인" 에 대해 저는 아래와 같이 생각을 했습니다. input : ... abc..(a, b, c a를 기준으로 수를 선택 할 수 있는 경..
[문제 풀이] 백준 2616 소형기관차
문 제 : https://www.acmicpc.net/problem/2616 처음에는 그리디로 문제인 줄 바로 코딩할까 생각하다가, 오랜만에 코테를 푸는 거라 의심하면서 조심스럽게 다시 생각해 봤습니다. "그리디 문제인가? " 에 대해서는 "매 순간 최적의 해가 정답으로 이어지는가?" 에 대해 생각을 해보면 된다는 것을 알지만 쉽지는 않죠. 만일 기차가 5 10 6 8 1 1 1 인 경우, 그리디로 접근하면 1번 객차에는 가장 합이 큰 10,6 객실을 선택할 것입니다. 하지만 문제의 정답은 10 과 6이 동시에 선택되서는 안됩니다. -> 노 그리디 문제 브루트 포스 접근은 시간 복잡도를 어림잡아보면 안 된다는 사실을 알 수 있습니다. 제가 알고있는 시간을 절약하면서 모든 경우를 확인하는 알고리..
[문제 풀이] 백준 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에서 서로 가장 먼 두 노드 간의 거리를 트리의 지름이라고 문제에서 말해주고 있습니다. 만일 ..
[문제 풀이] 가장 긴 증가하는 부분 수열 (LIS)
안녕하세요. 오늘의 문제는 LIS라고 불리는 가장 긴 증가하는 부분 수열 문제들의 해결 방식들에 대해 이야기해보겠습니다. 백준 번호 11722번https://www.acmicpc.net/problem/11722 (아 이 문제에서는 감소하는 수열이긴 한데 풀이법은 동일합니다.) 일단 모든 경우를 브루트 포스를 구한다면 얼마나 걸릴지 먼저 생각을 해보겠습니다. 수열 A의 크기 N에서 1개부터 N개까지 뽑는 경우의 수로 표현해야 할지 2^1000으로 표현해야 할지 고민이네요. 아무튼 둘 다 굉장히 오래 걸립니다. 그럼 어떤 규칙을 찾아야 합니다. 시간을 줄이기 위해서는 이미 한번 수행한 적이 있는 계산을 다시 수행하지 않아야 합니다. 다. 그 예를 들어보면 arrA = {1,2,3,4,6} / arrB={..