CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 두 개의 포인터를 이용하여 해결할 수 있습니다. 수열에서 연속된 수들의 부분합 중에 그 합이 S를 넘는 것 중, 가장 짧은 것을 찾는 것이 문제이기 때문에, 연속된 수들의 첫 부분과 마지막 부분을 포인터로 가리키고, 이 두 포인터를 적절히 증가시키며 최소 길이를 구할 수 있습니다. ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하면 비교적 어렵지 않게 해결할 수 있습니다. 한 작업이 시작되기 전에 완수되어야 할 여러 작업들을 입력으로 받아서, 해당 작업들이 완료되는데 걸리는 시간들을 확인하여 가장 늦게 끝나는 작업의 시간에 자신의 작업 시간을 더해서 dp 배열에 추가해주면 됩니다. t라..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 언뜻 보기에는 bfs로 풀 수 있을 것 같은 문제이지만, 특히 JAVA를 이용해 bfs로 구현을 하면 메모리 초과, 또는 시간 초과가 뜰 확률이 굉장히 높습니다. 이 문제는 bfs 대신 다이나믹 프로그래밍을 이용해 해결할 수 있습니다. 우선 arr라는 배열에 입력으로부터 행렬을 받아 넣습니다. 그리고 arr[i][j]를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이를 d..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 이 문제는 '', 그리고 공백에 대한 예외처리만 잘해주면 쉽게 해결할 수 있습니다. 저는 스택을 이용해 문자열을 뒤집고 출력했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 복잡하게 생각하지 말고, 배열에서 증가하는 부분과 감소하는 부분을 별개로 반복문을 수행하면 쉽게 정답을 찾아낼 수 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 풀이 이 문제는 스택을 이용하여 해결할 수 있습니다. 자신보다 오른쪽에 있는 수 중에 자신보다 크고 가장 왼쪽에 있는 수를 찾는 문제이기 때문에, 배열의 가장 뒤에서부터 반복문을 돌며 자신보다 크고 가장 왼쪽에 있는 수를 스택에 저장하는 방법을 사용하였습니다. 아래의 예시를 이용해 설명해보도록 하겠습니다. 우선 스택에 가장 오..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 이 문제를 풀기 위해서는 기본적인 아이디어가 하나 필요합니다. n이라는 값이 주어진다면, n은 1 + (n-1) or 2 + (n-2) or 3 + (n-3) 으로 표현될 수 있습니다. 다시 말해, n-1을 만드는 경우의 수에 1을 더하면 n이 되고, n-2를 만드는 경우의 수에 2를 더하면 역시..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍으로 접근할 수 있습니다. 상황에 따라 옮길 수 있는 위치가 다 다르므로 (직각으로 꺾을 수 없다던지...), 배열을 3개 선언하여, 오른쪽 칸으로 보내줄 수 있는 경우의 수, 아래쪽 칸으로 보내줄 수 있는 경우의 수, 대각선으로 보낼 수 있는 경우의 수..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 다이나믹 프로그래밍으로 누적 합을 구하는 아주 기초적인 문제입니다. 배열을 하나 별도로 만들어 우선 해당 값까지의 총합을 구해 저장시켜두고, 입력으로 구간을 받아 해당 구간의 합을 구해주면 됩니다. 예제에서 배열의 입력이 5 4 3 2 1 이었으니, 해당 값까지의 합을 구해두는 배열 ..

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