이번 글에선, c++ 에서 순열과 조합을 재귀를 통해 구현하는 포맷에 대해 알려드리겠습니다. 혹시 next_permutation을 통한 풀이가 궁금하시다면, 아래 글을 참고해주세요. 순열과 조합 (C++) — 코딩이랑 이것저것 (tistory.com) 순열과 조합 (C++) [ n개의 숫자를 전부 사용해서 만들 수 있는 모든 순열의 갯수] ex) 1,2,2 가 input으로 들어오면 1,2,2 2,1,2 2,2,1 3가지가 나온다. 여기서 중요한 점은 "중복된 순열은 제거" 된다는 점이다. 1,2( 1th ) , 2( 2 codenme.tistory.com 1) 순열 nPm, 즉 n개의 값들 중, m개를 처럼 순서를 고려해서 선택한다. ex: (1,2) != (2,1) 입출력 예시 4 2 //4P2 12..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 이 문제를 처음 보고선, 단순하게 시작점부터 각 노드간의 최단 거리를 모두 찾고, 그 중 가장 긴 거리의 수를 고르려고 했다. 이 방법엔 2가지 솔루션이 있다. 1) 시작점에서 각 노드간의 거리를 다익스트라로 구하기: [ V*O(V^2) == O(V^3) ] 2) 플로이드 와샬로 각 정점들간의 최단 거리 모두 구한 뒤, 시작점에서 각노드간 최단거리만 사용하기 [O(V^3)] 하지만, 주..
이번엔 해시, 혹은 c++ 헤더에 정의되어있는 "map" 자료구조를 통해 해결할 수 있는 문제들에 대하여 이야기해보겠다. map은 기본적으로 {key,value} 의 데이터쌍을 가진다. 사용하기 위해선 #include using namespace std; 위 헤더파일을 include해야한다. 정의는 map 으로 이루어지며, string형 key 값을 가지고, int형 value 값을 가지는 map의 경우 map ma; 와 같이 정의하면 된다. https://school.programmers.co.kr/learn/courses/30/parts/12077 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭..
https://school.programmers.co.kr/learn/courses/30/lessons/81304 위 문제에 대한 해설입니다. 우선 문제를 풀기 전 내가 가장 고생했던 부분은 trap 노드의 개수가 10개가 최대라는 점이다. 처음에 trap 노드 개수의 제한이 없고, 즉 input n의 개수인 3000개까지 trap이 생길 수 있다고 생각하고 고생을 좀했다. 만약 trap의 개수가 10개라는 정보를 안다면, "trap 노드" 라고하는 매우 복잡한 노드를 따로 처리하는 방식을 어렵지 않게 생각할 수 있을 것이다. 하지만 그럼에도 이 문제가 어려웠던 점은, 기존에 우리가 알던 "최단 거리" 알고리즘의 전제를 바꾸어 놓는다는 것 이다. 이 문제의 경우, 특정 시작점에서 도착점으로 향하는 최단거..
https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 문제를 보면 무식한 방식으로 풀어도 될거같다는 느낌이 옵니다. 제한사항을 보면 문자열 길이가 1000이하로 주어졌는데, 반복가능한 문자열 단위는 최대 500입니다. 그 이유는 전체 문자열 길이의 절반을 넘어가면 반복되는 문자열을 통한 압축이 불가능해지기 때문입니다 ex: aaaabb >> 길이 단위를 4로 해도 2aaaa 이런식으로 압축이 불가능합니다. 길이가 ..
분리집합 응용문제를 하나 들고 왔습니다. 분리집합에 관한 기본적인 지식은 생략하고 해당 문제의 핵심 아이디어만 아래 코드블럭의 주석에 구체적이게 달아 놓았으니 참고하세요! #include using namespace std; #include int n, m,cnt; int arr[1000000]; int find(int a) { if (arr[a] == a) return a; else return arr[a] = find(arr[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a == b)return; arr[a] = b; //두번째 파라미터가 첫번째 파라미터의 부모가 된다. } int main() { scanf("%d %d", &n, &m..
lis는 10, 20, 10, 30, 20, 50 이런 길이 5의 수열중 10, 20 ,30 ,50 과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다. dp를 통해서 풀게되면 O(N^2) 이고, lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다. lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 자세한건 아래 문제를 보면서 알아보자..! 1.lis 의 길이는? lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다. 흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다..
