나쿠리 개발 메모장

개요 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 실버4 난이도 문제다. 풀이 처음 문제를 봤을 때는 그래프의 탐색으로 접근하려고 했다. 근데 그렇다고 하기엔 난이도가 낮았다. (꼼수 , , ) 처음에는 비행기를 탑승한 횟수인 줄 알았는데, 다시 보니 탑승한 비행기의 종류를 구하는 문제였다. 어차피 N개의 노드를 방문하려면 무조건 N-1개의 간선을 지나야 한다. 그래서 N-1을 출력해 줬더니 해결됐다. ..

개요 회로에서 같은 동작을 한다면, 가급적 회로를 최소화 시켜 해야한다. (복잡성, 가격 등의 이유) K-Map True Table을 그림의 형태로 재구성하여 나타낸 표이다. 네모 칸들로 구성된 다이어그램이며, 각 칸은 최소화하고자 하는 함수의 하나의 최소항(minterm)을 나타낸다. K-Map을 활용하면 훨씬 직관적으로 계산 가능하다. 인접한 칸을 묶어서 간략화하는데, 2의 거듭제곱의 개수로 묶어야 한다. 양 끝 면은 서로 인접한 것으로 간주하고 묶어서 간략화할 수 있다. 주항(Prime Implicants) 주항은 Map에서 인접한 칸을 최대로 많이 묶을 때 생기는 곱의 항을 의미한다. 어떤 칸에 있는 항이 단 하나의 주항에 의해서만 커버된다면, 이 주항을 필수 주항(Essential PI)이라고한..

개요 재밌는 백준 문제 풀이,, 훌륭한 분들이 만들어 놓은 확장 기능들을 사용해 더 재밌게 즐겨보자,,! 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으로 사용..