✨ Algorithm

STL 헤더 iostream, vector, string, algorithm 등 유용한 것이 많은데, 이를 GCC계열 컴파일러에서는 하나로 모아둔 헤더가 존재한다. #include 대부분의 경우에 위와 같이 한줄만 입력하면 해결이 되지만, 코딩테스트 환경에 따라 개별적으로 헤더파일을 추가해야되는 경우도 있다. #include #include #include #include stl을 사용하기 위해서 std라는 namespace를 계속 사용해주어야하는데 이를 생략하려면 다음 한줄을 추가해주면 된다. using namespace std; I/O 속도개선 먼저, sync_with_stdio를 해제해주면, cin과 cout의 속도가 크게 향상된다. 대신 scanf/printf를 cin/cout 과 같이 쓰지 못하..

STL에 algorithm 헤더파일을 추가하면(#include ) 다음 아래 함수를 통해서 순열을 구할수가 있다. next_permutation 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환. 함수를 실행하기 전, 무조건 오름차순 정렬이 되어있어야 한다. ex) 순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정을 하면 next_permutation의 함수를 사용하면 배열의 값들이 다음 순열인 1-2-4-3로 바뀌고 함수는 true를 반환합니다. #include #include #include using namespace std; int main(){ // 1부터 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 먼저, 장르별로 재생횟수, 고유번호를 같이 m1 맵에 넣어주고 장르별로 재생횟수의 합을 m2 맵에 넣어준다. - cmp 함수 m1의 맵을 돌면서 재생횟수가 같으면 고유번호를 오름차순해주고, 재생횟수가 다르면 재생횟수를 내림차순해준다. (여기서 auto &x : m1은 x를 m1의 요소에 대한 참조로 가져오기 위해 &를 사용한다. 원본을 변경하기 위해서는 참조를 사용해야 합니다.) - cm..

https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 다리를 건너는 트럭을 queue를 사용해 푸는 문제이다. 먼저 현재 무게에 대기 트럭 첫번째 값을 넣어준다. 다리를 건너는 트럭의 총 무게 + 현재 무게 다리가 버틸 수 있는 무게면 무게가 0인 트럭으로 대체하여 넣어준다. 시간은 answer++로 while문이 돌아갈 때동안 1씩 증가시켜준다. #include #include #include using namespace std; /* b..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ✅ 누적합이란? x0, x1... xn까지 수가 있을 때 y0 = x0, y1 = x0 + x1, yn = x0 + x1 +... + xn처럼 해당 n까지의 합을 의미한다. y0 = x0 y1 = x0 + x1 y2 = x0 + x1 + x2 ... yN = x0 + x1 + ... + xN ✅ 누적합의 성질 i부터 j의 합을 구하려면 누적합 j에서 누적합 i - 1을 빼주..

https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 문제를 딱 보자마자 유니온 파인드 알고리즘이 생각났다. 풀고보니 유니온 파인드의 기본적인 문제이며, 부모 노드의 중복되지 않은 숫자의 개수는 몇 개인지 세면 되는 단순한 문제였다. 풀이 1 #include #include #include using namespace std; int parent[201]; int getParent(int x){ if(parent[x] == x) return x; re..

https://programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 다익스트라의 기본 문제이다. 다익스트라 알고리즘을 활용하여 dist 값을 찾아낸 뒤, 가장 큰 값을 찾아 그 값과 일치하는 개수를 세면 된다. #include #include #include using namespace std; const int INF = 1e9; vector dist; vector edge[20001]; priority_queue pq; void dijkstra(int..

https://programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 3중 for문에 익숙해지면 풀 수 있는 문제이다. #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for(int i = 0; i < arr1.size(); i++){ vector v; for(int j = 0; j < arr2[0].size(); j++){ int sum =..

https://programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 (0, 1, 2)(0, 2, 1)(1, 0, 2)(1, 2, 0)(2, 0, 1)(2, 1, 0) 다 돌아보면서 가장 많이 탐험할 수 있는 던전의 수를 세는 것이다. 그러므로, next_permutation 알고리즘과 dfs 알고리즘을 둘 다 쓸 수 있다. 풀이 1 (next_permutation) next_permutation 알고리즘을 쓰기 전에 먼저 정렬을 해준다. k의 수는 순열 ..

https://programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 next_permutation 알고리즘으로 풀면 쉽게 풀리지만, 그렇게 해선 시간초과가 나는 문제이다. 해결 방법은 팩토리얼을 사용하여 각 자리의 수를 직접 구해야 된다. 풀이 1 #include #include using namespace std; long long facto(int n){ if(n == 1) return 1; return n * facto(n - 1); } void r..