Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ##### 문제 ##### # 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. # 토마토는 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. # 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, # 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, # 익은 토마토들의 인접한 곳에 ..

▶ 문제 : https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net ##### 문제 ##### # 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. # 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, # 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. # 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 ..

▶ 문제 : https://www.acmicpc.net/problem/1432 1432번: 그래프 수정 첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. N은 50보다 작거나 같은 www.acmicpc.net ##### 문제 ##### # N개의 정점이 있는 그래프가 주어지면, 다음과 같은 방법에 의해서 정점의 번호를 다시 매기고 싶다. # 모든 그래프의 번호는 1보다 크거나 같고 N보다 작거나 같은 번호를 가져야 한다. # 만약 V1에서 V2로 연결된 간선이 있다면, V2의 번호는 V1보다 커야 한다. # 위와 같은 조건을 이용해서 그래프의 번호를 다시 매긴 후에, # 1번 정점의 새..

▶ 문제 : https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net ##### 문제 ##### # 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. # 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. # 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. # 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다. # 어떤 장난감 완제품..

▶ 문제 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ##### 문제 ##### # N명의 학생들을 키 순서대로 줄을 세우려고 한다. # 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, # 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. # 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. # 일부 학생들의 키를 비교한 결과가 주..

▶ 문제 : https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net ##### 문제 ##### # 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. # N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. # 이 구슬 중에서 무게가 전체의 중간인(무게 순서로 (N+1)/2번째) 구슬을 찾고자 한다. # 우리에게 주어진 것은 양팔 저울이다. # 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무..

플로이드 워셜 알고리즘(Floyed-Warshall Algorithm)은 모든 정점에서 모든 정점 사이의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘이 하나의 정점에서 모든 정점 사이의 최단 경로를 찾는 것과는 차이가 있다. 또한 가중치를 음수와 양수 모두 가질 수 있다는 점도 다르다. 플로이드 워셜 알고리즘의 기본 동작 원리는 다음과 같다. 1. 최단 거리 테이블을 만든다. 이때, 초기 주어진 조건으로 하나의 정점에서 다른 정점으로 바로 갈 수 있는 경우 그 값으로, 갈 수 없는 경우 무한대로 테이블을 초기화한다. 2. 모든 정점에 대하여 해당 정점을 지나 다른 정점으로 이동할 때의 거리를 구하고, 기존의 거리와 비교하여 그 거리가 더 짧다면 테이블의 값을 갱신한다. 점화식으로 표현하자면 다음과..

▶ 문제 : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net ##### 문제 ##### # 지구 온난화로 인하여 북극의 빙산이 녹고 있다. # 빙산을 2차원 배열에 표시한다고 하자. # 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. # 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. # 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, # 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이..

▶ 문제 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ##### 문제 ##### # N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. # 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. # 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. # 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있..

▶ 문제 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ##### 문제 ##### # 그래프의 정점의 집합을 둘로 분할하여, # 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, # 그러한 그래프를 특별히 이분 그래프(Bipartite Graph) 라 부른다. # 그래프가 입력으로 주어졌을 때, # 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. ##### 입력 ##### # 입력은 여러 개의 테스트..