레츠고✨

🌱 들어가기 전Python으로 코딩테스트를 풀 때에는 itertools 라이브러리를 사용해서 순열, 조합을 쉽게 사용할 수 있었는데,Java에서는 순열, 조합 라이브러리가 없어서 다 구현해야 한다.Java로 코테를 옮기면서 가장 불편한 점 중 하나이다.. 그래서 Java로 순열, 조합을 구하는 방법을 모두 정리해보려고 한다.   1️⃣ 순열순서를 고려하여 n개의 값 중에서 r개의 숫자를 뽑는 경우를 말한다.예를 들어 [1,2,3] 이라는 크기3의 배열에서 순서를 고려해서 2개의 숫자를 뽑는 경우는 3!/1! = 6가지 [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 방법1. SWAP을 이용한 순열(재귀)swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법이다.배열의 첫 값..

🔍  최장 증가 부분 수열이란?LIS  = Longest Increasing Subsequence원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열 예를 들어, nums = [4, 7, 2, 8, 10, 3, 11, 9] 라는 배열이 있다면[4, 7, 2, 8, 10, 3, 11, 9] => [4, 7, 8, 10, 11] 와 같이 증가하는 부분 수열 중 길이가 가장 긴 것을 말한다.반대로 감소하는 부분 수열 중 가장 긴 것은 최장 감소 부분 수열(LDS, Longest Decreasing Subsequence)이라고 한다. 코딩 테스트 문제 중에는 최장 증가(감소) 부분 수열을 이용한 문제들이 왕왕 있어 이번 ..

컴퓨터로 해결할 수 있는 다양한 문제들이 있지만, 컴퓨터도 연산 속도와 메모리 공간의 한계가 있기 때문에 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제들은 컴퓨터로도 해결하기 어려울 수 있다. 그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는데, 이러한 대표적인 방법이 바로 "다이나믹 프로그래밍" 기법이다. 1. 대표적인 예시 : 피보나치 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시에는 '피보나치 수열'이 있다. 피보나치 수열 : 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 ex) 1 1 2 3 5 8..

vector, list, set, map, pair, algorithm 헤더, cmath헤더, cctype헤더 저번 포스트에서 C++ STL가 무엇이고, 어떤 것들로 이루어지는 것인지 알아보았다. 오늘은 그중 시퀀스 컨테이너에 속하는 deque 에 대해서 알아보자. 시퀀스 컨테이너 : 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지된다. 1. vector 2. deque 3. list list 특징 더블 링크드 리스트, 노드 기반 컨테이너 구조이다. 장점 포인터로 다음 값을 찾아주는 방식이므로 모든 삽입 삭제가 용이하다. 단점 vector에서 가능했던 데이터의 위치로 값에 접근을 할 수 없다(순차접근만 가능) 용법 1. 선언/초기화 방법 #include list lt; // 비어 있는 li..

vector, list, set, map, pair, algorithm 헤더, cmath헤더, cctype헤더 저번 포스트에서 C++ STL가 무엇이고, 어떤 것들로 이루어지는 것인지 알아보았다. 오늘은 그중 시퀀스 컨테이너에 속하는 deque 에 대해서 알아보자. 시퀀스 컨테이너 : 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지된다. 1. vector 2. deque 3. list deque 특징 vector의 단점을 보완하기 위해서 만들어진 컨테이너 vector와 마찬가지로 배열기반의 구조이며 동적길이를 갖는다. vector는 새로원 원소가 추가될 때 메모리 재할당 후 이전 원소를 복사하는 방식으로 인하여 삽입시에 성능이 저하되는 단점이 있다. deque는 이런 단점을 보완하기 위해서..

vector, list, set, map, pair, algorithm 헤더, cmath헤더, cctype헤더 저번 포스트에서 C++ STL가 무엇이고, 어떤 것들로 이루어지는 것인지 알아보았다. 오늘은 그중 시퀀스 컨테이너에 속하는 vector 에 대해서 알아보자. 시퀀스 컨테이너 : 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지된다. 1. vector 2. deque 3. list vector 특징 동적배열이다. 즉, 자동으로 메모리가 할당되는 배열이라는 의미이다. 따라서 배열의 크기가 유동적이다. 임의의 위치에 있는 원소 접근과 뒤에서 원소를 추가하는 연산은 O(1)을 보장하여 매우 빠르다. 따라서 데이터의 위치를 안다면 배열처럼 쉽게 접근할 수 있다. 단점 중간 값 삽입과 삭제가 ..

vector, list, set, map, pair, algorithm 헤더, cmath헤더, cctype헤더 STL이란? Standard Template Library의 줄임말로 C++의 템플릿을 사용하여 표준으로 정리한 라이브러리이다. 반복자 / 컨테이너 / 알고리즘 함수객체 등의 라이브러리로 구성되어 있다. 컨테이너 : 기본 자료형과 사용자가 정의한 자료형을 담는 일종의 자료구조 크게 3종류로 나눌 수 있다. 시퀀스 컨테이너 어댑터 컨테이너 연관 컨테이너 1. 시퀀스 컨테이너 데이터를 선형적으로 저장하는 구조이다. 자료를 입력한 순서대로 저장하기 때문에 저장, 검색, 알고리즘에 불리하다. 적은 양의 자료를 저장하거나 검색 속도가 중요하지 않은 경우에 사용하는 것이 좋다. vector list deq..