이분탐색9 [백준 1072] 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 투포인터 문제이다. 코드는 어렵지 않지만 투포인터를 떠올리긴 쉽진 않은거 같다 ㅠ while문을 돌리면 TLE가 발행한다. 이 문제의 또다른 포인트는 롱롱과 인트 범위라고 생각하는데 승률을 구하는 경우 소수점 아래는 버림하므로 먼저 100을 곱하고 시작하는 게 맞다. 이 경우 분자의 최댓값이 10^9이므로 100을 곱하면 INT 범위를 넘어선다. 따라서 N과 D는 롱롱이 되어야 한다. in.. 2021. 6. 20. [알고리즘] 이분탐색 Binary Search O(n)이 걸리는 선형 탐색을 O(log n)로 줄일 수 있는 방법이다. 일반적으로 이분탐색이라 하면 // 주어진 조건 내에서 최솟값을 구하라고 할 때 int left = 0, right = MAX; while(left 2021. 2. 1. [프로그래머스 2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr ㅎㅎ.. 새로운 문제가 나오면 전혀 접근을 못하는게 문제다. 문제의 접근법에 대해 공부해야 할 것 같다. 이중 포문을 돌려도 문제가 해결가능하지만 시간복잡도가 n^2이다. for int i=1; i 2021. 1. 21. [백준 1477] 휴게소 세우기 www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 이분탐색이라는 걸 알았는데도 생각해내는데 오래걸렸다..ㅠㅠ 1. 거리를 기준으로 삼아서 mid 2. 거리가 조건에 충족하는지 여부에 따라 (cnt==m?) 3. start, end범위가 달라진다. 거리 계산을 쉽게하기 위해 0과 l-1(고속도로 끝자락엔 휴게소 세울 수 없음)을 넣어주고 소팅을 해주었다. 모든 거리 차에 대해 mid 이하를 갖는 휴게소를 총 몇 개 세울 수 있는 지 계.. 2020. 12. 28. 이전 1 2 3 다음