CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 백준에 나와있는 알고리즘 분류에는 DFS나 플로이드-와샬과 같은 알고리즘도 적혀있지만, 가장 해결하기 쉬운 방법은 그냥 브루트포스로 접근하는 것입니다. 우선 입력으로부터 친구들을 모두 구하고, 해당 친구들의 친구까지 확인하여 카운팅 해주기만 하면 됩니다. 코드의 주석을 보는 것이 이해하기 편할 것 같습니다. 1..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 이 문제는 재귀를 이용하면 어렵지 않게 해결할 수 있습니다. 처음에 전체 영상을 모두 검사하여 만일 하나로 통일된 값이 아니면 4등분을 하여 좌측 상단 부분부터 재귀를 돌리면 됩니다. 또 해당 부분이 통일된 값으로 이루어지지 않았다면, 다시 좌측 상단부터 재귀를 수행합니다. 그리고 통일된 구역이..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 특정 구간의 합을 dp라는 배열에 따로 저장하여 문제를 해결했습니다. 만일 예시와 같이 다음과 같은 입력이 주어졌다고 가정하겠습니다. 우선 4x4 크기의 표를 배열에 집어넣고 구간합을 구해줍니다. 구간합..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 풀이는 간단합니다. 우선 K를 입력받았을 때, K번 째 수가 몇 자리 숫자인지를 먼저 파악해야 합니다. K=4 라면 정답이 47이므로 2자리 수, 14라면 777이므로 3자리 수라는 것을 먼저 알아내야 합니다. 그 뒤에는 K가 해당 자릿수 숫자들 중 몇 번째에 해당하는 지를 알아내기만 하면 됩니다. 4와 7로 숫자를 표현했지만, 사실 이진수와 같은 표현법을 사용하기 때문에, ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용해 쉽게 해결할 수 있습니다. 다이나믹 프로그래밍을 위한 배열을 하나 만들고, 이 배열에 해당 칸까지 올 수 있는 경우의 수를 저장해주면 됩니다. 주어진 예제를 이용해보겠습니다. (0, 0)에 2가 들어가 있습니다. 그렇다면, 우측으로 2칸 점프하거나, 아래 방..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 문제는 간단합니다. 땅은 1, 바다는 0으로 표시된 지도를 하나 주고, 해당 지도에서 섬의 개수를 구하는 문제입니다. 한 땅의 상하좌우 또는 대각선에 또 다른 땅이 존재하면 같은 섬으로 인정됩니다. 풀이 이 문제는 dfs를 이용해 어렵지 않게 해결할 수 있습니다. 1을 하나 발견하면 dfs로 이어진 모..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA NxM의 방이 존재하고, 방의 각 칸에는 사탕이 여러 개씩 떨어져 있습니다. 그리고 각 칸에 도착하면 떨어져 있는 사탕들을 모두 주울 수 있습니다. 현재 준규는 가장 좌측 상단에 위치하고, 만일 (i, j)라는 위치에 존재한다면, (i+1, j), (i, j+1), (i+1, j+1) 이렇게 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 우선 1이 한 번, 2는 두 번, 3은 세 번... 반복되는 수열을 만듭니다. 이를테면 122333444455555666666... 과 같은 형태이죠. 여기서 A와 B가 주어지면 수열에서 A에서부터 B까지의 합을 구하는 문제입니다. 풀이 저는 B 크기의 배열을 하나 만들어 배열의 각 원소에 해당 번호까지의 합을 저장했습니다. 즉 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/20117 20117번: 호반우 상인의 이상한 품질 계산법 어떤 묶음에 있는 호반우의 품질이 [1, 2, 3, 4] 라고 하면 중간값인 3으로 모든 호반우의 품질을 계산한다. 따라서 이 묶음의 총 가격은 3 × 4 = 12 가 된다. 품질이 [6, 3, 9] 라고 하면 중간값인 6으로 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 호반우는 품질에 따라 등급이 숫자로 매겨집니다. 호반우 상인들은 N개의 호반우를 개별적으로, 또는 묶음으로 판매할 수 있습니다. 그리고 등급과 같은 가격으로 호반우를 판매합니다. 호반우 상인들은 이윤을 최대화하기 위해 묶음으로 호반우를 판매할 경우,..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/1590 1590번: 캠프가는 영식 첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각, 간격, 대수가 공백을 사이에 두고 주어진다. 버스의 개수와 각 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 영식이는 버스를 타야합니다. 버스터미널에는 N개의 종류의 버스가 존재하고, 영식이가 버스터미널에 도착한 시간은 T입니다. 각각의 버스는 첫 차 시간, 간격, 총 대수의 정보를 가지고 있습니다. 만일 버스에 대한 정보가 150 50 10으로 주어진다면, 해당 버스의 첫 차 시간이 150이고, 50분 간격으..