CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 전형적으로 다이나믹 프로그래밍을 이용하여 해결하는 문제이고, 구현도 어렵지 않습니다. 왼쪽부터 다이나믹 프로그래밍을 위한 dp라는 배열을 채워나갈 텐데, 다음과 같은 규칙을 갖습니다. 바로 A칸에 들어갈 dp의 값은 1번 칸까지의 dp 값과, 2번 칸까지의 dp 값과, 3번 칸까지의 dp 값 중 ..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 기본적인 문제의 풀이는 아래의 문제와 같습니다. jooona.tistory.com/104 [BOJ] 1463 - 1로 만들기 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이.. jooona.tistory.com..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 굉장히 전형적인 다이나믹 프로그래밍 문제처럼 보이지만, 다이나믹 프로그래밍으로 해당 문제를 구현 시 메모리 초과가 나는 것을 확인할 수 있었습니다. 이 문제는 다이나믹 프로그래밍이 아닌 그리디 알고리즘으로 접근을 해야 합니다. B에서부터 뒤에 1을 뗄 수 있으면 떼주고, 2로 나눌 수 있으면, 2로 나누어주면서 A까지 이동하는 것입니다. 물론 1을 떼는 것에 우선순위를 둡니다. 그리고 중간에 1을 뗄 수도, 2로 나눌 수도 없는 ..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 문제의 시간제한을 봐도 알 수 있듯이, 이 문제는 다이나믹 프로그래밍을 이용해서 해결해야 합니다. 문제는 1을 만드는 것이지만, 구현은 반대로 1에서 N을 만드는 최소 연산 수를 구하는 식으로 했습니다. 배열을 하나 만들어, 반복문을 돌며 배열의 i 번째 칸에 i까지 오는데 걸리는 연산의 최소 횟수를 저장해주고, 마지막에 배열의 N번째 칸에 들어있는 값을 출력해주면 됩니다. i 번째 칸까지 오는데 필요한 연산의 최소 횟..

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 풀이 이 문제는 스택을 이용하는 전형적인 문제입니다. 다른 고려사항도 없어 쉽게 해결할 수 있습니다. 문자열에서 문자를 받아서 1. 스택이 비었으면 스택에 push 한다. 2. 스택이 비어있지 않다면, 스택의 top에 있는 문자를 확인한다. 3. 만약 top에 있는 문자와 자신이 같다면, 해당 문자를 스택에서 pop 해준..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 필요한 시간의 합을 최소화하기 위해서는 당연히 짧게 걸리는 순서대로 연산을 수행하면 됩니다. 즉 입력을 한 배열에 담고 해당 배열을 오름차순으로 소팅하여 총시간을 계산해주면 됩니다. 예를 들어, 1 2 3 4 ... 순서로 줄을 서 있다면, 1이 인출을 하기 위해 기다려야 하는 시간은 1초 2가 인출을 하기 위해 기다려야 하는 시간은 1..

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