devBB 메모장

백준 온라인 저지(BOJ) 1010번 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N개의 강 서쪽 사이트에서 M개의 강 동쪽 사이트로 N개의 다리를 연결하려 함 다리끼리 겹치지 않도록 다리를 짓는 경우의 수를 출력 2. 풀이 결론부터 말하면 M개의 사이트에서 N개를 뽑는 경우의 수, 즉 mCn을 출력하면 됩니다. M개의 사이트에서 N개를 선택한 후 각각의 케이스 별로 가능한 경우의 수는 ..

백준 온라인 저지(BOJ) 11050번 이항 계수 1 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 자연수 N과 정수 K가 주어졌을 때 nCk(이항 계수) 출력 2. 풀이 이항 계수 공식을 활용하여 풀 수도 있지만 N과 K의 크기가 작기 때문에 단순하게 구현했습니다. nCk는 n! / ((n - k)! * k!) 이므로 {n * (n - 1) * ... * (n - k + 1)} / k! 입니다. 따라서 n부터 1씩 빼면서 곱하는 절차를 k번 진행한 후, 그 값을 k!로 나눠..

백준 온라인 저지(BOJ) 10872번 팩토리얼 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 0보다 크거나 같은 정수 N에 대해서 N!을 출력 2. 풀이 N!은 N * (N - 1) * (N - 2) * ... * 1 입니다. 이를 그대로 구현하면 N을 입력받은 후 N부터 1까지 1씩 빼면서 곱해날 수 있습니다. 단, 이렇게 할 경우 N이 0인 경우를 따로 처리해주어야 합니다. (0!은 0이 아니라 1이므로) 저는 0인 경우를 따로 처리하지 않기 위해 출력 값(res)를 1로 초기화한 뒤, for문으로..

백준 온라인 저지(BOJ) 24723번 녹색거탑 https://www.acmicpc.net/problem/24723 24723번: 녹색거탑 Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N층의 녹색거탑에서 바닥까지 내려오는 최단 경로의 경우의 수 출력 2. 풀이 N을 입력받고 2^N을 출력하면 됩니다. N의 최대값이 5이기 때문에 단순하게 1을 N회 만큼 2배한 후에 출력했습니다. 만약 N이 충분히 큰 문제이거나 library를 활용하고자 한다면 mat..

백준 온라인 저지(BOJ) 15439번 베라의 패션 https://www.acmicpc.net/problem/15439 15439번: 베라의 패션 베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까? www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N개의 상의와 N개의 하의가 있고 i번째 상의와 하의는 같은 색상임 N개의 색이 모두 다를 때 상의와 하의가 서로 다른 색상의 조합을 출력 2. 풀이 상의로 선택할 수 색상은 N개이고, 하의는 상의 색상을 제외한 나머지 색 중에서 선택할 수 있으므로 (N - 1)개 입니다. 따라서 N * (N - 1..

백준 온라인 저지(BOJ) 24511번 queuestack https://www.acmicpc.net/problem/24511 24511번: queuestack첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제각각 1개의 원소만 있는 queue 또는 stack이 N개 연달아 나열되어 있고, 이를 queuestack 자료구조라 함 queuestack에 숫자가 들어오면 1번부터 N번까지 순차적으로 push & pop을 반복하며 다음..

백준 온라인 저지(BOJ) 2346번 풍선 터뜨리기 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 1번부터 N번까지의 풍선이 순서대로 원형 형태로 놓여있음 (1번 → 2번 → 3번 → ... → N번 → 1번) 각 풍선 안에 들어있는 종이에 -N보다 크거나 같고, N보다 작거나 같은 정수가 적혀있음 1번 풍선을 터뜨린 후 종이에 있는 값만큼 이동하여 다음 풍선을 터뜨림 (양수는 오른..

백준 온라인 저지(BOJ) 28279번 덱 2 https://www.acmicpc.net/problem/28279 28279번: 덱 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 정수를 저장하는 덱을 구현한 후, 입력으로 주어지는 명령을 처리하는 프로그램 구현 2. 풀이 Library를 사용하지 않고 DEQUE 자료 구조를 구현해보았습니다. List 계열 자료구조를 구현할 때 자주 활용하는 방식인데, 연습을 충분히 하면 관련 자료구조를 구조화하는 역량이 많이 늘어납니다. _node를 struct로 구현한 뒤 각 ..

백준 온라인 저지(BOJ) 11866번 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 1번부터 N번까지 N명의 사람이 원을 이루어 앉아있음 1부터 K번째 사람을 한 명 씩 제거하면서 제거되는 순서대로 출력 2. 풀이 처음에는 배열로 만들고 제거된 자리에 -1로 표시한뒤 cnt를 늘리며 직접 확인하는 방식을 생각했습니다. 하지만 애초에 매번 K번을 반복하는 것도 비효율적인데 제거된 자리를 계속 skip하면서 세는건 너무 비효율적인 것 같아서 List 구조를 활용하여 자..

백준 온라인 저지(BOJ) 2164번 카드2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 1부터 N까지 번호의 카드가 위에서 아래로 순서대로 놓여있음 제일 위 카드를 버리고, 그 다음 제일 위 카드를 제일 아래로 옮기는 동작을 반복했을 때 마지막으로 남은 한 장의 번호를 출력 2. 풀이 FIFO(First In First Out)인 큐를 구현하면 풀 수 있는 문제입니다. 개인적으로 Linked Li..