'Cpp' 태그의 글 목록
본문 바로가기
728x90

Cpp18

백준 No.3190 [뱀] BOJ No.3190 [뱀] 문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 설명 * 구현 우선순위 큐 와 셋 을 사용하여 구현을 해서 풀었다. 게임이 끝나는 조건은 두 가지 조건이 있다. 1. 벽과 만나는 경우 -> 현재 위치가 맵을 벗어났을 때 현재 시간을 return 하였다. 2. 몸과 부딪히는 경우 -> 현재 몸이 있는 좌표들을 set 에 추가하여 몸과 부딪히는 여부를 파악하였다. 2-1) 현재 좌표에 해당하는 set 이 이미 있다면, 몸과 부딛힌 경우이므로 현재.. 2021. 8. 26.
백준 No.1261 [알고스팟] BOJ No.1261 [알고스팟] 문제 1261번: 알고스팟 (acmicpc.net) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 * Dijkstra (다익스트라) * 너비 우선 탐색 (BFS) 주어진 미로의 각 좌표들을 노드라고 생각하고, 좌표에서 이동할 수 있는 방향은 상하좌우로 인접한 네 방향이므로 이 네 방향을 하나의 간선이라고 생각할 수 있다. 좌표의 최대 크기는 100 * 100 이다. 따라서 노드의 최대 개수는 10,000 개가 되며 한 노드당 좌표의 모서리에 위치한.. 2021. 8. 17.
백준 No.1626 [두 번째로 작은 스패닝 트리] BOJ No.1626 [두 번째로 작은 스패닝 트리] 문제 1626번: 두 번째로 작은 스패닝 트리 (acmicpc.net) 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100, www.acmicpc.net 설명 * 최소 스패닝 트리 / 최소 신장 트리 (MST) * 최소 공통 조상 (LCA) 먼저 최소 스패닝 트리(MST) 를 먼저 구해야 한다. 두 번째로 작은 스패닝 트리는 앞서 구한 MST 보다 총 가중치의 값은 최소한으로 늘어나야 한다. 문제에서 예제 입력을 가지고 최소 스패닝 트리.. 2021. 8. 17.
백준 NO.13537 [수열과 쿼리 1] Baekjoon Online Judge No.13537 [수열과 쿼리 1] 문제 13537번: 수열과 쿼리 1 (acmicpc.net) 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 설명 * 정렬 * 인덱스드 트리 * 세그먼트 트리 (Segment tree) 세그먼트 트리, 인덱스드 트리를 이용하여 풀 수 있으며 이번에는 인덱스드 트리를 통해 풀어보았다. 세그먼트 트리나 인덱스드 트리에서 가장 중점은 트리의 노드를 어떻게 정의하느냐 인 것 같다. 이번 문제에선 각 트리의 노드.. 2021. 8. 14.
백준 No.14427 [수열과 쿼리 15] Baekjoon Online Judge No.14427 [수열과 쿼리 15] 문제 14427번: 수열과 쿼리 15 (acmicpc.net) 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 설명 * 세그먼트 트리 (Segment tree) 기본적인 세그먼트 트리 자료구조를 통해 풀 수 있는 문제이다. 1. 트리의 노드들에 그 노드에 해당하는 수열의 영역 내에서 최소값을 가지는 원소의 {값, 인덱스} 를 저장한다. 최소값을 저장하는 조건은 문제의 요구대로 아래.. 2021. 8. 13.
백준 No.17070 [파이프 옮기기 1] No.17070 [파이프 옮기기 1] 문제 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 설명 동적할당(DP : Dynamic programming) 을 이용하여 풀 수 있는 문제이다. 점화식을 위한 dp 배열은 3차원으로 선언을 하였다. dp[ i ][ j ][ k ] == (i, j) 좌표로 오는 파이프가 k 방향에서 올 수 있는 경우의 수 (k == 1 인 경우는 좌측, k == 2 인 경우는 위, k == 3 인 경우는 .. 2021. 8. 8.
백준 No.3830 [교수님은 기다리지 않는다] Baekjoon Online Judge No.3830 [교수님은 기다리지 않는다] 문제 3830번: 교수님은 기다리지 않는다 (acmicpc.net) 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 설명 유니온 파인드 (2021.08.06 - 유니온 파인드 (Union Find, Disjoint set))알고리즘을 이용하여 샘플(노드)을 추가해야 하는 경우엔 추가하고 두 샘플의 무게를 비교할 땐 비교를 해야한다. 유니온 파인드 알고리즘은 노드들간의 그룹 여부를 알 수 있는 알고리즘.. 2021. 8. 6.
백준 No.1005 [ACM craft] Baekjoon Online Judge No.1005 [ACM craft] 문제 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 설명 위상정렬(2021.08.05 - [Algorithm (C++ based)/Algorithm 이론] - 위상 정렬 (Topological Sort))의 기본 개념을 이용하여 풀 수 있는 문제이다. 위상정렬을 통해 각 건물(노드)에 방문을 할 때 마다 그 건물을 짓는데 걸리는 시간을 계속해서 최대값으로 업데이트를 한다. .. 2021. 8. 5.
유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 유클리드 호제법 이란 두 자연수 사이의 최대공약수(GCD) 를 구하는 알고리즘 이다. gcd(a, b) == a 와 b 의 최대공약수 라고 할 때 알고리즘에 사용되는 식은 다음과 같다. gcd(a, b) == gcd(b, a % b) ... (b 2021. 8. 4.
백준 No.7453 [합이 0인 네 정수] Baekjoon Online Judge No.7453 [합이 0인 네 정수] 문제 7453번: 합이 0인 네 정수 (acmicpc.net) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 설명 투 포인터 알고리즘을 활용하여 풀었다. 투 포인터를 하기 이전 투 포인터를 할 수 있는 상태를 만들어야 한다. 위와 같이 4개의 배열이 주어졌다고 할 때, 결국 네 배열의 원소의 합이 0인 경우가 몇 번 있는지를 찾는 것 이므로, 각각의 배열들은 다른 배열과 무조건 한 번씩은 더해지는 작업을 거치게 된.. 2021. 8. 2.
백준 No.9466 [텀 프로젝트] Baekjoon Online Judge No.9466 [텀 프로젝트] 문제 9466번: 텀 프로젝트 (acmicpc.net) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 설명 학생들을 노드라고 하고, 학생들이 각각 본인이 팀을 하고 싶은 상대를 간선으로 표현하였다. 결국, 한 팀이 이루어지기 위해선 아래와 같이 싸이클이 이루어져야 한다. 빨간 간선들이 팀을 의미한다. {1, 2, 4} 세 명 이서 한 팀을, {3} 혼자서 한 팀을 이렇게 총 두 팀을 이루었고, {5, 6, 7}은 모두 팀을 이루지 못 했다. 처.. 2021. 8. 2.
백준 No.12015 [가장 긴 증가하는 부분 수열 2] Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2] 문제 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 설명 2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열] 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가.. 2021. 7. 28.
백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li.. 2021. 7. 28.
백준 No.7579 [앱] BOJ No.7579 [앱] Problem 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #define memory first #define cost second using namespace std; typedef pair PII; int cost_max =.. 2021. 2. 22.
백준 No.11066 [파일 합치기] Baekjoon Online Judge No.11066 [파일 합치기] Problem 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #incl.. 2021. 2. 7.
728x90