좀 더 어려운 그리디, 다이나믹 프로그래밍, 구현과 그래프와 관련된 알고리즘, 완전 탐색, 백트랙킹, 이분 탐색 을 이용하여 최적해 문제를 판정 문제로 바꾸어 푸는 법을 공부해봅시다. 대부분의 코딩 테스트는 해당 레벨 정도의 난이도로 출제됩니다.
최적해 문제는 주어진 조건에 맞는 최적의 해를 찾는 문제입니다. 예를 들면 배열에 존재하는 최댓값, 1000원으로 가장 많은 살 수 있는 물건의 개수 같은 문제들이 있습니다.
판정 문제는 단순하게 보자면 참이냐 거짓이냐로 볼 수 있습니다. 즉, 예-아니오로 대답을 할 수 있는 문제들을 말합니다. 예를 들면 10은 4로 나누어 떨어지는가? 와 같은 문제들이 있습니다.
최적해 문제를 판정 문제로 바꾸어 푸는 예로는 정수만 존재하는 배열 A에 존재하는 최댓값을 구하는 문제 를 배열 A에 x보다 큰 숫자가 존재하는가? 라는 판정 문제 Q(x)로 바꾼다면 Q(x-1) 이 참이고 Q(x) 는 거짓인 x 를 찾으면 됩니다.
이러한 판정 문제를 이분 탐색으로 풀기 위해선 어떻게 해야 할까요?? 이분 탐색을 사용하기 위해선 어떤 상황이여야 하는지 생각해봅시다!🔔
- BOJ 소용돌이 예쁘게 출력하기
- BOJ 한 줄로 서기
- BOJ 스타트링크 타워
- BOJ 피자 굽기
- BOJ 타일 위의 원
- BOJ 소코반
- BOJ 톱니바퀴
- BOJ 내리막길
- BOJ 드래곤 커브
- BOJ 아기 상어
- BOJ DFS와 BFS
- BOJ 최소 스패닝 트리
- BOJ 트리
- BOJ 게임
- BOJ 특정한 최단 경로
- BOJ 이분 그래프
- BOJ 숨바꼭질
- BOJ 벽 부수고 이동하기
- BOJ 네트워크 복구
- BOJ 키 순서
- BOJ 저울
- BOJ 가운데서 만나기
- BOJ 백도어
- BOJ 타임머신
- BOJ 골목길
- BOJ 집합의 표현
- BOJ 피리 부는 사나이
- BOJ 유니온 파인드 복원
- BOJ 트리의 순회
- BOJ 전화번호 목록
- BOJ 회사 문화1
- BOJ 트리 색칠하기
- BOJ LCA