메이쁘

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 안녕하세요. 이 문제는 문자열 검색 알고리즘인 KMP의 기본 문제로서 문제에도 노골적으로 O(전체 문자열 길이 + 찾으려는 문자열 길이) 의 시간복잡도로 문자열을 탐색하라고 나와있다. KMP 알고리즘에 대해 알고싶으면 백준 1701번 문제 포스팅을 보고 와도 좋다. https://maivve.tistory.com/203 (JAVA) 백준 1701번 : Cubeditor https://ww..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 �� www.acmicpc.net 안녕하세요. 처음에 문자열 탐색 문제라고 생각해서 정석대로 문제를 해결하려 했으나 "메모리 초과" ... 이건 아니다.. 먼가 다른 알고리즘이 있을 것이다 해서 몇 번 서치해봤는데 역시나 존재했다. 공부각이다..! 찾아보니, 그것은 바로 KMP 알고리즘 이었다. 간단하게 설명하자면, 그나마 최근에 나온 문자열 탐색 알고리즘 으로, 1) 기본적인 문자열 탐..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 안녕하세요. 그리디 알고리즘 문제로, 난이도는 중 이다. 알아야 할 부분을 정리하자면, - N개의 도시, N-1개의 도로 - 1km -> 1L - 원 안의 숫자 : 리터당 가격. 즉, 1km 당 가격 - 왼쪽부터 순차적으로 이동해야 함 정도가 된다. 문제 해결 방법은 더욱 쉽다. 여기서 구하고자 하는 것은 시작 도시부터 도착 도시까지 이동하는데 드는 최소 비용 이다. 그럼 최소 비용..

https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 안녕하세요. 그리디 + 문자열 문제이다. 난이도는 쉬운 편이다. 거두절미하고, 핵심은 "문자열 안에 순서대로 UCPC 가 들어가있으면 I love UCPC, 들어가있지 않으면 I hate UCPC 이다." UCPC가 붙어있지 않아도 되지만, 반드시 앞에서부터 U - C - P - C 순서대로 들어있어야 한다. UCPC를 배열에 넣거나, 다른 자료구조를 사용해도 된다. ***..

https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 안녕하세요. 이 문제는 그리디 알고리즘 문제다. 난이도는 쉬운 편이기 때문에 핵심만 알면 된다. 즉, 이 문제의 조건만 기억하면 된다! "낮은 레벨의 점수는 반드시 다음 레벨의 점수보다 낮아야 한다." "점수 1을 낮추는 방법을 1이라고 했을 때, 최소의 방법을 구하라." 최소의 방법은 바로 바로 이전의 레벨의 점수가 다음 레벨의 점수보다 1 낮은 것. 굳이 다음 레벨의 점수보다 2, 3, 10..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 안녕하세요. DP(동적 프로그래밍) 문제 중 하나로, 처음에 깊게 생각하지 않아서 한 번 틀리고, 방향을 바꿔 맞출 수 있었다. (사실 두 번 틀렸다.) 이 문제의 핵심은 이거다. 구하려고 하는 수 N의 제곱수의 합은 1 ~ N 까지의 수 중 제곱수인 수 + (n - 제곱수) 의 최소 제곱수 갯수 중 최소인 값 이다. 예를 들어보자. 13 = 2^2 + 2^..

https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 안녕하세요. 이전 포스팅의 2진수 8진수와 반대되는 문제다. 8진수를 2진수로 변환하는 문제인데, 이 역시 마찬가지로 입력 조건을 잘 봐야 한다. "주어지는 수의 길이는 333,334을 넘지 않는다." 즉, 10진수로 8^333334 의 값이 나올 수 있어 숫자 변수를 사용할 수 없다. (직접 변환이 빠르고, 메모리 초과도 발생하지 않는다.) 그렇기 때문에, 8진수 1자리 -> 2진수 3자리 로 바꿔서 각각의 결과를 하나의 문자열로 합쳐야 한다. ex) 8진수 314 -> 011 001 100 (2진수)..

https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 안녕하세요. 문자열 문제로, 2진수 문자열을 8진수로 변환하는 문제다. 근데, 여기서 필자가 착각했던 점은 문제의 입력 조건이었다. 입력 조건을 보자면 "주어지는 수의 길이는 1,000,000 을 넘지 않는다." 즉, 문자열의 전체 길이가 999999 이다. 이를 10진수로 변환한다면, 최대 2^999999 의 값까지 가능하다는 것. 그렇기 때문에, 입력 조건을 생각하지 않고 2진수 -> 10진수 -> 8진수 하려하니 오류가 발생했었다. int에 담을 수 없는 범위이기 때문에. 결국 처음에 틀렸고, ..

https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)�� www.acmicpc.net 문자열 문제. 이것도 상당히 쉬운 문제이다. 괄호 문제라고 해서 필자는 스택을 쓰거나, 복잡한 조건을 간단히 만들어서 알고리즘을 작성하거나, 예외가 많아 까다로울 줄 알았다. 하지만 단순하게도 int 변수 하나로 큰 조건 없이 '(' 와 ')' 의 개수를 파악하면 된다. 매커니즘과 해설은 크게 의미 없을 것 같고 이 해당 괄호가 VPS 에 부합하는 조건만 파악하면..

https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 팰린드롬 문제인줄 알고 들어갔으나 막상 문제 읽어보니 하급 문제. 앞뒤 똑같은지 반복문을 사용하면 끝. 그렇기 때문에, 별도 해설은 생략합니다. 감사합니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 문자열 처리 // 팰린드롬인지 확인하기 (쉬움) public class p10988 { public static vo..