본문 바로가기

이분탐색8

[프로그래머스 Lv3] : 징검다리 건너기 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내구도가 정해진 징검다리가 있을 때, 건너갈 수 있는 니니즈 친구들의 수의 최대를 리턴하자. 풀이 직접 한 명, 한 명 건너가면서 돌의 내구도를 감소시키면 물론 정답은 출력이 될 것이다. 하지만 효율성 테스트에서 시간초과가 나게 된다. 그래서 내가 처음 생각했던 방법은 내구도가 0인 돌이 연속해서 K개 이상 있을 때, 그때는 더 이상 사람이 건너가지 못하게 된다. 그래서 다리를 K개씩 .. 2022. 7. 20.

[프로그래머스 Lv4] : 가사 검색 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 키워드가 담긴 배열이 주어졌을 때, 각 키워드 별로 매치된 단어가 몇 개인지 리턴하자. 오답 나는 단어와 키워드를 직접 비교를 하는 방식을 선택했다. 먼제 단어를 시작하는 알파벳, 단어의 길이를 기준으로 분류했다. 단어의 길이와 키워드의 길이가 일치하지 않으면 비교할 필요가 없기 때문이다. 이때 키워드에 물음표가 뒤에 붙어있다면, 문자를 앞에서부터 비교하고 물음표가 나오는 순간부터는 비.. 2022. 7. 12.

[프로그래머스 Lv3] : 금과 은 운반하기 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 새로운 도시를 짓기위해 여러 나라에서 금과 은을 운송한다. 이때 필요한 금과 은을 모두 운송하기위해 필요한 최소 시간을 구해보자. 풀이 각 도시마다 자원의 양이 한정되어있고, 한 번에 운반할 수 있는 양과, 한 번 운반에 필요한 시간이 모두 다르다. 최적의 시간을 구하기 위해서 모든 경우의 수를 다 따져보기엔 말이 안된다. 그래서 나는 제한시간을 걸어두고, 이 시간안에 정해진 금과 은을.. 2022. 7. 11.

[프로그래머스 Lv4] : 징검다리 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 바위를 n개 제거했을 때, 각 지점 사이의 거리의 최솟값이 최대가 되도록 바위를 제거하는 문제. 풀이 풀이 알고리즘 각 지점들 사이에 벌어져야할 최소 간격을 "이분탐색"을 통해서 탐색한다. 벌어저야할 간격의 범위는 0 ~ distance 이내 일 것이다. L = 0, R = distance로 잡고 mid 값을 지점들 사이 벌어져야할 최소 .. 2022. 6. 21.

[프로그래머스 Lv3] : 입국심사 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 모든 입국자를 심사하기 위해 걸리는 최소시간을 리턴하는 문제. 풀이 각 심사관마다 심사하는데 걸리는 시간은 다르며 이는 입력으로 주어진다. 풀이 알고리즘 주어진 시간이 T라고 했을 때, 임의의 i 심사관이 T시간동안 심사할 수 있는 사람의 수는 T / times[ i ] 를 내림한 것과 같다. 그렇다면 T 시간동안 모든 심사관이 입국 심사할 수 있는 사.. 2022. 6. 21.

[BOJ] 9879 : Cross Country Skiing 문제 링크 https://www.acmicpc.net/problem/9879 9879번: Cross Country Skiing The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 N >> M; int L = INF; int R = -1; for (int i = 0; i Map[i][j]; L = min(Map[i][j], L); R = max(Map[i][j], R); } } for (int i = 0; i num; if (num == 1) { waypoints.push_back({ i,j }); is_waypoint[i][j] = true; } } } R = R - L;.. 2022. 5. 3.

[BOJ] 1800 : 인터넷 설치 문제 링크 https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1번과 N번 컴퓨터를 연결시키기 위해 필요한 비용중 최대값의 최소가 되도록하는 문제. 풀이 일단 1번과 N번 컴퓨터를 최대 효율로 연결시켜야 하므로 다익스트라 알고리즘을 사용해야하는 것을 알 수 있다. 그런데 기존 다익스트라는 비용이 계속해서 누적된다. 그리고 그 누적 비용이 가작 적게 들도록 N에 도달하는 것이 보통인데, 여기서는 비용들 중 가.. 2022. 4. 20.

[BOJ] 24887 : 최대한의 휴식 문제 링크 24887번: 최대한의 휴식 (acmicpc.net) 24887번: 최대한의 휴식 Amel은 SKH 회사 내에서 일을 잘하기로 소문난 유능한 사원이다. 그러나, 체력이 매우 안 좋은 Amel은 하루 동안 일하고 나면 빠르게 지쳐버리기 때문에 한 번 일하고 난 후 가능한 오랜 기간 동안 www.acmicpc.net 숭고한 대회 DIvision2 E번 문제. 대회 당일엔 앞에서 막히는 바람에 읽어보지도 못했다 ㅎㅎ; 풀이 연속으로 쉰 날의 최소값의 최대값을 구하는 문제다. 연속으로 쉬는날의 최소값을 이분탐색으로 찾아준다. 초기 범위는 Left = 0, Right = N 으로 설정해줬다. DP배열을 선언해서 DP[i] 연속으로 쉬는날의 최소가 mid 일때, i번째 날까지 채울수 있는 할당량의 최대값.. 2022. 3. 30.

이전 1 다음

티스토리툴바