분류 전체보기361 [003]First Bad Version 문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3316/ 이분 탐색 문제입니다. mid를 구한 후 Bad Version이 나왔다면, 상한을 en = mid 으로 줄여서 탐색범위를 절반씩 줄여나가면 됩니다. 시간복잡도 O(logN) // The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { long long int st, en,mid, before; st = 0; en = (long long int).. 2020. 5. 16. [코딩테스트 연습] 지형 이동 문제: https://programmers.co.kr/learn/courses/30/lessons/62050최소 설치비용을 만족하려면 두 가지 조건을 만족해야 합니다. 1. 최소의 사다리 개수2. 사다리를 놓을 수 있는 위치들 중에 최소비용인 위치 1번에 대해 생각해보면 사다리 없이 이동할 수 있는 지점이 N개라고 하면 N-1개의 사다리만 놓으면 N개의 지점은 모두 연결이 됩니다. 여기서 이 문제가 MST 문제임을 알 수 있습니다. 2번에 대해서는 각 컴포넌트 중에서 경계점에 있는 좌표에 대해 엣지를 구합니다.Edge(현재 컴포넌트 번호, 연결되어있는 컴포넌트 번호, 사다리 비용) 이 엣지를 우선순위 큐에 넣고 작은 비용의 사다리부터 뽑도록 크루스칼 알고리즘을 돌리면여기서 뽑혀나온 N-1개의 엣지가 최소.. 2020. 5. 16. [코딩테스트 연습] 점프와 순간이동 문제: https://programmers.co.kr/learn/courses/30/lessons/12980 N이 10억이하의 자연수이므로 BFS 탐색을 하면 그대로 터지는 문제입니다. 순간이동은 공짜이므로 순간이동을 가장 많이 한다면 그 값이 최소비용이 될 것입니다. 그러면 주어진 수에서 점프하는 거리를 최대로 줄이다 보면 1을 초과하는 거리는 점프를 할 필요가 없습니다. 즉, 주어진 수를 이진수로 나타내면 1로 나타나는 지점이 어쩔 수 없이 점프를 해야하는 지점입니다. 그러니 이진수를 만든 후 거기서 1의 개수를 세면 그게 최소비용이 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter01.cc 2020. 5. 15. [코딩테스트 연습] 영어 끝말잇기 문제: https://programmers.co.kr/learn/courses/30/lessons/12981 단어의 중복 여부는 set으로 관리하고 단어의 마지막 단어만 char nxt로 관리하여 다음 단어의 첫 글자랑 같은 지 비교해주었습니다. 총 인원수가 N명일 때, M번째 순서에 탈락자가 발생했다면 M % N = N명의 인원 중 자신의 순서 M / N = 지나간 턴 횟수 위와 같은 관계가 성립합니다. 0부터 시작하니 둘 다 +1을 해줘야 원하는 숫자가 나옵니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter15.cc 2020. 5. 15. 이전 1 ··· 77 78 79 80 81 82 83 ··· 91 다음
