두잉낫띵 두잉낫띵

정렬 : sort() 함수 이용 - #include 선언해줘야함 - 퀵소트로 구현되어있어 빠른 속도로 정렬함 - 기본적으로는 오름차순으로 정렬을 해줌 ex) 1,2,3,4,5,6 - 사용법 : sort(v.begin(),v.end()); → 내림차순으로 정렬하고싶을땐 어떻게 할까 ? 1. 비교함수를 만들어서 인수로 주자 ( return 형은 bool ) #include #include #include #include using namespace std; bool compare(int a ,int b) { // 비교함수 return a > b; } void main() { vector num = { 1,2,3,4,5 }; sort(num.begin(), num.end(), compare); for (aut..

#include #include #include using namespace std; /* 순열 알고리즘 */ void Permutation(vector& Array, int Start, int End) { if (Start == End) { for (const auto it : Array) { cout

문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil..

큐 ( queue ) : 먼저 들어간 데이터가 먼저나오는 FIFO 구조의 자료구조 우선순위 큐 ( priority queue ) : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 구현하는 3가지 방법 1. 배열을 기반으로 구현 2. 연결리스트를 기반으로 구현 3. 힙을 이용하여 구현 - 가장 효율적임 힙 : '이진트리 ' 중에서도 '완전 이진 트리' 최대힙 : 부모노드 > 자식노드 최소힙 : 자식노드 > 부모노드 C++ 의 priority_queue 의 구조 (1) push(1), push(2). 현재 가장 큰 수: 2(top) (2) push(3). 현재 가장 큰 수: 3(top) (3) push(9). 현재 가장 큰 수: 9(top) (4) push(8). 현재 가장 큰 수: ..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 [6, 10, 2] 6210 [3, 30,..

BFS 너비 우선 탐색 : 시작 정점을 방문한 후에 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법 DFS 와는 달리 ( 스택이용 ) "큐" 를 사용하여 구현한다. 예제 ↑위와 같은 그래프가 있다. 준비물 visited 배열 : 방문한 노드는 true 로 바꿔서, 방문했던 노드를 다시 방문하지 않도록 하기위한 장치 mem 큐 : dfs 와는 다르게 큐를 사용한다. 1. 시작 노드 "0" 을 큐에 넣는다. 2. "0" 에 대한 visited 를 true 로 바꾼다. 1. "0" 을 큐에서 뺀다. 2. 큐에서 빼져있는 "0" 과 인접한 노드 "1" 과 "2" 를 큐에 차례대로 삽입한다. 3. "1" 과 "2" 의 visited 를 true 로 바꾼다. 1. "0" 을 출력한다. 1. "1" 을 큐에서 ..

#include #include #include using namespace std; int answer = 0; void dfs(int index, int sum , int target , vector numbers) { if (index == numbers.size()) { // numbers 의 마지막 원소까지 간 경우 if (sum == target) { // sum 이 target 과 같으면 answer++; } return; } dfs(index+1, sum+numbers[index], target, numbers); // 더하는쪽으로 dfs(index+1, sum-numbers[index], target, numbers); // 빼는쪽으로 } int solution(vector numbers..

코테에 자주 등장하는 DFS / BFS 중 DFS 에 대해 다뤄보려고 한다. 그래프와 트리를 검색하는 알고리즘 중 하나인 DFS : 깊이 우선 탐색 구현시 " 스택 " 을 이용하여 구현한다. 예제 아래와 같은 그래프가 있다고 하자. 준비물은 mem 스택 : 선택된 노드와 인접한 노드들을 스택에 쌓아놓고 하나씩 빼면서 살펴볼때 이용한다. visited 배열 : 노드가 mem 스택에 들어간 경우 값을 true 로 바꾸어 , 방문한 노드를 다시 방문하는 경우가 없도록 한다. 1. 제일먼저 가장 처음 노드를 스택에 넣고 , 해당 노드의 visited 를 true 로 바꾼다. 1. 스택에서 "0" 을 꺼낸다 2. "0" 과 인접한 노드 1, 2 를 순서대로 스택에 넣는다. 3. "1" 과 "2" 에 해당하는 vi..