본문 바로가기

알고리즘

 (19)
Programmers / heap / 더 맵게 https://www.welcomekakao.com/learn/courses/30/lessons/42626 https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)#%EC%98%88%EC%A0%9C heap은 최대값 또는 최소값을 찾아내는 연산을 빠르게 하기 위해서 고안된 완전이진트리 기반의 자료구조이다. max heap : 부모노드의 key 값이 자식노드의 key 값보다 항상 큰 heap min heap : 부모노드의 key 값이 자식노드의 key 값보다 항상 작은 heap 이 문제는 최소값을 매 단계마다 계속 찾아야 하므로 min heap을 구성하면 효율적으로 최소값..
Programmers / BFS, DFS / 여행 경로 https://www.welcomekakao.com/learn/courses/30/lessons/43164?language=cpp 1. 가능한 경로가 두개 이상일 경우, 알파벳 순서가 앞서는 경로를 찾아야 된다. 그러므로 탐색 순서를 알파벳순으로 하면 해결되기 때문에, 초기 항공권 배열을 오름차순으로 정렬한다. 2. 알파벳순으로 탐색하므로, DFS를 수행해서 제일 먼저 모든 항공권을 사용한 경우가 정답이다. 3. 주의할 점은 틀린 경로라면 다시 돌아가서 rollback 작업을 수행할 것인데, 해답을 찾은 경우에도 재귀적으로 함수를 빠져나가므로 rollback 하지 않고 return 하도록 처리해야 한다. #include #include #include #inclu..
Programmers / BFS, DFS / 단어 변환 https://www.welcomekakao.com/learn/courses/30/lessons/43163 1. 최소 변환을 구해야하므로 BFS 기법으로 탐색 2. cur(현재단어) = begin 부터 시작해서 단어 리스트를 조사해서 변환 가능한 문자열들을 모두 큐에 추가 => 이 때, 큐의 요소는 (단어, 단계수) 형태로 저장 3. target 단어가 되거나 큐가 빌 때(모든 단어를 탐색 완료)까지 2의 과정 수행 4. 만약 마지막 조사한 단어가 target이 아니면, 모든 단어를 탐색하고 빠져나온 경우이므로 answer = 0 4-else. target 단어이면 cur.second에 단계수가 있으므로 answer=cur.second #include #inclu..
Programmers / BFS, DFS / 네트워크 https://www.welcomekakao.com/learn/courses/30/lessons/43162 1. 0번 컴퓨터 부터 시작하면서 0번 컴퓨터와 연결된 모든 컴퓨터를 찾아낸다. 2. 찾아낸 컴퓨터들을 방문했다고 체크하고, 네트워크 수를 1 증가 시킨다. 3. 방문하지 않은 컴퓨터가 없을 때까지 반복한다. #include #include #include using namespace std; int solution(int n, vector computers) { int answer = 0; // 해당 컴퓨터가 네트워크 확인에 쓰였는가 vector visited(n); queue que; for (int i = 0; i < n; i++) { // 이미 조사한..
Programmers / BFS, DFS / 타겟 넘버 https://www.welcomekakao.com/learn/courses/30/lessons/43165 1. 주어진 숫자 배열을 DFS 기법으로 구현한다. 2. 한번은 양수로, 한번은 (-1)을 곱한 음수로 넣는다. 3. 모든 숫자를 다 설정했다면, 합계를 계산해서 target과 일치하는지 확인한다. #include #include #include using namespace std; int answer = 0; vector num_list; // 구성된 숫자 배열을 합산하여 target과 일치하는지 검사 int calc(int target) { int total = 0; for (int i = 0; i < num_list.size(); i++) { total..
Programmers / 완전탐색 / 카펫 https://www.welcomekakao.com/learn/courses/30/lessons/42842 1. 노란 영역을 기준으로 가로길이를 row, 세로길이를 col 이라고 하면... - brown = 2*row + 2*yellow + 4 - yellow = row * col 2. col을 1부터 해답이 나올 때 까지 증가시킨다. -> 이 때, row = ((brown - 4) - (2*yellow)) / 2 이다. #include #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; // yellow 영역을 기준으로 row와 col을 사용 i..
Programmers / 완전탐색 / 소수 판별 https://www.welcomekakao.com/learn/courses/30/lessons/42839 1. 주어진 숫자 조각들로 모든 경우의 수를 만든다. -> 이 때, 중복되는 수가 생길 수 있으므로 set을 사용하면 자동으로 중복이 제거되므로 편리!! + 재귀 함수를 사용해서 모든 경우의 수를 만들 수 있다. 2. 만든 경우의 수에 대해서 소수판별을 각각 수행한다. - 소수 판별법 : 2부터 해당 숫자의 제곱근까지 나누었을 때, 모두 나누어 떨어지지 않으면 소수이다. #include #include #include #include #include using namespace std; vector visited; vector num_list; set num..
Programmers / 완전탐색 / 모의고사 https://www.welcomekakao.com/learn/courses/30/lessons/42840 1. 1번, 2번, 3번 수포자가 맞춘 문제수를 계산 2. 제일많이 맞춘 개수를 찾아냄 3. 그 찾아낸 점수에 해당하는 사람을 오름차순으로 저장 #include #include #include using namespace std; vector one = { 1,2,3,4,5 }; vector two = { 2,1,2,3,2,4,2,5 }; vector three = { 3,3,1,1,2,2,4,4,5,5 }; // 맞춘 수에 대해서는 내림차순, 사람의 인덱스에 대해서는 오름차순 bool cmp(pair a, pair b) { if (a.second ..

티스토리툴바