https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 알고리즘 s = a^n을 만족하는 가장 큰 n을 찾는다는 것은 문자열의 패턴의 최대 갯수를 찾으라는 문제다. 주의해야 할 점은 문자열의 최대 길이는 백만글자 미만이다. 인덱스별 탐색을 하려면 O(n^2)으로 시간초과가 날 것이다. 즉, 문자열 비교를 효율적으로 탐색하기 위해 KMP 알고리즘을 사용해야 한다. KMP 알고리즘이란? https://sasca37.ti..
KMP 알고리즘 KMP는 알고리즘을 설계한 Knuth-Morris-Pratt의 앞글자를 하나씩 따서 만든 알고리즘으로 문자열 검색을 효율적으로 할 수 있는 알고리즘이다. (ctrl + f 해서 찾는 검색 알고리즘이 KMP 알고리즘) 전체 텍스트의 길이를 N, 찾고자하는 문자열을 M이라 할 때 각 인덱스 별 비교를 하면 시간 복잡도는 O(NM)이지만, KMP 알고리즘을 적용하면 O(N+M)으로 찾을 수 있다. 실패 함수 KMP 알고리즘의 원리는 실패함수를 이용하는 것이다. 실패 함수란 문자 매칭에 실패했을 때 전체 비교인 O(NM)을 효율적으로 처리하기 위해 건너 뛸 자리를 구하기 위한 함수이다. 즉, 텍스트와 패턴이 불일치 상황에서 접두사 / 접미사가 일치한 최대 길이를 구하여 다음에 건너 뛸 자리를 결..
객체 지향 OOP is A PIE Abstraction (추상화) : 현실 객체를 추상화해서 클래스를 구성 Polymorphism(다형성) : 하나의 객체를 여러 가지 타입으로 참조 (메서드 다형성, 타입 다형성) Inheritance(상속) : 부모 클래스를 물려받아 자식이 재정의 Encapsulation(캡슐화) : 데이터를 외부에 직접 노출시키지 않고 메서드를 이용해 보호 Type Primitive Type (기본형) 미리 정해진 크기의 Memory Size로 표현 변수 자체에 값 저장 long 보다 더 큰 값을 표현하고 싶을 땐 무한대에 가까운 BigInteger를 사용한다. Reference Type(참조형) 크기가 미리 정해질 수 없는 데이터의 표현 변수에는 실제 값을 참조할 수 있는 주소만 ..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 알고리즘 부분합의 짧은 길이를 출력하는 문제로 이중 반복문을 사용하면 시간초과가 발생하며, 투포인터를 사용해야하는 문제이다. start, end를 0으로 초기화한 후, end++를 해가며 sum의 값을 더한다. sum이 S보다 크면 길이를 측정하고, start를 end 전까지로 이동한다. 풀이 import java.io.*; import java.util.StringTokenizer..
객체 지향 프로그래밍 1960년대 하드웨어 발전 속도에 비해 소프트웨어의 발전 속도는 느렸다. 하드웨어처럼 모듈화를 못했기 때문이었다. 이를 위해 소프트웨어에 객체지향 패러다임이 등장 객체와 객체 간 자유로운 데이터 이동이 가능 절차지향프로그래밍 : 위에서 부터 아래로 순차적으로 진행되는 형태 프로그램 재사용시 기존에 만들어진 코드를 복사 붙여넣기 하는 방식 모듈을 만들어 공유 데이터로 공유하는 방식으로 구현되었지만, 유기적으로 연결되어야하는 단점이 있다. 객체 현실 세계에 존재하는 모든 것을 객체로 표현 정적인 요소 : 변수 - 자동차 (이름, 속도, 제조사) 동적인 요소 : 메서드 - 자동차 (시동켠다(), 가속한다(), 시동끈다()) 클래스 현실 세계의 객체를 컴퓨터 메모리에서 생성할 수 있는 일종..
직관과 증명의 패러다임 카드 문제 사실 : 모든 카드의 한쪽에는 알파벳, 다른 쪽에는 숫자 존재 주장 : 한쪽이 D라면 반대쪽은 3 주장이 사실임을 증명하기 위해 반드시 뒤집어보아야하는 카드는? 문제 : D F 3 7 정답은 D, 7 2개이다. F는 주장과 관련이 없으므로 뒤집어볼 필요가 없고, 3은 D가 있든 없든 영향을 주지 않는다. 7은 뒤집었을 때 D가 나온다면 주장이 성립하지 않게 되므로 확인해봐야 한다. 맥주집 문제 규칙 : 20세 이하인 사람은 맥주를 마실 수 없음 17세 , 31세, 콜라, 맥주 - 4명 중 확인이 필요한 사람은? 정답은 17세, 맥주 2명이다. 카드 문제보다 맥주집 문제가 풀기 쉽게 느껴지지만 논리적 구성은 동일하다. 그렇다면 왜 맥주집 문제가 풀기 쉬운가? 이유는 맥주집..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 LIS(Longest Increasing Subsequence) 문제이다. 원소가 N개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 그 길이가 최대인 부분 수열을 최장 증가 부분 부분 수열(LIS)라고 한다. {10, 20, 10, 30, 20, 50 } 의 LIS 는 10,20,30,50이 최장이므로 ..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 N이 100까지 이므로, Long타입을 통한 dp 배열을 생성해야 한다. 특히 인접한 모든 자릿수의 차이가 1이라는 것에서 0과 9일 때 예외처리를 해주어야 한다. 또한, N=1일 때 모든 수가 계단 수 이므로 dp[1][0~9]를 1로 초기화 해주어야 한다. i번째 자릿수가 0일 때 다음 자릿수의 값 : 1 , i번째 자릿수가 9일 때 다음 자릿수의 값 : 8 , 나머지 i+1, i-1 이 된다. 소스 코드 import java.io.BufferedReader; import java.io.IOExce..