어흥

문제 링크: https://www.acmicpc.net/problem/17352 17352번: 여러분의 다리가 되어 드리겠습니다! 선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 www.acmicpc.net 1. 주의할 점 - 딱히 없다 - 입력이 많을 수 있기 때문에 입출력 속도에 신경쓴다 2. 구..

문제 링크: https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 입출력 속도 함수를 사용해야 한다 (cin, cout의 경우 사용하지 않으면 TLE 발생) - 매 TC마다 Factorial을 구하지 않고 미리 구해놓는다 - 페르마의 소정리에 대해 알고 있어야 한다 2. 구현 *공통 부분 - My_pow(Num, Remain) 함수를 직접 구현하여 Pow함수를 LogN번 안에 계산하도록 한다(분할 정복). 라이브러리에 있는 Pow함수는..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - 위상정렬 알고리즘의 기초에 대해 알고 있어야 한다 - 사용하는 배열이 많기 때문에 주석 혹은 변수명을 잘 사용한다 - Need_time[] : 해당 번호만을 짓는데 걸리는 시간 - Need_pre[]: 해당 Node를 짓기 위해 남..

문제 링크: https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다. 지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한 www.acmicpc.net 1. 주의할 점 - 메모아이징을 사용한 DFS를 이용한다 (DP문제) 2. 구현 - Check[] 배열을 전..

문제 링크: https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 1. 주의할 점 - 음의 가중치를 가지는 간선이 존재한다 -> 벨만포드 알고리즘 (다익스트라 알고리즘은 음의 가중치가 있으면 적용하지 못한다) - Int의 범위를 벗어날 수도 있기 때문에 (Dist의 값이) Long Long으로 설정하지 않으면 "출력초과"가 발생한다 2. 구현 - 2차 배열을 이용한 형태와 벡터에 간선을 담..

문제 링크: https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 1. 주의할 점 - MST 문제로, 프림 혹은 크루스칼 알고리즘에 대하여 알고 있어야 한다. 여기서는 크루스칼 사용 - X..

문제 링크: https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 문제 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다. 상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이 www.acmicpc.net 1. 주의할 점 - 매 TC마다 초기화 필수 - 도착지점에서 뻗어나가는 간선은 존재하면 안된다 - 간선형태로 정보를 저장..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 (모두 중요) - 이 문제는 구현보다는 배열을 어떻게 설정할 것인지 생각하는게 중요! - Arr[][],Numx[],Numy[]를 직접 만들어서 시행했는데, TC를 입력받기 전에 미리 1번 Make_arr()함수를 실행하여 생성해 놓는다 - 6각형 모양이라고 생각하고 (y,x)를 기준으로 6방향인 (y-1,x+1), (y,x+2), (y+1,x+1), (y+1,x-1)..