선택은 나의 것

문제 BOJ 15591 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 접근 한 정점에서 다른 정점으로의 USADO값의 최솟값을 구하기 위해 모든 정점에서부터 BFS를 돌아준 뒤 입력받은 K값보다 크거나 같은 값을 USADO로 가지는 것을 세주어서 문제를 풀었다. 다만 다 풀고 나니 이 과정을 따로 나눌 필요 없이 BFS 한 번에 해결할 수 있도록 짰으면 메모리와 시간을 더 효율적으로 사용..

문제 BOJ 1874 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 스택(LIFO : 후입선출)으로 문제에서 주어지는 수열을 만들 수 있는지 확인하는 문제이다. 후입선출 구조란 말 그대로 늦게 들어온 자료가 가장 먼저 나가는 구조를 뜻한다. 양동이 모양을 생각하면 편할 것이다. 이러한 후입선출 구조를 생각해서 코드를 짜면 쉽게 해결할 수 있는 문제이다...

문제 BOJ 3865 : https://www.acmicpc.net/problem/3865 3865번: 학회원 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 학회의 수 n이 주어진다. n은 100을 넘지 않는 양의 정수이다. 다음 n개 줄에는 각 학회의 학회원 정보가 문제에서 www.acmicpc.net 접근 구하고자 하는 임의의 학회에 가입한 회원의 정보는 사람일 수도, 또 다른 학회일 수도 있다. 이때 가입한 회원이 사람이 아닌 또 다른 학회라면 그 학회에 포함되어있는 사람들의 명단을 가지고 와야 하기 때문에 DFS로 접근하게 되었다. 하지만 이 과정에서 똑같은 학회가 여러 번 불릴 수 있기 때문에 메모이제이션(memoization)을 통해 visit 처리를 하여 동일한..

문제 BOJ 13417 : https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net 접근 알파벳이 적힌 카드가 n장이 있을 때 이 카드를 순서대로 뽑아서 내가 가진 알파벳 카드들의 왼쪽 혹은 오른쪽에 배치할 수 있다. 이렇게 배치했을 때 사전 순으로 가장 빠른 문자열을 출력해주는 문제이다. 따라서 뽑은 알파벳이 현재 내가 가진 문자열의 가장 앞의 알파벳보다 사전 순으로 빠르다면 문자열의 가장 앞에(왼쪽에), 아니라면 뒤에(오른쪽에) 배치해 주면 된다. ..

문제 BOJ 17089 : https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 접근 친구 관계를 입력받아 두 사람(a, b)이 친구라면 2차원 배열의 값을 1로 주어 친구 관계임을 나타낸다. 동시에 특정 인물 a가 몇 명의 친구를 가졌는지를 저장해주는 배열의 값도 증가시켜준다. 다음으로 임의의 사람 i와 j가 친구라면 임의의 사람 k와 i, k와 j가 친구인지 확인해준다. 세 사람이 친구인지 확인했다면 i..

문제 BOJ 18310 : https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 접근 이 문제에서 안테나는 단 한 집에만 설치할 예정이고, 안테나가 있는 집에서 다른 집까지의 거리는 최소가 되어야 한다. 따라서 집들을 정렬해준 뒤에 가운데에 위치한 집의 위치를 출력해주면 된다. 코드 #include #include #include using namespace std; int main() { int n, t; cin >> n; vector v; for (int i = 0; ..