티스토리

정신 차리고 살자

검색하기

블로그 홈

정신 차리고 살자

9x211x2.tistory.com/m

yegyeom 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[BOJ] 16398번 행성 연결 (C++) 링크 (https://www.acmicpc.net/problem/16398) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 무난한 최소 스패닝 트리 문제이다. MST 문제를 항상 크루스칼 알고리즘으로만 풀었는데 이번엔 프림 알고리즘으로 풀어봤다! 정답이 int 범위보다 클 수 있으므로 long long으로 해주어야 한다. [소스코드] 더보기 2022-03-02 Gold 4 - 그래프 이론 - 최소 스패닝 트리 공감수 0 댓글수 0 2022. 3. 3.
[BOJ] 14621번 나만 안되는 연애 (C++) 문제 (https://www.acmicpc.net/problem/14621) 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다. 특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다. 남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다. 만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(B.. 공감수 0 댓글수 0 2022. 3. 3.
[BOJ] 1253번 좋다 (C++) 문제 (https://www.acmicpc.net/problem/1253) 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 처음엔 검사하는 숫자보다 작은 수들로만 검사하는 숫자가 만들어진다고 생각했다. 하지만 음수도 가능하기 때문에 -4 -2 -2 같은 케이스가 존재한다. (-4가 좋은 수) 또한 자기 자신은 서로 다른 두 수에 해당하면 안 되므로 예외 처리를 해주어야 한다. 나는 그냥 for문을 돌 때마다 원본 벡터를 복사한 벡터에 해당 숫자를 erase로 제거하여 사용했다. - n이 2보다 작거나 같으면 다른 수 두 개의 합으로 나타.. 공감수 0 댓글수 0 2022. 1. 19.
[BOJ] 3078번 좋은 친구 (C++) 문제 (https://www.acmicpc.net/problem/3078) 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우로 해결한 문제!!! 문제 설명이 엄청 길지만,, 요약하자면 좋은 친구의 정의는 아래와 같고 좋은 친구가 몇 쌍 있는지 출력하면 된다. 좋은친구: 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 pair (등수, 이름의 길이) 형태로 입력을 받았다. i번째(i등) 학생은 크기가 k인 창문 내의 다른 학생들 중, 이름의 길이가 같은 학생과 좋.. 공감수 0 댓글수 0 2022. 1. 19.
[BOJ] 2096번 내려가기 (C++) 문제 (https://www.acmicpc.net/problem/2096) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net DP + 슬라이딩 윈도우로 해결한 문제이다. 두 알고리즘 모두 취약해서...ㅎㅎ 다른 코드를 참고하여 풀었다. 크기가 3인 배열들 minArr, maxArr, minTmp, maxTmp을 사용했는데, minTmp, maxTmp는 현재 행 이전까지의 결과를 저장해둔 배열이다. - 첫 번째 행의 값들은 최솟값이자 최댓값이므로 4개의 배열에 모두 삽입해준다. - 첫 번째 행이 아닐 경우에는 minTmp, m.. 공감수 0 댓글수 0 2022. 1. 19.
[BOJ] 2211번 네트워크 복구 (C++) 문제 (https://www.acmicpc.net/problem/2211) 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다. 11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다. route[a] = b는 "a번에 최소로 도.. 공감수 0 댓글수 0 2022. 1. 17.
[BOJ] 13549번 숨바꼭질 3 (C++) 문제 (https://www.acmicpc.net/problem/13549) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작년에 BFS로 풀었던 1697 숨바꼭질과 비슷한 문제이다. 다익스트라 알고리즘 스터디 주간에 고른 문제여서 다익스트라로 해결해보려 했지만,, 문제를 읽고 생각을 해봐도 1697번 문제처럼 BFS로 해결하는 방법밖에 떠오르지 않았다...! 그래서 일단 BFS로 해결 완! (코드 첨부) BFS로 해결할 경우 방문 순서에 따라 정답이 되기도 하고 아니기도 한.. 공감수 0 댓글수 0 2022. 1. 17.
[BOJ] 1238번 파티 (C++) 문제 (https://www.acmicpc.net/problem/1238) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다. N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다. Dijkstra Algorithm: '한 정점'에서 '모든 정점'으로의 최단경로 인접 리스.. 공감수 0 댓글수 0 2022. 1. 17.
[BOJ] 2887번 행성 터널 (C++) 문제 (https://www.acmicpc.net/problem/2887) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 입력으로 행성들의 좌표가 들어온다. 이 좌표들로 모든 행성 사이의 거리와 연결 비용을 구한다면 시간 초과가 발생한다. (N ≤ 100,000) 따라서, 행성들의 x, y, z 좌표를 각각 정렬한 후 반복문을 돌며 각 좌표에서 인접한 행성들 간의 비용을 구한다. 예제와 같이 N이 5라면 총 12개의 간선 정보가 생성된다. N이 6이라면 15개이다. 즉 (N-.. 공감수 0 댓글수 0 2022. 1. 5.
[BOJ] 1939번 중량제한 (C++) 문제 (https://www.acmicpc.net/problem/1939) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이번 스터디 주제인 이분탐색으로 해결하려고 했으나 도저히 모르겠어서 크루스칼로 해결했다 🤯 중량의 최댓값을 구해야 하는 문제이므로 입력을 받은 후 간선의 크기를 기준으로 내림차순 정렬했다. 노드들을 합쳐가면서 매번 마지막 입력으로 들어온 두 섬이 연결되었는지 확인해야 한다. 연결이 되었다면, 연결된 모든 노드들 간의 간선들 중 가.. 공감수 0 댓글수 0 2022. 1. 5.
[BOJ] 3020번 개똥벌레 (C++) 문제 (https://www.acmicpc.net/problem/3020) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제를 읽고 고민을 하다가.. 예전에 푼 문제에서 lower_bound와 upper_bound를 사용했던 게 생각이 났다. 구현을 해봤지만 시간 초과가 발생했고 구글링으로 약간의 힌트를 얻은 후 구현했다. 석순과 종유석을 각각 입력받고 정렬한다. 정렬 후, 1부터 h까지 반복하며 각 높이일 때 몇 개의 장애물을 파괴하는지를 구한다. 이때 lower_bound를 사용하는 것이다. 장애물의 개수.. 공감수 1 댓글수 0 2022. 1. 5.
[BOJ] 4386번 별자리 만들기 (C++) 문제 (https://www.acmicpc.net/problem/4386) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다. 이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61) 위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다. [소스코드] 더보기 2021-12.. 공감수 0 댓글수 0 2022. 1. 4.
[BOJ] 11779번 최소비용 구하기 2 (C++) 문제 (https://www.acmicpc.net/problem/11779) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 출발 도시에서 도착 도시까지의 최소 비용을 구하는 일반적인 다익스트라 문제이다. 다른 문제들과 차이점은 최소 비용뿐만 아니라 경로에 포함되어있는 도시의 개수와 방문하는 도시 번호도 출력해야 한다. 따라서 배열을 생성하여 각 도시에 도달하기 위해서는 몇 번 도시에서 출발해야 하는지를 기록했다. 예를 들어, route[a] = b는 "a번에 최소로 도달하기 위.. 공감수 0 댓글수 0 2022. 1. 4.
[BOJ] 1484번 다이어트 (C++) 문제 (https://www.acmicpc.net/problem/1484) 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net (현재 몸무게)^2 - (예전 몸무게)^2 = 찐 몸무게 1부터 g까지의 모든 수를 배열에 담아두고 투 포인터를 실행했다. end는 현재 몸무게를 가리키는 포인터이고 start는 예전 몸무게를 가리키는 포인터로 설정했다. 위 식대로 찐 몸무게를 구한 후 구한 값이 g와 같다면 정답을 담아두는 배열에 삽입한다. g보다 작다면? 찐 몸무게를 더 늘려야 하므로 end(현재 몸무게)를 증가 g보다 크거나 같다.. 공감수 0 댓글수 0 2022. 1. 3.
[BOJ] 1644번 소수의 연속합 (C++) 문제 (https://www.acmicpc.net/problem/1644) 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 2 이상 N 이하의 모든 소수를 벡터에 삽입한다. 2. start부터 end까지의 합에 따라 1번에서 구한 벡터 위에서 start와 end를 움직인다. 2-1. 합이 n보다 작다면? end 증가 2-2. 합이 n보다 크거나 같다면? start 증가 2-3. 합이 n과 같다면? ans 증가 [소스코드] 더보기 2021-12-28 Gold 3 - 수학 - 정수론 - 두 포인터 - 소수 판정 - 에라토스테네스의 체 공감수 0 댓글수 0 2022. 1. 3.
[BOJ] 2470번 두 용액 (C++) 문제 (https://www.acmicpc.net/problem/2470) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터 알고리즘을 사용하여 해결한 문제이다. start를 맨 앞, end를 맨 뒤에 두고 움직이기 시작한다. start와 end가 가리키는 값을 더하여 최솟값인지 절댓값을 취해 비교한다. 더한 값이 0보다 작다면? 숫자를 크게 하여 0에 가까워져야 하므로 start 증가 더한 값이 0보다 크거나 같다면? 숫자를 작게 하여 0에 가까워져야 하므로 end.. 공감수 0 댓글수 0 2022. 1. 3.
[BOJ] 3107번 IPv6 (C++) 문제 (https://www.acmicpc.net/problem/3107) 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 출력은 무조건 4 글자씩 8번 출력되어야 하고, 콜론은 7개여야 한다. 1. 입력받은 문자열을 ':' 기준으로 분리시킨다. 2. 분리된 문자열을 담고 있는 벡터의 크기가 8보다 작다면 2번 규칙이 적용된 것이다. 따라서 2번 규칙이 적용된 곳에 문자열 "0000"을 부족한 만큼 삽입한다. 3. 2번에서 완성한 벡터의 문자열 중 0이 생략된 문자열에 0을 채워준다. [소스코드] 더보기 2021-12-28 Gold 5 - 구현 -.. 공감수 0 댓글수 0 2022. 1. 3.
[BOJ] 1990번 소수인팰린드롬 (C++) 문제 (https://www.acmicpc.net/problem/1990) 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 소수&팰린드롬을 푼 직후에 풀어서 처음엔 쉽다고 생각했는데.. 계속 시간 초과가 발생했다. 1부터 1억까지의 숫자들 중 소수이면서 팰린드롬인 숫자를 모두 출력해보았더니 최댓값이 10,000,000을 넘지 않았다! (캡처를 못해두었는데 대략 9천7백만 정도?) 따라서 반복문의 최댓값을 10,000,000으로 설정하고 숫자의 범위가 b를 넘어가면 반복문을 탈출했다. [소스코드] .. 공감수 2 댓글수 0 2021. 12. 27.
[BOJ] 1747번 소수&팰린드롬 (C++) 문제 (https://www.acmicpc.net/problem/1747) 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 문제이다. N부터 반복문을 돌며 소수와 팰린드롬을 둘 다 만족하는지 확인한다. 만족하는 숫자를 발견하면 바로 반복문을 탈출한다. 이 문제에서 했던 실수,, 처음엔 N의 최댓값이 1,000,000인걸 정답의 최댓값이 1,000,000인 줄 알고 for문의 두 번째 인자를 i 공감수 0 댓글수 0 2021. 12. 27.
[BOJ] 1043번 거짓말 (C++) 문제 (https://www.acmicpc.net/problem/1043) 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온파인드로 해결한 문제이다. 1. 각 파티에 오는 사람들끼리 연결시킨다. (unionParent) 2. 전체 파티의 인원수만큼 반복문을 돌며 처음 입력받았던 진실을 아는 사람과 연결되었는지 확인한다. (findParent) 2-1. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재한다면? 그 파티에서는 거짓말을 할 수 없으므로 반복문 탈출 2-2. 해당 파티에 진실을 아는 사람과 연결된 사람이.. 공감수 0 댓글수 0 2021. 12. 27.
[BOJ] 15927번 회문은 회문아니야!! (C++) 문제 (https://www.acmicpc.net/problem/15927) 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분 문자열의 길이를 구하는 문제. 예제를 보면 바로 파악이 가능한데, 케이스를 3가지로 나눌 수 있다. 1. 팰린드롬 O / 문자열의 모든 문자가 같은 문자인 경우 => -1 2. 팰린드롬 O / 문자열의 모든 문자가 같지 않은 경우 => 문자열의 길이 - 1 3. 팰린드롬 X .. 공감수 0 댓글수 0 2021. 12. 27.
[BOJ] 7490번 0 만들기 (C++) 문제 (https://www.acmicpc.net/problem/7490) 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 풀고 검색해보니까 대부분 백트래킹으로 풀던데 나는 백트래킹으로 풀 생각은 못했다ㅠㅠ 다음에 백트래킹으로도 풀어봐야지...! 자연수 N이 주어질 때, 연산자 개수는 N-1개이다. 각 연산자 자리에 들어갈 수 있는 것은 +, -, ' ' 총 3개이다. 중복 순열을 만들어서 각 순열이 만들어질때마다 수식을 검사한다. 공백이 있다면 이어붙이고 만들어진 수식을 계산했다. 계산된 수식의 값이 0이라면 해당 수식 문자열을 vector에 담아두었고, 아스.. 공감수 0 댓글수 0 2021. 12. 21.
[BOJ] 17070번 파이프 옮기기 1 (C++) 문제 (https://www.acmicpc.net/problem/17070) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 가능한 이동 방법은 아래와 같다. 1. 파이프가 가로 방향일 때 - 오른쪽 방향 - 오른쪽 아래 대각선 방향 2. 파이프가 세로 방향일 때 - 아래 방향 - 오른쪽 아래 대각선 방향 3. 파이프가 대각선 방향일 때 - 오른쪽 방향 - 아래 방향 - 오른쪽 아래 대각선 방향 파이프의 오른쪽 끝 위치(x, y), 현재 파이프의 방향(가로/세로/대각선)(dir)과 함께.. 공감수 0 댓글수 0 2021. 12. 21.
[BOJ] 1477번 휴게소 세우기 (C++) 문제 (https://www.acmicpc.net/problem/1477) 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분 탐색 문제이다. vector에 휴게소의 시작점과 끝점(0, l), 입력받은 위치들을 넣어주고 정렬한다. 1 ≤ 휴게소의 위치 ≤ l - 1이므로 start = 1, end = l - 1로 설정했다. 휴게소 사이의 거리인 mid를 구하고 기존 휴게소 사이에 몇 개의 휴게소를 설치할 수 있는지 계산한다. 이때, dist % mid 값이 0이라면 휴게소 위치가 겹치는 것이므로 개수를 하나 빼야 함! 예를 들어,.. 공감수 0 댓글수 0 2021. 12. 21.
[BOJ] 2776번 암기왕 (C++) 문제 (https://www.acmicpc.net/problem/2776) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 10816번 (숫자 카드 2) 문제와 매우 비슷한 문제이다! 이 문제도 upper_bound, lower_bound를 사용하여 해결했다. upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 [소스코드] 더보기 2021-12-19 Silver 4 - 자료 구조 - 정렬 - 이분 탐색 - 해시를 사용한 .. 공감수 0 댓글수 0 2021. 12. 20.
[BOJ] 2343번 기타 레슨 (C++) 문제 (https://www.acmicpc.net/problem/2343) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 실수했던 점! - ans 초기화할 때 값은 10,000이 아닌 1,000,000,000으로 해야 함 - 블루레이의 개수가 꼭 M일 필요 없음 - cnt 초기화를 1로 해두면 편하다... 많이.... - M 모든 강의가 들어가지 않는 것이므로 mid 값이 커지도록 한다 [소스코드] 더보기 2021-12-19 Silver 1 - 이분 탐색 - 매개 변수 탐색 공감수 0 댓글수 0 2021. 12. 20.
[BOJ] 10816번 숫자 카드 2 (C++) 문제 (https://www.acmicpc.net/problem/10816) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net upper_bound()와 lower_bound를 사용하여 푼 문제! 기억하기~~~ upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 upper_bound 리턴 값 - lower_bound 리턴 값 0: value 값이 존재하지 않는 것 양수: value 값의.. 공감수 0 댓글수 0 2021. 12. 19.
[BOJ] 1654번 랜선 자르기 (C++) 문제 (https://www.acmicpc.net/problem/1654) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 전에 올린 나무 자르기와 비슷한 듯 다른 문제..! 나는 end 값을 입력받은 길이 중 가장 큰 값이 아닌 모든 길이의 합을 n으로 나눈 값으로 정했다. 각 길이를 mid로 나누었을 때 몫의 합이 n보다 - 크거나 같다면? 랜선의 길이를 더 길게 start 이동, 최댓값이라면 답으로 설정 - 작다면? 랜선의 길이를 더 짧게 end 이동 [소스코드] 더보기 20.. 공감수 1 댓글수 0 2021. 12. 19.
[BOJ] 2805번 나무 자르기 (C++) 문제 (https://www.acmicpc.net/problem/2805) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색하는 값 (mid): 절단기의 높이 절단기의 높이가 mid일 때, 나무를 자르고 남은 길이들의 총합이 m 이상이면? - 더 큰 mid 값으로 m 이상을 구할 수도 있으므로 start를 mid + 1로 지정한다. [소스코드] 더보기 2021-05-25 Silver 3 - 이분 탐색 - 매개 변수 탐색 공감수 0 댓글수 0 2021. 12. 19.
[BOJ] 2521번 예산 (C++) 문제 (https://www.acmicpc.net/problem/2512) 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색하는 값 (mid): 예산 저번에 푼 1920번 문제는 배열의 인덱스를 이분 탐색으로 찾아냈다면 이 문제는 인덱스가 아니라 값들을 이분 탐색으로 찾아야 한다. 예산 요청의 총합이 m보다 크다면 이분 탐색을 진행한다. 이분 탐색을 진행할 때마다 sum을 구해야 하는데, 요청 금액이 mid 값보다 크다면 mid 값으로 더해주어야 한다. 배정된 예산들 중 최댓값인 정수를 출력해주.. 공감수 0 댓글수 0 2021. 12. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.