본문 바로가기

📝 알고리즘/Code Tree

(23)

[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 ..

[코드트리] Backtracking - 백트래킹 / 재귀 연습문제 백트래킹. 대충 알고있는건 백트래킹 == 완전탐색(모든 경우의 수를 무식하게 찾기)에서 가지치기로 효율 높임 이정도라서..ㅋㅋ 연습문제도 풀어봐야겠다 대부분의 알고리즘 문제들은 원하는 모든 조합을 만들어 그 중 문제에서 원하는 답을 고르는 식으로 해결이 가능합니다. 만약 n 제한이 작고, 모든 조합을 만드는 데 걸리는 시간이 문제에서 주어진 제한 시간보다 더 작다면, 항상 모든 조합을 다 만들어 보는 것이 가독성 측면에서나, 코드를 작성하는 입장에서 가장 좋다고 할 수 있을 것입니다. 다만, (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), .. 등 여러 가능한 순열과 조합을 만드는 것을 for문 만을 ..

[코드트리] DFS / BFS 소마 서류에 덜컥 붙어버리고, 코테 준비 4일전사 도전... 자주 나온다는 유형을 급하게 공부해봅니다 하하 DFS는 Depth First Search, 깊이 우선 탐색입니다. 이름처럼 최대한 깊게 탐색한 후 더 이상 도달할 수 없는 상황이라면 다시 이전으로 돌아갑니다. 중요한 것은 깊게 탐색하고 나서 이전과정으로 돌아가야 한다는 점 입니다. DFS는 재귀(스택)를 활용해 구현하는 경우가 많습니다. 즉, 방문할 수 있는 지점이 있다면 그 지점을 방문하는 함수를 재귀적으로 호출하고, 더 이상 방문할 곳이 없다면 함수를 종료하면 될 것입니다. 다만, 이미 방문했던 지점을 또 방문하면 효율이 떨어지기 때문에 이전에 방문했던 지점은 다시 방문하지 않아야 합니다. 한 번 방문한 지점은 어떤 처리를 해서 더 이상 방..

[코드트리] TreeSet 연습문제 문제 : top K 숫자 n개의 숫자가 주어졌을 때, 중복을 제외하고 내림차순으로 정렬했을 때 앞에 있는 k개의 숫자를 출력하는 프로그램을 작성해보세요. 입력 형식 첫 번째 줄에는 원소의 개수 n과 k가 공백을 사이에 두고 주어집니다. 두 번째 줄에는 n개의 원소가 공백을 사이에 두고 주어집니다. 1 ≤ k ≤ n ≤ 100,000 1 ≤ 주어지는 원소 값 ≤ 109 출력 형식 중복을 제외하고 내림차순으로 정렬했을 때 앞에 있는 k개의 숫자를 공백을 사이에 두고 출력합니다. 중복을 제외했을 때 원소의 개수가 k보다 작은 경우는 없다고 가정해도 좋습니다. 나의 풀이 #include #include using namespace std; int main() { int n; int k; int a; set s..

[코드트리] Tree Set SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. set STL C++에서는 set이라는 STL을 이용할 수 있습니다. set은 TreeSet 자료구조로 되어있으며, 이 TreeSet이 바로 균형 잡힌 이진트리 구조로 데이터들을 관리해주는 자료구조 입니다. 모든 함수의 시간복잡도는 O(logN)입니다. set을 사용하기 위해서는 #include 헤더와, set name; 형태의 선언이 필요합니다. T는 타입으로, set 안에 들어갈 원소의 타입을 적어줘야 합니다. #include #include using namespace std; in..

[코드트리] Hash Set 연습문제 문제 : 데이터 비교 정수로 이루어진 두 수열을 비교하여 같은 원소를 가지고 있는지 판단하는 프로그램을 작성해 보세요. 입력 형식 첫 번째 줄에는 수열 1의 원소의 개수 n이 주어집니다. 두 번째 줄에는 수열 1의 원소들이 공백을 두고 주어집니다. 세 번째 줄에는 수열 2의 원소의 개수 m이 주어집니다. 네 번째 줄에는 수열 2의 원소들이 공백을 두고 주어집니다. 1 ≤ n, m ≤ 100,000 −109 ≤ 주어지는 숫자의 범위 ≤ 109 출력 형식 수열 2의 원소의 순서대로 그 원소가 수열 1에 존재하는 원소이면 1을, 수열 1에 존재하지 않는 원소이면 0을 공백을 사이에 두고 출력합니다. 나의 풀이 #include #include using namespace std; int main() { unor..

[코드트리] Hash Set SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. unordered_set STL C++에서는 unordered_set이라는 STL을 이용할 수 있습니다. unordered_set은 HashSet 자료구조로 되어있으며, 이 HashSet이 바로 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. 모든 함수의 시간복잡도는 O(1)입니다. unordered_set은 set보다 속도가 빠르지만, 값의 존재 여부에만 관심이 있지 그 순서에는 전혀 관심이 없는 자료구조입니다. #include 헤더와, unordered_set name; 형태의..

[코드트리] TreeMap 연습문제 문제 n개의 명령이 주어졌을 때, 각 명령을 수행하는 프로그램을 작성해보세요. 명령의 종류는 크게 4가지 입니다. add k v : (k, v) 쌍을 treemap에 추가합니다. key가 k, value가 v라는 뜻입니다. 이때 만약 동일한 k가 이미 존재한다면, v로 덮어씁니다. remove k : key가 k인 쌍을 찾아 treemap에서 제거합니다. 잘못된 입력은 주어지지 않습니다. find k : key가 k인 쌍이 treemap에 있는지를 판단합니다. 있다면 해당하는 value를 출력하고, 없다면 None을 출력합니다. print_list : treemap에 있는 쌍들을 key 기준으로 오름차순 정렬하여 각 value 값들만 공백을 사이에 두고 순서대로 출력합니다. 만약 treemap이 비어있다..

이전 1 2 3 다음

728x90

티스토리툴바