Baekjoon

[백준]1052번 - 물병 C++

문제 설명 그리드 알고리즘 문제 문제 풀이 저는 이 문제를 보고 바로 2048게임이 생각났습니다ㅋㅋ 이 문제의 규칙은 다음과 같습니다. 2의 거듭제곱마다 하나의 물병으로 만들 수 있습니다. 합쳐지지 못한 물병을 세어가며 들고가야하는 물병의 개수가 K보다 작아질 시점을 구하면 됩니다. 문제 입력 예시인 13 2 로 예시를 들어보겠습니다. 우리는 i값을 구하면 됩니다. 코드 #include int main() { int N, K; int i = 0; std::cin >> N >> K; while (1) { int tmp = N; //N을 0이 될 때까지 나누므로 새로 갱신해야 합니다. int result = 0; //들고가야 할 물병 while (tmp > 0) { if (tmp % 2 == 1) //들고가..

1697번 - 숨바꼭질 C++

문제 설명 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS와 dijkstra 알고리즘을 섞어 사용했습니다. 문제 예시로 나와있듯이 수빈이가 -1, +1, *2 칸을 이동해서 동생을 잡는 건데요. 5에서 17을 잡을 때 5 -> 4 -> 8 -> 16 -> 17 처럼 최소 시간으로 잡아야합니다. 그러기 위해선 최단 경로 알고리즘인 다익스트라 알고리즘을 이용합니다. 다익스트라 알고리즘이란? https://yhoon..

2178번 - 미로 탐색 C++

문제 설명 대표적인 BFS 문제 https://www.acmicpc.net/problem/2178 Tip 본 문제에서는 그래프 입력이 101111 101010 101011 111011 이런식으로 붙어있어서 하나씩 떼어줘야 합니다. 문자열로 받아 한글자씩 떼는 방법도 있지만 매우 간단한 방법이 존재합니다. scanf("%1d", &maze[i][j]) 보통 C언어에서 입력값을 받을 때 사용하는 std::scanf 함수를 이용하는 것 입니다. 1d라는 것은 붙어있는 여러 개의 숫자를 한 글자씩 떼어 입력합니다. (2d라면 두 개씩 끊어 입력합니다.) BFS란? https://yhoons.tistory.com/9 BFS(너비 우선 탐색) 알고리즘 BFS(Breadth-First Search)란? 그래프 순회 ..

19532번 - 수학은 비대면강의입니다 C++

문제 설명 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net [브루트 포스 문제] 각각 -999 이상이고 999이하인 (x, y)을 찾는 문제 입니다. 모든 경우의 수는 2000 * 2000이라 O($n^2$)인 완전탐색으로 풀어도 되지만 더 깔끔하고 효율적인 방법이 존재합니다. 연립 방정식을 풀 때 서로 다른 방정식의 계수를 맞추어 x 또..

10816 - 숫자 카드2 c++

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 알고리즘 분류 : 해시를 사용한 집합과 맵 시간복잡도: O(n+m) 이하 난이도: silver 4 해시 맵이 궁금하시다면 다음 글을 참고해주세요. https://yhoons.tistory.com/32\ hash map - C++ STL 예시 #include #include int main() { std::unordered_map hashmap; //inser..

2003번 - 수들의 합 2

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 알고리즘의 기본적인 문제라고 할 수 있다. 어떻게 보면 이중 반복문을 사용하여 쉽게 풀 수도 있지만 이는 시간 초과가 날 확률이 높으므로 우린 투 포인터 알고리즘 개념을 사용할 것이다. 투 포인터 알고리즘 개념이 익숙치 않다면- https://yhoons.tistory.com/6 투포인터 알고리즘(Two Pointers Algorithm) - c..

1504번 - 특정한 최단 경로

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 알고리즘 분류 이 문제는 Dijkstra 알고리즘을 이용하는 문제이다. 다익스트라 개념을 아시는 분들이라면 충분히 활용하여 푸실 수 있을 것 이다. 다익스트라 개념 바로가기 -> https://yhoons.tistory.com/4 다익스트라 알고리즘(Dijkstra algorithm) - c++ 다익스트라 알고리즘이란? 더보기 : 그래프에서 엣지(..

2193번- 이친수

https://www.acmicpc.net/problem/2193 DP알고리즘 문제 같은 경우, 어떤 규칙이 반복되는지만 파악한다면 어렵지않게 문제를 해결해나갈 수 있다. 쓴이는 테스트케이스 1부터 어떤 경우가 나오는지 써가며 푸는 편이다. N=1 -> 이친수: {1} N=2 -> 이친수: {10} N=3 -> 이친수: {100}, {101} N=4 -> 이친수: {1000}, {1001}, {1010} N=5 -> 이친수: {10000}, {10001}, {10010}, {10100}, {10101} N=6 -> 이친수: {100000}, {100001}, {100010}, {100100}, {100101}, {101000}, {101001}, {101010} . . . 테스트 케이스를 살펴보면, 이전..