나쿠리 메모장

개요 재밌는 백준 문제 풀이,, 훌륭한 분들이 만들어 놓은 확장 기능들을 사용해 더 재밌게 즐겨보자,,! BaekjoonHub(백준 허브) 백준 허브는 LeetCode의 개인 풀이를 github에 자동 푸시해주는 LeetHub에서 영감을 받아 만든 프로젝트입니다. 백준, 프로그래머스를 통해 알고리즘 공부를 하시는 분들이 더욱 쉽게 코드를 저장하고 관리할 수 있게 하도록 만들었으며, 오픈소스 프로젝트로 여러분의 조언과 참여를 환영합니다. 백준에서 문제를 풀면 연동된 깃허브의 레포지토리로 자동으로 푸시해주는 엄청나게 편리한 확장기능이다. (프로그래머스도 지원한다) GitHub GitHub - BaekjoonHub/BaekjoonHub: 백준 자동 푸시 익스텐션(Auto Git Push for BOJ) 백준 ..

개요 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 골드3 난이도 문제! 풀이 학생들이 파티가 열리는 마을에 갔다가 자신의 마을로 돌아와야한다. 이러한 학생들중 가장 오래 걸리는 학생의 소요시간을 출력하면 된다. 우선순위 큐를 이용한 다익스트라를 사용했다.(O(ElogE)) Dijkstra 함수의 매개변수로 출발지와 목적지를 받았다. 목적지에 도착했을 경우, 파티 장소인지 체크 후 파티장소일 경우 집을 목적지로 ..

개요 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 골드5 난이도 문제다. 풀이 가중치 그래프 문제로 기본적인 다익스트라 알고리즘 문제 유형이다. V> N >> M; for (int i = 0; i > a >> b >> c; graph[a].push_back({ b, c }); graph[b].push_back({ a, c }); } Dijkstra(); cout

개요 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 골드4 난이도 문제다. 풀이 유니온 파인드로 해결할 수 있다. 진실을 아는 사람의 parent를 -1로 초기화하고, 이를 루트 노드로 사용했다. 파티에 2명이상 있는 경우 Union 연산으로 합쳐주었다. 진실을 아는 사람과 같은 파티에 참석한 사람은 모두 진실을 아는 사람이 된다. (해당 파티에서 진실을 듣기 때문) 때문에 파티들의 첫 번째 손님의 루트 노드를 Find하며 거짓말 할 수 있는 파티인지 ..

개요 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 골드4 난이도 문제다. 풀이 노드간 연결 여부를 확인하는 문제다. BFS를 통해 풀 수도 있겠지만 이번에는 유니온 파인드(disjoint-set)를 이용했다. 같은 경로의 경우 같은 루트 노드를 갖고 있으므로 이를 비교하면 된다. 기본적인 유니온 파인드로 구현이 가능했다. 코드 #include #include using namespace std; constexpr int N_LIMIT = 2..

개요 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 골드2 난이도 문제다. 풀이 문자열과 분리 집합의 형태를 보아하니 유니온 파인드와 map 자료구조로 해결할 수 있을 것 같다고 판단했다. map[current].id = parent 의 형식으로 데이터를 저장했다. 친구 네트워크가 연결될 때마다 루트 노드의 cnt를 연결된 네트워크의 친구의 수 만큼 증가시켰고, cnt가 낮은 네트워크를 높은 네트워크에 넣도록 했다. 그 후 루트 노..

개요 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 골드4 난이도 문제다. 풀이 유니온 파인드 그 자체인 문제다. 유니온 파인드에 필요한 Initialize, FInd, Union 기능을 구현하면 된다. Find 함수에서 경로 압축 최적화를 통해 연산 시간을 줄였다.(Path Compression) Union 함수에서는 레벨이 낮은 트리가 높은 트리에 들어갈 수 있도록 최적화 했다.(Union-by-ran..

개요 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 골드4 난이도 문제다. 풀이 문제를 보고 딱 큐가 떠올랐다. 머리가 늘어나고 꼬리가 사라지는 선입선출 구조! 이동하며 머리가 한 칸 늘어난다.(queue에 push) 이동한 곳에 아무것도 없는 경우 꼬리를 줄이고(queue를 pop) 사과가 있을 경우에는 그대로 진행한다. 만약 뱀 자기 자신이나 벽이 있으면 게임 오버 처리를 해준다. 방향은 1차원 배열을 따로 만들어서 index를 time으로 사용..

개요 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 골드5 난이도 문제다. 풀이 투 포인터로 풀어낼 수 있다. 배열을 정렬 후 양끝에서 각 포인터를 시작한다. 두 포인터의 합이 K보다 큰 경우 큰 쪽 포인터를 작은 쪽으로 이동시키고, 반대로 작은 경우 작은 쪽 포인터를 움직인다. K와 두 포인터 합의 절댓값을 비교한다. 기존 가장 가까운 합보다 더 가까우면 카운트를 1로 만들고 가장 가까운 값을 바꾸어준다. 가장 가까운 값과 동일한 경우 카운트..

개요 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 난이도 문제다. 풀이 투 포인터를 이용하면 간단하게 풀 수 있다. N sum) front++; else if (A[i] sync_with_stdio(0); cin >> N; for (int i = 0; i > A[i]; sort(A, A + N); TwoPointers(); cout