본문 바로가기

Algorithm/BAEKJOON145

[백준/C++] Tree (No. 13244) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리의 특징을 잘 알고있으면 쉽게 풀 수 있는 문제다. 먼저 트리의 특징은 사이클이 없고, 한 노드에서 경로를 따라 다른 모든 노드에 방문할 수 있어야한다는 점이 있다. 그러므로 이러한 조건을 만족하는 경우를 찾아 tree인지 graph인지 출력하면 되는 문제다. 먼저 트리의 특징을 이용하면 쉽게 N과 M의 수를 이용해 트리인지 그래프인지 판단할 수 있다.트리는 노드의 개수가 N일 때 경로(간선)의 개수가 N-1이라는 특징이 있다. 만약 경로가 N-1보다 크다면, 사이클이 무조건 존재하게 된다.경로가 N-1.. 2024. 10. 28.

[백준/C++] 규칙적인 보스돌이 (No. 29792) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N, M, K가 작고 max값을 이용하면 쉽게 풀 수 있는 문제다. 먼저 각 캐릭터가 15분동안 사냥을 할 수 있기 때문에 N개의 캐릭터가 15분 동안 보스를 잡아 얻을 수 있는 메소의 최대값을 구하면 된다.이후 캐릭터를 M개 선택할 수 있으므로 정렬해서 메소를 얻을 수 있는 캐릭터를 M개 선택하면 된다. 이때, 보스를 잡아서 얻을 수 있는 메소를 나타내는 방법은 다음과 같다. 먼저 i번째 보스를 잡을 때 타임이 T만큼 걸린다고 가정하고 얻을 수 있는 메소가 D라고 하자.이후 현재 시간이 S라면 V[S] +.. 2024. 10. 24.

[백준/C++] Fly me to the Alpha Centauri (No. 1011) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 잘 생각하면 쉽게 풀이방법을 생각할 수 있다. 이동거리가 1 증가, 그대로, 1 감소 3가지 경우 중 하나기 때문에 최대한 빠르게 이동하려면1, 2, 3, 4, ... n-1, n, n, n-1, ... 3, 2, 1 와 같은 방법으로 이동하는 게 가장 빠르다. 이를 이용해 (1~n, n~1)의 이동거리가 y와 x 의 거리의 차이보다 작거나 같으면서 가장 큰 n을 찾으면 된다. 예를 들어 만약 y와 x의 거리 차이가 7이라고 가정해보자. 그러면 위 조건을 만족하는 n은 2가 된다. 이후 현재 이동거리가 1,.. 2024. 10. 22.

[백준/C++] 전화번호 수수께끼 (No.14369, 14370) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 완전탐색을 해야하나? 생각이 들었다.그런데 0~9 를 영어로 표현하면 0은 'Z' 처럼 한번만 나와서 빠르게 0의 개수를 파악할 수 있다는 생각에 각 수를 영어로 표현하기 시작했다. 처음에는 Z나 8의 G처럼 구분되는 수만 빼려고 했는데, 잘 생각해보니 0을 빼면 Z, E, R, O 각 글자가 하나씩 빠지면서 문자의 개수로 특정 수가 몇 개 인지 파악이 되겠다는 생각이 들었다. 그렇게 알파벳의 개수로 숫자가 몇 개 인지 파악할 수 있는 경우를 구해나갔고 알파벳의 개수를 잘 세면 매우 빠르게 문제를 풀 수 있음을.. 2024. 10. 21.

[백준/C++] 마법천자문 (No. 23325) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 경우에 대해 계산을 하게되면 매우 많은 경우가 발생하므로 다른 방법으로 풀어야 한다. 이때, 잘 생각해보면 우리가 원하는 값은 최대 값이므로 특정부분까지 계산하는 방법이 매우 다양해도 최대값만 고려하고 다른 방법은 고려하지 않아도 된다는 것을 알 수 있다. 그러므로 이를 이용해 DP로 해결했다. 푸는 방법은 간단하다. DP[i] = i번까지 계산한 방법 중 최대값 으로 정의한다. 그러면 DP[i] 뒤에 이어지는 연산을 생각해보면 i+1은 무조건 연산자가 된다. 그리고 i+2는 무조건 숫자기 때문에 아래.. 2024. 10. 18.

[백준/C++] 빠른 무작위 숫자 탐색 (No. 25688) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 예전에 풀었던 실버 문제 중 이와 비슷한 문제가 있어서 쉽게 풀 수 있었다. 푸는 방법은 어떤 순서로 가야 가장 빠르게 방문할 수 있는지 브루트 포스로 탐색을 해야하는 문제다.단지, 예전에 풀었던 문제랑 다른 점은 A에서 B로 가는 경우를 BFS로 갈 수 있는지 탐색해야 한다는 점이었다. 1~6번 수 들을 방문하는 경우의 수 즉, 6!의 경우를 계산하도록 구현하면 된다. 이때, 1~6번 숫자를 방문했는지 체크하기 위해 bit연산을 사용했다.(visited 배열로 체크해도 상관없다) 이제 실제로 어떤 방법으로 구현했는지.. 2024. 10. 17.

[백준/C++] 가운데에서 만나기 (No. 21940) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 어떤 답을 원하는지 정확히 알기 힘들었다... 일단 왕복시간이 a도시에서 b도시를 방문하고 a도시로 돌아오는 경우로만 정의되어있어 아무 값이나 사용하면 되는지, 최솟값을 사용해야하는지 명확하지 않았다. 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다. 라는 지문이 있는데 이 의미가 먼저 친구들이 i도시를 왕복하는 시간들을 각각 구한다.그 다음 그 왕복 시간 중 최대값을 구한다.이제 1~N번 도시까지 구한 최대값을 비교하고 그 중 최솟값을 찾아 최솟값인 도시의 번호를 출력한다... 2024. 10. 12.

[백준/C++] 벼락치기 (No. 14728) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 기준만 잘 잡으면 풀 수 있다. 공부할 수 있는 최대 시간이 10000이므로 아래와 같은 배열을 하나 만든다. 이 배열은 T시간동안 공부했을 경우 얻을 수 있는 점수의 최대값을 저장하는 배열이다.그리고 전부 -1로 초기화를 한 다음 시간이 0 인 경우만 0으로 초기화한다.여기서 DP[T] = -1일 경우는 현재 T시간을 공부하는 방법이 없다는 뜻이다. 그 후 입력을 받아 n개의 공부의 값을 이용해 위 배열을 채워나가면 된다.(이때, 과목에 대한 시간 = E, 성과 = V라고 하자) 10,000 부터 0 .. 2024. 10. 9.

[백준/C++] 직각삼각형 (No. 1711) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀 때, 처음에 잘못 생각해서 단순 반복으로 구하면 되는 문제인 줄 알았다.실제로도 풀려서 잘 풀렸구나 싶었는데, 막상 다른 사람들의 풀이를 보니 시간이 적게 걸려서 구경했다. 다시보니 내 풀이가 약 561,375,500의 경우를 계산하는 풀이였었다는 걸 그 때 알았다;;약 1500C2의 경우로 해결된다고 착각했었다.. 다른 사람들의 풀이를 보니 시간을 조금 더 줄일 수 있는 풀이는 내적과 비율을 이용하는 방법이 있었다. 내적한 값이 0이 되려면 a벡터의x * b벡터의x = -a벡터의y * b벡터의y 이 성.. 2024. 10. 8.

[백준/C++] 계란으로 계란치기 (No. 16987) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 가장 효율적인 방법이 있을까? 고민했지만 방법이 떠오르지 않았다.그래서 완전 탐색으로 모든 경우를 고려해 계란을 깨는 방법을 선택했다. 이러한 방법이 가능한 이유는 N이 8로 작기 때문에 8^8 = 2^24로 충분히 빠르게 해결이 가능하기 때문이다. 1번 계란부터 차례대로 다른 계란을 치는데 만약 깨져있다면 넘어가도록 코드를 구현했다. 이 과정에서 내구도와 무게가 저장된 vector가 계속 복사되지 않도록 Call by Reference를 이용했다. i번 계란으로 j번 계란을 칠 수 있다면 i.. 2024. 10. 1.

[백준/C++] MEX (No. 23820) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 많은 고민을 했다. 잘 생각해보면 조건에서 200만까지만 범위가 정해져있으므로, 정말 최악의 경우 200만 보다 크면서 가장 작은 소수의 범위를 벗어나지 않겠다는 생각이 들었다. 그리고 a_i *a_j로 S집합의 수를 나타낼 수 있으므로, a_i * a_j의 계산 값이 200만 보다 크면서 가장 작은 소수의 범위 k보다 작을 때 까지만 체크를 하면 되겠다는 생각이 들었다. (잘 생각해보면 이때의 시간 복잡도는 약 2,000,000/a_i 를 전부 더한 값이므로 적분하면 시간복잡도가 약 nLo.. 2024. 9. 28.

[백준/C++] 동작 그만. 밑장 빼기냐? (No.20159) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 밑장을 뺄 경우 어떻게 수가 분배 되는지를 파악하면 누적합을 이용해 쉽게 풀 수 있는 문제다. 그림을 통해 한번 알아보자 B카드를 받아야 하는 상태에서 밑장을 빼면, A카드를 받고 그 뒤에 z, b, c, d ...카드를 받게 된다.즉, 내가 카드를 받을 순서에서 밑장을 빼면 그때부터 나는 원래 받을 카드가 아니라, 상대방의 카드를 전부 받게 된다. 이를 이용하면 내가 받을 i번째 카드의 밑장을 빼면 내가 원래 받을 i-1번째 카드까지의 합 + 상대방이 받을 i번째 카드부터 N/2번째 카드까지의 합으로 나.. 2024. 9. 25.

[백준/C++] 단어 수학 (No.1339) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 단순 대입을 이용해 재귀로 풀었다.그랬더니 단순히 반복문이 10^10이라 시간초과가 걸렸다;; 다음으로 생각한 방법은 어차피 수가 최대 10개나오므로 가장 앞자리에 많이 나온 자리수를 이용해 정렬하면 풀 수 있겠다는 생각이 들었다. 즉, A라는 문자가 10의 자리에만 2번 나오고 B의 문자가 10의 자리에만 1번 나온다면 당연히 A>B로 수를 대입하는게 더 큰 수를 만들 수 있다는 아이디어다. 문제는 수의 개수가 10개라는데서 반례가 발생했다. 만약 A라는 문자가 10의 자리에 2번 나.. 2024. 9. 24.

[백준/C++] 더워! (No. 32360) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가장 빠르게 집에서 약속장소를 도착하는 시간을 찾는 문제므로 BFS로 풀 수 있다. 단지, 일반적인 BFS와 다른 점은 불쾌감 지수가 있어서 불쾌감 지수가 100이상이 되면 더 이상 이동할 수 없는 상태가 된다.그러므로 불쾌감 지수가 100이 되지 않으면서 약속장소에 도달할 수 있도록 불쾌감을 조절하며 가장 빠르게 약속장소에 도착하는 시간을 찾으면 된다. 이제 불쾌감 지수를 고려해 BFS로 문제를 푸는 방법을 생각해보자. 현재 위치의 불쾌감 지수를 B, 시간을 T라고 하고, 앞으로 이동할 위치에 방문한.. 2024. 9. 23.

[백준/C++] 합성함수와 쿼리 (No.17435) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 빠르게 해결하기 위해 Cycle이 생기는 순간을 기록해야하나? 의문이 들었다.그런데 아무리 생각해도 Cycle을 판단하는데 시간이 오래 걸릴 것으로 보여 다른 방법을 고민했다. 중간에 다른 사람의 힌트를 보니 DP를 이용해 문제를 푼 것을 보고 해결을 할 수 있었다. 함수를 2^k번 적용한 값을 저장하는 DP를 만들면, DP배열을 이용해 빠르게 계산을 할 수 있다. 함수를 2^k번 적용한 DP배열을 만드는 방법도 간단하다. x라는 수를 2^k번 적용해 x1이라는 수가 나오면, x1을 다시 2.. 2024. 9. 4.

이전 1 2 3 4 5 ··· 10 다음

티스토리툴바