전체 글
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로 문제 해결. 즉, 추가 메모리(공간복잡도)는..
LeetCode(448)::Find All Numbers Disappeared in an Array
문제 Find All Numbers Disappeared in an 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 array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. n == nums.length 1
Binary Search Algorithm(이진 탐색 알고리즘)
Binary Search Algorithm 여러가지 탐색 알고리즘들을 보면 여러가지 알고리즘을 찾을 수 있다. 가장 기본적으로는 선형 탐색 방식으로 앞에서 부터 하나씩 비교하며 찾는 방법이다. 말그대로 탐색을 한 쪽 끝에서 다른 끝까지 탐색하기 때문에 탐색 대상이 뒤쪽에 위치해있으면서, 탐색 대상이 많은 경우 매우 비효율적일 수 있다. 하지만, 만약 탐색하고자 하는 데이터가 정렬이 되어 있는 경우 좀더 효율 적인 방법을 이용할 수 있는데 이것이 바로 이진 탐색 알고리즘이다. 정의(Definition) 정렬된 탐색대상에서 특정 대상을 찾고자 할때 사용 할 수 있는 탐색 알고리즘 정렬된 알고리즘으로 부터 탐색 중간값과 탐색대상을 비교후 탐색 범위를 절반으로 줄여가며 찾는 알고리즘 이렇게 정렬된 알고리즘으로 ..
LeetCode(189)::Rotate Array
문제 Rotate 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 array, rotate the array to the right by k steps, where k is non-negative. 배열의 값이 k스텝 마다 한칸씩 오른쪽으로 넘기면 될 거 같습니다. 문제풀이 해당 문제는 여러가지 풀이 기준이 존재하는데 인덱스 기준으로 생각할 수도 있으며, 시프트 방식으로 in-place로 문제를 해결할 수도 있다. 해결책 1..