https://www.acmicpc.net/problem/4796
4796번: 캠핑
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.
www.acmicpc.net
그리디
| 백준 2805 : 나무 자르기 (0) | 2021.04.18 |
|---|---|
| 백준 13397 : 구간 나누기 2 (0) | 2021.04.16 |
| 백준 1654 : 랜선 자르기 (0) | 2021.04.16 |
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
이진 탐색의 대표적인? 문제??
경계값을 정확히 알아야 한다
만약 기업 코테처럼 정답 유무를 알 수 없다면 다 풀어놓고 틀리는 슬픈 상황이 일어날 것이다
무슨 차이가 있을까?
| 백준 4796: 캠핑 (0) | 2021.12.22 |
|---|---|
| 백준 13397 : 구간 나누기 2 (0) | 2021.04.16 |
| 백준 1654 : 랜선 자르기 (0) | 2021.04.16 |
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
13397번: 구간 나누기 2
첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수
www.acmicpc.net
완전 이분탐색 문제다. 이걸 제대로 풀지 못해서 랜선 자르기를 추가로 더 풀었다
중요한 포인트는, 완전 탐색처럼 모든 경우의 수를 찾아가면서 해를 찾는 것이 아니라
해를 정해두고 해당 해가 적합한지를 테스트, 적합하지 않다면 해를 조정해가면서 최적의 해를 찾는 것이 이분탐색의 주요 포인트라는 생각이 든다
이걸 제대로 풀었어야 했는데
ㅁ
| 백준 4796: 캠핑 (0) | 2021.12.22 |
|---|---|
| 백준 2805 : 나무 자르기 (0) | 2021.04.18 |
| 백준 1654 : 랜선 자르기 (0) | 2021.04.16 |
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
이분탐색 스킬을 올리기 위해 이분탐색 문제를 계속 풀었는데
풀라는 이분탐색으로는 안풀고 자꾸 요상한 방식으로 풀어대니까
정작 뻔한 이분탐색 문제에서 손도 못쓰고 나가떨어져서 제대로 풀어보고자 선택한 문제
근데 아직 완벽하게는 모르겠다...
중요한 포인트는, 완전 탐색처럼 모든 경우의 수를 찾아가면서 해를 찾는 것이 아니라
해를 정해두고 해당 해가 적합한지를 테스트, 적합하지 않다면 해를 조정해가면서 최적의 해를 찾는 것이 이분탐색의 주요 포인트라는 생각이 든다
| 백준 2805 : 나무 자르기 (0) | 2021.04.18 |
|---|---|
| 백준 13397 : 구간 나누기 2 (0) | 2021.04.16 |
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
| 백준 14465 : 소가 길을 건너간 이유 5 (0) | 2021.04.13 |
1477번: 휴게소 세우기
첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나
www.acmicpc.net
이진탐색 문제인데, 이진탐색으로 푸는 방법이 생각이 잘 안난다
뜬금없이 우선순위 큐로 푸는 방식이 떠올랐다 ㅡㅡ;
느흐느에서 본 문제랑 비슷한 느낌
| 백준 13397 : 구간 나누기 2 (0) | 2021.04.16 |
|---|---|
| 백준 1654 : 랜선 자르기 (0) | 2021.04.16 |
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
| 백준 14465 : 소가 길을 건너간 이유 5 (0) | 2021.04.13 |
| 백준 14468 : 소가 길을 건너간 이유 2 (0) | 2021.04.13 |
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00
www.acmicpc.net
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
반례
3
999999998 999999999 1000000000
5
-10 -8 -4 6 4
lowest 값을 하... 이거때문에 몇시간을 날려먹은건지
40%에서 틀리는 사람이 있다면 최대 / 최소 범위 설정을 한번 확인해보기 바람...!
| 백준 1654 : 랜선 자르기 (0) | 2021.04.16 |
|---|---|
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
| 백준 14465 : 소가 길을 건너간 이유 5 (0) | 2021.04.13 |
| 백준 14468 : 소가 길을 건너간 이유 2 (0) | 2021.04.13 |
| 백준 2110 : 공유기 설치 (0) | 2021.04.13 |
14465번: 소가 길을 건너간 이유 5
첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.
www.acmicpc.net
이렇게 풀어도 되나...?
이분탐색으로는 어떻게 푸는거지?
슬라이딩 윈도우를 사용했다고 생각했는데, 분류를 보니 스위핑이다
@.@
| 백준 1477 : 휴게소 세우기 (0) | 2021.04.15 |
|---|---|
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
| 백준 14468 : 소가 길을 건너간 이유 2 (0) | 2021.04.13 |
| 백준 2110 : 공유기 설치 (0) | 2021.04.13 |
| 백준 10451 : 순열 사이클 (0) | 2021.03.30 |
14468번: 소가 길을 건너간 이유 2
존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다. 이 소들은 자신의 습관대로 매일
www.acmicpc.net
건너간 이유 5의 징검다리 문제
ㅁㄴ
| 백준 2470 / 2467 : 두 용액 / 용액 (0) | 2021.04.14 |
|---|---|
| 백준 14465 : 소가 길을 건너간 이유 5 (0) | 2021.04.13 |
| 백준 2110 : 공유기 설치 (0) | 2021.04.13 |
| 백준 10451 : 순열 사이클 (0) | 2021.03.30 |
| 백준 15683 : 감시 (0) | 2021.03.26 |
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
이진탐색색 문제
처음에는 왜 이진탐색인지 몰랐다
지도같은게 있고 최소 거리같은걸 찾으라는 키워드는 보통 BFS라거나, 이런 느낌이 있는데
이건 멍하니 보기만 했다
과제로 인한 일주일 밤샘의 여파인지 몰라도, 머리가 노동을 거부하는 듯 생각을 안하려고 하더라
아직 갈 길이 멀다
| 백준 14465 : 소가 길을 건너간 이유 5 (0) | 2021.04.13 |
|---|---|
| 백준 14468 : 소가 길을 건너간 이유 2 (0) | 2021.04.13 |
| 백준 10451 : 순열 사이클 (0) | 2021.03.30 |
| 백준 15683 : 감시 (0) | 2021.03.26 |
| 백준 1992 : 쿼드트리 (0) | 2021.03.26 |
10451번: 순열 사이클
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3
www.acmicpc.net
감이 다 떨어졌다는 의미, 출력을 두번 해서 틀린건데 내 접근이 틀린줄 알고 시간을 더 허비했다
민망하기 짝이 없다
| 백준 14468 : 소가 길을 건너간 이유 2 (0) | 2021.04.13 |
|---|---|
| 백준 2110 : 공유기 설치 (0) | 2021.04.13 |
| 백준 15683 : 감시 (0) | 2021.03.26 |
| 백준 1992 : 쿼드트리 (0) | 2021.03.26 |
| 백준 16234 : 인구 이동 (0) | 2021.03.26 |
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
민망한 코드에 변명을 하자면
시간을 재고 풀었다
| 백준 2110 : 공유기 설치 (0) | 2021.04.13 |
|---|---|
| 백준 10451 : 순열 사이클 (0) | 2021.03.30 |
| 백준 1992 : 쿼드트리 (0) | 2021.03.26 |
| 백준 16234 : 인구 이동 (0) | 2021.03.26 |
| 백준 17144 : 미세먼지 안녕! (0) | 2021.03.23 |
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
쿼드트리 문제
Direct X 공부하면서 본 절두체 컬링에 쿼드트리가 사용되었던 적이 있다
쿼드트리는 Trie 자료구조의 차원을 2차원으로 넓힌 자료구조라고 볼 수 있다
Trie가 3차원이면 옥트리라고 한다
| 백준 10451 : 순열 사이클 (0) | 2021.03.30 |
|---|---|
| 백준 15683 : 감시 (0) | 2021.03.26 |
| 백준 16234 : 인구 이동 (0) | 2021.03.26 |
| 백준 17144 : 미세먼지 안녕! (0) | 2021.03.23 |
| 백준 14391 : 종이 조각 (0) | 2021.03.19 |
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제 설명이 좀 이상하다
덕분에 몇시간을 낭비했는지 모르겠다
www.acmicpc.net/board/view/64414
글 읽기 - 문제 지문 일부 수정 요청
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
기존 인구 이동이 몇 번 일어났느냐에 대한 질문에는 인구 이동이 일어날 때마다 카운트를 세는 것이 더 답안에 가깝다고 생각합니다. 다만 이 문제에서 요구하는 것은 땅 전체를 한 번 탐색할 동안 일어난 인구 이동들을 한 번으로 카운트 하는 것입니다.
따라서 며칠 동안 인구 이동이 발생하는지 묻는 것으로 변경하는 것이 더 직관적인 것 같습니다.
그리고 띄어쓰기가 안 되어 있던 부분을 추가로 수정했습니다.
www.acmicpc.net/board/view/50238
글 읽기 - 마지막 예제가 왜 3회 이동인가요?
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
풀기 전에 반드시 참고하는게 좋을 것
ㅡㅡ;
| 백준 15683 : 감시 (0) | 2021.03.26 |
|---|---|
| 백준 1992 : 쿼드트리 (0) | 2021.03.26 |
| 백준 17144 : 미세먼지 안녕! (0) | 2021.03.23 |
| 백준 14391 : 종이 조각 (0) | 2021.03.19 |
| 백준 6443 : 애너그램 (0) | 2021.03.19 |
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
컨디션이 좋지 않을 때 풀었다
그래도 풀었다는 것에 의의를;;
| 백준 1992 : 쿼드트리 (0) | 2021.03.26 |
|---|---|
| 백준 16234 : 인구 이동 (0) | 2021.03.26 |
| 백준 14391 : 종이 조각 (0) | 2021.03.19 |
| 백준 6443 : 애너그램 (0) | 2021.03.19 |
| 백준 15686 : 치킨 배달 (0) | 2021.03.18 |
| 백준 16234 : 인구 이동 (0) | 2021.03.26 |
|---|---|
| 백준 17144 : 미세먼지 안녕! (0) | 2021.03.23 |
| 백준 6443 : 애너그램 (0) | 2021.03.19 |
| 백준 15686 : 치킨 배달 (0) | 2021.03.18 |
| 백준 14620 : 꽃길 (0) | 2021.03.17 |