완전 탐색
[종만북 내용 메모]
6.7장에서 단순 완전 탐색 말고, 이를테면 n개의 사과 중 r개를 그냥 선택하는거 말고, 무게가 최소화 되도록 선택한다던지 이런 걸 "최적화 문제"라고 한다. 현대 계열 코테에서 볼 것 같은 문제. 자동차 디자인 등등 각종 공학에 최적화 문제 아주 빈번하게 등장.
대표적 예가 외판원 문제.
어떤 (최적화 혹은 그냥) 문제를 완탐으로 접근할 때 해야 할 첫번째 일은 시간 안에 답을 구할 수 있을지 확인하는 것
1107 리모컨 이건 그럭저럭 익숙해지긴 했으나... 아 여기에 나동빈 책에서 본것도 싣고...
카카오 2020 <자물쇠와 열쇠>: https://programmers.co.kr/learn/courses/30/lessons/60059?language=python3
처음엔 하도 어려워서 벙쪘다... 근데 결국 어케 하다보니 잘 풀리더라... 사실 맞춰보는 부분의 로직은 어렵지 않았다. 근데 좌표 전환하는 부분이 정말 끝내주게 애먹었다... 처음에 계속 잘못된 코드를 돌리다가 나중에 깨달았는데, 지금 구현하라면 뭐 4분면 나누고 엑스 와이 둘다양, 둘다음, 하나씩 양 음 뭐 이런것처럼 기준을 length//2로 해서 할수 있을 것 같지만 이미 더 좋은 방법을 알아버려서 ...
그 방법 코드를 꼭 기억했으면 좋겠고, 현재 작성된 나의 예술적 코드와, 아래 링크들을 공부하면 된다
https://mingrammer.com/understanding-the-asterisk-of-python/
14888: https://www.acmicpc.net/problem/14888
사실 완전탐색이라는 생각을 못했음 나동빈에선 문제 분류가 dbfs 로 되어있어서... 이게 대체 어케 그거지 싶었지...
글고 뭐 연산자 순서 원칙 고려 안하고 걍 무저건 앞에서부터 뒤로 계산해야 한다고 해서 뭔가 엄청난게 있다고 착각했었음..
하여간 그런 선 정보들에 압도되어 선입견을 가졌고 결국 도댕체가 어케 풀라는건지 모르겠어서(하나하나 다 따져보는 브루트포스가 아닌 뭔가가 있을줄로 안거임) 풀이봤더니 걍 브루트포스임 ㅎ; 중복순열인지 중복조합인지 써서 풀면 더 빨리 풀수있고 그것도 맞는풀이래 ㅋ;;;;;
1182: 실버 2의 무지 쉬운 문제 지만 dfs는 항상 위험하기 땜에 비트마스크로 풀어봤다. 그렇게 했을 때 시간은 당연 엄청 안나올거 알았지만, 원래 실버는 시간 여유를 비교적 많이 주기 땜에 통과했지... 근데 핵심은 다른 사람들 풀이다. 상위권 풀이가 전부 숫자들 배열을 반으로 나눈 담에 희한하게 푸는데 도대체 뭔 사고방식인질 모르겠음
카카오 2020 외벽점검: 분명 간단한건데도 이해도 안되고 풀이 계속 봤더니 풀기도 싫어서 당분간 방치할 예정.. 담에 생각나서 풀어보게 되면 이 영상 풀이로 공부하삼. https://youtu.be/yYc2KiCSIoA
(완전탐색) 1759: 순열조합인데 코드를 무지짧게 작성할수있는데 이걸 숙달해야함
리트코드 5942(쉬움)
- 1038: https://www.acmicpc.net/problem/1038
우선 푸는 동안 생각이 안나다가 오늘에서야 생각난 것.. 최대/한계가 얼마, 어디일까였는데 9876543210이잖아... 대단하다 정말... 그담에 분류상은 브루트포스인데 내가 여기에 넣은 이유는 굳이 설명 안하겠음. 골드는 항상 이런 아이디어를 요하기도 하고, 완탐 절대 아니라 생각해서 나는 무조건 아이디어가 있을 걸로 생각(계산량과 시간을 줄이는 아이디어). 내가 시도한 건 무지 먹방 문제처럼 개수를 줄이는 거였는데, 전혀 생각지 못한 방향이었군. 내 방법으로 풀어도 풀릴..수있지만 최악의 경우 따지면 시간 초과 가능하다고 생각했다. 그래서 이걸로 더 푸는 게 의미 없을 듯 해서 그냥 백준 최상위 풀이 공부 - 솔직히 이 풀이 조합 풀이에 비하면 이해 안됨. 그래서 더더욱 반드시 재도전할 문제다.
- 1963: https://www.acmicpc.net/problem/1963
완탐(소수 판별) & dbfs(검사 대상 추리기) 포함하는 전형적인 문제. 다만 각 로직을 언제 어디서 할 것이냐.. 풀이 방법이 다양하게 나올 수 있다보니 오히려 헷갈리고.. 여하여간 안풀림. 속도가 하도 늘어져서 그냥 풀이 보고 공부했는데, 유명한 풀이인 만큼 최상위 풀이가 워낙 고퀄이라 공부할 게 많은 문제. 지금은 너무 늘어져서 다음에 다시 와서 보려고 함