본문 바로가기

이분탐색

 (5)
[백준] 1072번: 게임 - JAVA 🔗 문제 링크 BOJ 1072번: 게임 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1️⃣ 이분 탐색 📝 풀이 과정 새로운 게임을 하게 되면 계산되는 확률은 $((y+횟수) \times 100) / (x + 횟수)$ 따라서 해당되는 횟수가 최소로 증가할 때 확률의 값이 변하는 경우를 찾으면 된다. 주어진 게임의 2배만큼 진행했는데도 확률이 변하지 않았다면 더이상 변하지 않기 때문에, 0부터 최고 1,000,000,000번 진행했을 때까지 이분탐색을 통해 값을 찾을 수 있다. 💡 부동소수점 오차 변수..
[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 가사 검색 programmers.co.kr 1️⃣ Trie 📝 풀이 과정 words의 길이는 100,000개, queries의 길이는 100,000개로 단순 탐색시 시간 초과가 발생한다. 다음으로 생각한 풀이는 Trie를 사용하는 방법이었다. words를 모두 Trie에 insert한 다음 queries를 통해 문자열을 검색할 때, 삽입된 문자열의 길이를 모른다면 탐색하기 어렵다. 때문에, Trie의 노드마다 lenMap을 생성하였다. key는 삽입된 문자열의 길이고, value는 해당 길이의 문자열의 개수를 가지고 있다. 따라서 Trie의 node 위치에 도달했을 때, 해당 노드까지 도달..
[프로그래머스] 순위 검색 / 2021 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 순위 검색 / 2021 KAKAO BLIND RECRUITMENT
[프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십 - JAVA 🔗 문제 링크 [프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 📝 풀이 과정 돌의 최솟값을 기준으로 이분탐색하는 방법을 사용했다. 범위는 돌의 크기인 1 ~ 200,000,000으로 지정해주었다. N-1번 니니즈까지 길을 건넜다고 가정하고 N번째 니니즈가 길을 건너는 차례라고 생각한다. K번 이내의 거리에 N이상의 값이 존재해야 길을 건널 수 있기 때문에 N미만의 값이 연속적으로 k개 이상 나온다면 길을 N번은 건널 수 없다는 의미가 된다. 따라서 범위를 줄여주고 다시 탐색을 시작해주고, 만약 연속 값이 k보다 작다면 길을 건널 수 있는 경우로 값을 저..
[백준] 1800번: 인터넷 설치 - JAVA 🔗 문제 링크 BOJ 1800번: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝 풀이 과정 처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다... 계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다. 최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개..

티스토리툴바