분류 전체보기
BaekJoon(10844)::쉬운 계단 수
문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악 여기서 쉬운 계단수란? '인접한 모든 자리의 차이가 1'인 수를 말한다. N이 주어졌을때, 길이가 N인 쉬운 계단 수가 몇개 있는지 구하는 문제이다. 여기서 주의할점은 숫자의 길이가 100자리를 넘는다는 점과 0으로 시작하는 수는 계단수가 아니라는 점이다 문제 풀이 해당 문제의 진행을 다음과 같다. 결국 N자리의 수에서의 계단수의 갯수는 N-1번째 계단의 수에서 결정이 된다. 이유를 잘생각해보면 N자리의 마지막 수는 N-1번째 계단수의 마지막수와 차이가 1일 수 밖에 없기 때문이다. 이러한 점을 잘 생각해보면 다음과 같은 식을 구할 수 있다. 끝자리의 값이 무엇..
BaekJoon(1463)::1로 만들기
문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제파악 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 최소 연산횟수를 구하는 문제. 즉, DP를 사용하면 해결이 가능해 보인다. 문제풀이 해당 문제도 dp를 이용하면 풀수 있을 것이며, 그중 나의 경우 반복문을 이용해서 풀 생각이다. dp[n] = dp[n-1] + 1는 기본적으로 가능한 횟수이다. 그리고 각 나누어떨어지는 상황 즉, 2로 나누는 연산과 3으로 나누는 연산과의 횟수를 비교해서 작은 값을 저장해 주면 된다. #include using na..
BaekJoon(10773)::제로
문제 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 파악 해당 문제는 0을 넣으면 가장 최근에 넣은 수를 빼는 문제 즉, 스택을 이용해서 문제를 해결하면 된다. 여기서 0은 지울수 있는 수가 있음을 보장하기 때문에 empty 여부를 확인 하지 않아도된다. 문제 풀이 딱히 풀이 할 것이 없어보인다. 스택을 이용하면 된다. #include #include using namespace std; int main() { int n; cin >> n; stack st; while ..
BaekJoon(9012)::괄호
문제 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제파악 괄호문자열(Parenthesis String,PS)은 두 개의 괄호 기호인 '('와 ')'로 구성된 문자열. 그 괄호 모양이 잘 닫혀져 있으면 올바른 문자열은(Valid PS, VPS)라고 부른다. 예를 들어 '(()())' 그리고 '((()))' 등은 vps지만 '(()(' 혹은'(()' 등은 vps를 만족하지 못한다. '(' 그리고 ')'로 구성된 문자열 : VPS 두개의 vps로 접합된 문자열 또한 VPS 만족 ..
JAVA::자바에서 형변환(Casting)하기
형변환(Casting) 알고리즘 문제를 해결하다 보면 종종 숫자를 string으로 변환해서 문제를 해결하거나 char형으로 변경해서 문제를 해결하는것이 더 유리한 경우도 있습니다. 그리고, 그 외에도 작업을 하다보면 여러 타입간의 연산을 수행하거나 특정 형식을 맞추기위해 형을 바꿔야하는 경우가 있습니다. 이러한 경우에 변수나 리터럴 타입들을 다을 타입으로 변환해주느데 이것을 형변환이라고 합니다. 정의(Definition) 변수나 리터럴 타입을 다른 타입으로 변환하는 것 형변환 종류(자동 vs 강제)?? 그렇다면 현변환은 어떻게 해야할까? 일반적으로 컴파일러에 따라 형변환을 생략하더라도 알아서 자동적으로 추가해서 형변환시켜주는데 이를 자동형변환(묵시적 형변환)이라고 한다. 그리고 그렇지 않은 경우 바꿀 타..
BaekJoon(1003)::피보나치 함수
문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제파악 피보나치수열 아마 쉽게 알 수 있는 문제일 것이다. 피보나치 수열이란? 첫째 및 둘째 항이 1이며 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열 그렇다면, 이 문제는 피보나치수열에서 무엇을 원하는 건지 알아봐야 한다. 피보나치수열의 점화식은 다음과 같다 $$f(n) = f(n-1)+f(n-2) \quad and \quad n \geqq 2$$ 정의상 n은 3 이상일 수 있지만 편의상 0번째 항의 값을 0으로 생각한다면 2 이상으로 생각해도 무관하다. 그리고 피보나치를 재귀로 구현하면 다음과 같다. int fibonacci(int n) { if..
BaekJoon(1010)::다리놓기
문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제파악 문제를 읽어보면 강을 중심으로 왼쪽 영역 N개에서 오른쪽 영역 M개의 영역으로 다리를 연결하게 되는데 그 때 가능한 케이스의 갯수를 구하는 문제이다. 이경우 다음과 같이 한영역에 다리가 겹쳐지거다 교차될 수 없다고 한다. 다음 그림을 보면 좀더 이해가 쉬울 거 같다. 이렇게 봤을 때...문제를 어떻게 해결할 수 있을까 생각해보면, M영역 즉, 우측지역의 영역에서 N(좌측)영역의 지역의 갯수만큼 선택해서 순서대로 연결해주면 교차하지도 않고 겹치지도 ..
BaekJoon(9461)::파도반 수열
문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제파악 파도반 수열은 리처드 파도반에 의해 이름이 붙여졌으며, 오른쪽 그림과 같이 삼각형들이 한변의 길이를 공유한 상태로 나선형으로 계속해서 이어지는 삼각형이다. 해당 수열이 진행을 보면 다음과 같다 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 수열과 같은 문제를 풀다보면 대부분 점화식을 찾아내면 쉽게 해결할 수 있다. 파도반 수열의 점화식은 다음과 같다 $$f(n)=\begin{cases}1 & \mbox{if }n..
Data Structure::Queue(큐)
Queue(큐) 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조(LILO이라고도 할 수 있다.) Queue 연산 큐 자료구조는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 따르게 되며 먼저 들어간 데이터가 먼저 제거되는 구조가 된다. 해당 자료구조를 만족하기 위해서 여러 연산이 필요하다 Enqueue(Data) :스택에서의 Push와 같은 연산으로 데이터를 추가해주는 연산. Dequeue() : 제일 처음 추가된 데이터를 제거하는 연산 Peek() : 제일 처음 추가된 데이터를 얻는 연산(front에 위치한 데이터) isEmpty() : 큐에 데이터가 있는지 여부를 확인하는 연산 용어는 Enqueue를 Add,..
LeetCode(977)::Squares of a Sorted Array
문제 Squares of a Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. 배열에 저장된 수들을 제곱하여 다시 정렬하면되는 문제로 파악된다. 1
LeetCode(344)::Reverse String
문제 Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. in-place로 문제 해결. 즉, 추가 메모리(공간복잡도)는..
LeetCode(344)::Reverse String
문제 Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. in-place로 문제 해결. 즉, 추가 메모리(공간복잡도)는..