티스토리

devtravel

검색하기

블로그 홈

devtravel

hyun-jun5.tistory.com/m

The biggest risk is not taking any risk

구독자: 2

방명록 방문하기

주요 글 목록

[백준 / BOJ] C++ 11279 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이 그냥 간단하게 우선순위큐로 구현하여 풀 수 있다. 다만 시간초과가 계속나서 신경을 써야한다.. 시간제한 1초라니 C++ 개행을 endl로 해도 시간초과가 날정도로 짧다. 아래는 코드이니 참조하자. Code ( C++ ) #include #include using namespace std; int main() { ios::sync_with_stdio(false); .. 공감수 0 댓글수 0 2023. 3. 28.
[백준 / BOJ] C++ 1992 쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 풀이 이 문제는... 처음에 이해하는게 힘들었다. 풀이 하자면 문제에서 요구하는 방법은 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 즉 Z 순서로 숫자를 비교하고 탐색하는 것이다. 위 이미지 같은 경우 (01(1101)(0011)이 되는것 이다. 그렇다면, N은 항상 2의 제곱수로 주어지니, 첫번째로 영상의 모든 수가 동일한지 확인하고, 동일하지 않다면 모든 비디오 영상을 4.. 공감수 0 댓글수 0 2023. 3. 4.
[백준 / BOJ] C++ 1780 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 풀이 한변의 크기가 N인 정사각형을 입력받는다. 입력 받은 후 문제에서 제공되는 조건으로 종이를 자르거나 더해주거나 한다. 우선 전체 입력받을 종이 3^7 사이즈 2차원 배열과, 결과값을 저장할 result 배열을 선언한다. 다음 해당 종이의 행과 열의 숫자들을 비교하고, 모두 동일한 수인지 판단을 한다. 동일한 수가 아닐 경우, 입력받은 크기 N에 3을 나누어 해당 크기만큼 다시.. 공감수 0 댓글수 0 2023. 3. 4.
[백준 / BOJ] C++ 1764 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 풀이 N 만큼 입력받은 문자열들과 M만큼 입력받은 문자열들 중, 겹치는 문자열을 정렬한채로 출력하는 문제이다. 알파벳 순으로 정렬되는 기능인 sort를 사용하였고, 입력되는 문자열들은 vector에 저장하였다. 그리고 겹치는 문자열이 있는지 유무 확인은 이진탐색(binary_search)으로 하였다. 이후 겹치는 문자열들을 출력할 vector에 저장하고, 출력하였다. 특정한 알고리즘을 사용.. 공감수 0 댓글수 0 2023. 3. 4.
[백준 / BOJ] C++ 1676 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 팩토리얼 계산을 하게되면 적은숫자면 모르지만 큰수를 입력할 경우 오버플로우 오류가 생긴다. (숫자가 너무 커서) 문제를 풀어서 생각해보면, 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는것이다. 처음 0이 아닌 숫자가 나오는 경우는 10의 거듭제곱 밖에 없다. 결국 10은 2와 5로 소인수 분해를 할 수가 있다. 숫자는 2부터 입력받은 수까지 반복하며 소인수 분해한 2와 5중 더 작은 개수를 출력하면 된다. Code ( C++ ) #include using namesp.. 공감수 0 댓글수 0 2023. 2. 1.
[백준 / BOJ] C++ 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 문제에서 주어지는 조건은 3가지이다. 1. X가 3으로 나누었을때 나누어 떨어지면 3으로 나눈다. 2. X가 2로 나누었을때 나누어 떨어지면 2로 나눈다. 3. 그냥 1을 뺀다. 예시로 확인해보자. 1의 경우는 연산작업이 필요가 없기에 연산 수는 0 2의 경우는 2로 나누어떨어지기에 연산 횟수는 1 3의 경우는 3으로 나누어 떨어지기에 연산회수는 1 10의 경우에는 (10 - 1) / 3 / 3의 연산을 해야하기에 연산 횟수는 3 이를 따라, 점화식을 구해보자면 2의 경우는 dp[i] = dp[i/2.. 공감수 0 댓글수 0 2023. 1. 10.
[백준 / BOJ] C++ 2798 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 풀이 브루트포스 알고리즘의 가장 전형적인 예이다. 3장의 카드들이 입력된 M보다 작아야하며 가장 큰 수를 완전탐색하면된다. 아주 간단한 문제인 브루트포스 알고리즘 입문 문제이다. 근데 실제로 브루트포스 알고리즘은 나는 잘 안쓰게된다... Code ( C++ ) #include #include using namespace std; int N, M; int ans.. 공감수 0 댓글수 0 2022. 12. 15.
[백준 / BOJ] C++ 1107 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 풀이 브루트포스 알고리즘이다. 문제에서의 함정이있는데, 이동하고자 하는 채널 N은 0 N >> M; for (int i = 0; i > btn; remote[btn] = true; } int result = abs(100 - N); for (int i = 0; i 0) { int b = abs(N - i); if (result >.. 공감수 0 댓글수 0 2022. 12. 15.
[백준 / BOJ] C++ 1003 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 아~~ 주 쉽게 생각했다가 짜증만 엄청 냈던 문제.. 시간초과를 생각못하고 어떻게 풀던 시간초과가 나오고, 계속 '이렇게해서 안되면 어쩌란거야 ?'를 반복하다가 찾아보니 점화식을 이용하는 문제였다. 이럴거면 피보나치 위에 그 함수코드는 왜있었는지 이해불가.. 아무튼 피보나치 함수의 점화식은 아래와 같다. N이 0일때, return값이 0인경우 = 1, 1인경우 = 0 N이 1일때, return값이 0인경우 = 0, 1인경우 = 1 N이 2일때, return값이 0인경우 = 1, 1인.. 공감수 0 댓글수 0 2022. 12. 11.
[백준 / BOJ] C++ 2448 별찍기 - 11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 풀이 이것저것 해보다가 결국 끼워맞추기를 시작한 문제.. 반복되는 문양을 vector 배열에 넣어준다. 이후에는 코드에서 알 수 있듯.. 끼워맞춰서 출력만 되도록하였다. 이해를 돕기위해 아래 이미지를 참조하자. 반복되기 이전 공백이 3개씩 들어가며, 그 공백의 갯수는 2^n개로 알 수가 있다. 입력값이 3 * 2^k 이기 때문에 유추할 수 있다. 앞에 공백 " "을 채워주고 별 그린 이후 이후 공백 " "을 채워준다. 아래 코드를 참조하자. Code.. 공감수 0 댓글수 0 2022. 12. 7.
[백준 / BOJ] C++ 2407 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 풀이 조합 공식을 이용 - (nCm = n-1Cm-1 + n-1Cm)을 이용하여 값을 구한다. long long을 사용해도 자료형 허용 범위를 넘어가는 미친 문제이다. 조합 공식쓰고 그냥 했다가 왜 안되지? 하며 꽤나 헤매었던 문제... Visual studio 2022 C++ 17 개발환경으로 long long으로 빌드하거나 디버깅하면 문제없이 다 출력이 된다. 그래서 오히려 헤메었다.. python에서는 자바의 Biginteger가 백그라운드에서 자동 지원이라서 string으로 구현하지않아도 문제없이 실행이 .. 공감수 0 댓글수 0 2022. 12. 7.
[백준 / BOJ] C++ 2096 내려가기 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 문제들에 익숙해지면 조건식을 바로 알아챌 수 있다. 1. 별표 문양이 왼쪽에 있을 경우 dp[i][0] = arr[i][0] + max(dp[i - 1][0], dp[i - 1][1]); 2. 별표 문양이 중앙에 있을 경우 dp[i][1] = arr[i][1] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]); 3. 별.. 공감수 0 댓글수 0 2022. 11. 28.
[백준 / BOJ] C++ 1991 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 정말 오랜만에 보는 순회 문제이다. 사실.. 나는 전위, 중위, 후위를 구현하는 방법을 알고있어서 어렵지 않게 문제를 풀었다. 풀이할게 딱히 없고, preorder, inorder, postorder를 구현할줄 알면 어렵지 않게 푸는 문제이다. Code ( C++ ) #include #define MAX 26 using namespace std; int N; typedef stru.. 공감수 0 댓글수 0 2022. 11. 27.
[백준 / BOJ] C++ 1967 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 깊이우선탐색(DFS)를 이용한 문제이다. 백준 문제를 풀다보면 자주자주 나오는 유형의 문제이다. 그래도 이 문제는 가장 끝 노드와 그 해당 노드로 부터 가장 멀리 떨어진 노드를 찾는다는 조건이 주어지기 때문에 비교적 쉽게 문제 풀이가 가능하다. 조건의 시작점은 트리의 시작 노드에서 부터 가장 멀리 떨어진 노드이다. (DFS 탐색 첫번째) 조건의 끝점은 시작노드로 부터 가장.. 공감수 0 댓글수 0 2022. 11. 25.
[백준 / BOJ] C++ 1932 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 문제에서 주어지는 조건을 활용해보자. 아래층으로 내려올때 선택 할 수 있는 수는 윗층에서의 대각선에 위치한 수이다. 즉, 위의 이미지를 참조하여 써보겠다. node[0][0] = 7 node[1][0] = 해당 node + node[0][0], node[1][1] = 해당 node + node[0][0] node[2][0] = 해당 node + node[1][0], node[2][1] = 해당 node + max(node[1][0], node[1][1]), ..... 공감수 0 댓글수 0 2022. 11. 25.
[백준 / BOJ] C++ 1918 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 후위 표기식 문제이다. 기본적으로 후위표기식의 순서는 다음과 같다. 전체 식 중 괄호 안에 있는 연산 전체 식의 사칙연산 중에서 곱셈 또는 나눗셈이 들어간 연산 이후 더하기 빼기 연산 이후, 전역으로 선언해놓은 스택에는 연산자만 입력해준다. 입력한 문자열 ( 연산식 )의 길이만큼 한글자씩 탐색한다. 그렇다면 후위표기의 알고리즘은 아래와 같다. 알파벳인지, 연산자인지 우선 확인 여는 괄호 .. 공감수 0 댓글수 0 2022. 11. 24.
[백준 / BOJ] C++ 1753 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 문제이다. 시작노드부터 최단 경로를 찾아내며, 최단경로에 저장되어있는 가중치를 출력한다. 우선 아래 이미지는 위의 입력을 그림으로 표현하였다. 우선순위큐를 이용하여 가중치 낮은순으로 저장을 하고, 해당 노드 방문시 시작지점으로부터 가중치를 더하여 비교를 하였을 때, 작은 경우만 출력을 해주면 된다. Code ( C++ ) #include #in.. 공감수 0 댓글수 0 2022. 11. 16.
[백준 / BOJ] C++ 1629 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 간단하지만 수의 크기때문에 생각의 시간이 필요했던 문제. (A * B) % C = (A%C * B%C) %C 위처럼 생각하여 C로 나누어 주어 숫자를 줄여 풀이가 가능하다. Code ( C++ ) #include using namespace std; long long pow(long long A, long long B, long long C) { if (B == 0) return 1; if (B == 1) return A % C; long long resu.. 공감수 0 댓글수 0 2022. 11. 10.
[백준 / BOJ] 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 풀이 다익스트라 문제가 점점 익숙해지고 있다. 우선 문제를 살펴보자면, '특정 정점을 무조건 들려야한다' 라는 전제조건이 있다. 만약 정점을 2곳을 꼭 들려야 한다면 출발지점에서 해당 정점 2곳을 들리는 다익스트라 함수, 해당 정점으로부터 도착지점까지 가는 다익스트라 함수 즉 3번 탐색을 하면된다. 1. 시작점에서 입력받은 정점까지 가는 최단거리 2. .. 공감수 0 댓글수 0 2022. 11. 10.
[백준 / BOJ] C++ 1238 파티 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 풀이 다익스트라를 이용하는 문제이다. 1. 선언한 vector에 입력받은 시작위치에 끝점과 소요시간을 저장한다. 2. 시작 idx인 i 부터 X까지의 거리를 구한다. 3. X번 마을에서부터 다시 i 까지 돌아가는 거리를 구한다. 다익스트라 함수는 흔히 알고있는 다익스트라를 구현한다. 해당 거리를 저장하는 배열을 지속적으로 갱신해주고, 결과값에 저장후, 최대값을 찾아 .. 공감수 0 댓글수 0 2022. 11. 10.
[백준 / BOJ] C++ 1167 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리 내에 임의의 두 점 사이중 가장 거리가 긴 점을 이어야한다. Root에서 가장 멀리 떨어진 정점으로 풀면 되겠지 했지만.. 안되서 해설을 찾아보았다. 루트에서 가장 멀리 떨어진 점과, 임의의 점에서 부터 가장 멀리 떨어진 정점의 합을 구하면 된다고한다. 저렇게만 보면 쉬운데.. 문제 풀이에 대해 아직 조금 미숙한것 같다. Code #include #include #inc.. 공감수 0 댓글수 0 2022. 11. 3.
[백준 / BOJ] C++ 1149 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 연속적으로 같은색을 사용하지 않으면 되는 문제입니다. 2차원 배열에서 arr[i][0] 의 i 색이 연속적으로 동일하면 안되는 간단한 문제입니다. Code #include using namespace std; int N; int rgb[3]; int arr[999][3]; int result; int main() { ios::sync_with_stdio(false); c.. 공감수 0 댓글수 0 2022. 11. 2.
[백준 / BOJ] C++ 1043 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 과장된 이야기를 할 수 있는 파티의 갯수를 세어줘야한다. 우선 문제에서 주어지는 순으로 정리를 해보자. 첫번째 줄에는 N,M으로 사람의 수와 파티의 개수를 입력해준다. 두번째 줄에는 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는사람들을 체크하며, 해당 번호를 진실체크하는 queue에 넣어준다. 세번째 줄부터는 파티에 오는 사람의 명수와 번호가 주어진다. 입력받은 M만큼 반복하며, 해당 파티에 .. 공감수 0 댓글수 1 2022. 10. 28.
[백준 / BOJ] C++ 6198 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 풀이 Stack을 이용한 간단한 문제이다. 스택에 i 번째 건물을 추가할때, 해당 건물보다 작거나 같은건 모두 pop을 해준다. 이후 pop해주고 stack에 남은 size만큼 total에 추가해주고, 다음 건물을 stack에 push 해준다. 그런데 해당 문제를 풀다가 total변수 자료형을 int로 하고, stack 자료형을 int로 하여 문제를 풀었으나, 계속 틀렸다고 하여서 다시 찾.. 공감수 0 댓글수 0 2022. 10. 19.
[백준 / BOJ] C++ 17610 양팔저울 https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 풀이 틀렸습니다와 런타임 에러로 고생한 문제... 이문제 난이도가 실버 1이라니 ..ㅜ 어떻게 해야할까 생각하다가 알고리즘 분류에 브루트포스 알고리즘을 보자말자 '완전탐색 문제구나' 했다. 우선 위의 그림과 같이 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게를 구해야한다. 이 경우의 수는 아래의 이미지와 같다. 따라서, 양팔저울에 무게추를 올리는 경우의 수는 다음과 같이 정리할 수 있다.. 공감수 0 댓글수 0 2022. 10. 19.
[백준 / BOJ] C++ 1697 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 문제에서 주어지는 조건 3가지를 만족하는 한 모든 경우의 수를 큐에 넣어버린다. 이후, 수빈이의 위치 X와 동생의 위치 K가 동일한 값이 되는 가장 처음 값을 구하면 된다. 계속 반복하며 처음 입력한 위치를 기준으로 모든 경우의 수를 큐에 다 넣고, 동생의 위치만 수빈이와 동일하면 정지시켜주자. 이후, 해당 위치값을 출력하면 끝. 직전 포스팅인 미로 문제와 크게 다.. 공감수 0 댓글수 0 2022. 10. 17.
[백준 / BOJ] C++ 2178 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 연결된 점을 찾아가는 문제이다. (N,M). 이런문제는 알고리즘 분류에도 나와있지만, 너비 우선탐색으로 풀 수있다. 너비우선 탐색은 보통 큐 (queue)를 이용하여 구현한다. 큐에 관해 포스팅 되어있으니 참고하길 바란다. https://hyun-jun5.tistory.com/m/57 [Algorithm] C++ Queue (큐) 클래스 구현 큐 ( Queue ) FIFO(First In First Out) - 선입선출 이.. 공감수 0 댓글수 0 2022. 10. 17.
[백준 / BOJ] C++ 1260 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS란? - 깊이우선탐색(Depth First Search)으로, 방문할 수 있는 정점이 있을경우, 계속해서 탐색해 나가는 방법이다. 보통 스택이나 재귀함수를 이용하여 탐색한다. BFS란? - 너비우선탐색(Breadth First Search)으로 해당 노드층의 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통 큐를 .. 공감수 0 댓글수 0 2022. 10. 14.
[백준 / BOJ] C++ 11000 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 우선순위 큐와 vector를 이용하였다. vector에 시작시간과 종료시간을 넣은 후 오름차순으로 정렬한다. 이후 우선순위 큐에 오름차순으로 정렬된 종료시간을 저장하고, 이후 종료시간과 두번째 저장된 시작시간을 비교한다. 종료 시간보다 시작시간이 작은 경우는, 다른 강의실을 사용해야하기에 우선순위 큐에 넣어주고, 예외 상황에는 동일 강의실을 쓰기에, pop 이후 다시 push를 해준다. Code #include #include #inclu.. 공감수 0 댓글수 0 2022. 10. 13.
[백준 / BOJ] C++ 2075 N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 우선순위 큐를 이용한 간단한 문제입니다. 전체 숫자를 전부 큐에 넣으면 아니나 다를까, 시간초과입니다. 정렬된 우선순위 큐에서 주어진 수 N의 크기보다 더 클 경우 해당 숫자를 pop 해주고, N개의 큰 수들만 남겨놓는 식으로 풀 수 있습니다. Code #include #include using namespace std; int main() { ios::sync_with_stdio(false); c.. 공감수 0 댓글수 0 2022. 10. 12.

문의안내

티스토리
로그인
고객센터

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