소파와 바보개의 블로그

그리디 알고리즘 (Greedy Algorithms)?그리디 알고리즘은 항상 그 순간에 할 수 있는 최고의 선택을 하면서 문제를 해결하는 방식입니다. 선택을 되돌리는 것은 없고 최고의 선택만을 하면서 바로 결과를 도출합니다. 그러므로 매우 효과적이기는 합니다. 그러나 항상 모든 문제에 대한 최적의 답을 구해주지는 않습니다. 동전 문제(Coin Problem)그리디 알고리즘을 적용할 수 있는 예시로는 동전의 단위가 주어졌을 때, K원을 만들기 위한 최소 동전 갯수를 찾는 문제가 있습니다. 예를 들어 {1, 5, 10, 20, 50, 100, 200} 단위의 동전을 가지고 540원을 만드는 최소 동전 갯수를 찾는 문제입니다. 이 경우 가능한 큰 동전부터 금액이 모두 차감될 때까지 다 사용해보는 greedy한 ..

[백준/BOJ] 1450 냅색문제 (c++)https://www.acmicpc.net/problem/14502025.02.21 - [Competitive Programming] - 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개dnsldprp.tistory.comN개의 물건을 C만큼의 무게를 담을 수 있는 가방에 넣는 ..

[백준/BOJ] 2295 세 수의 합 (c++)https://www.acmicpc.net/problem/22952025.02.21 - [Competitive Programming] - 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개dnsldprp.tistory.comN개의 자연수가 주어지고 그 중에 3개를 골라서 N개의..

[백준/BOJ] 1044 팀 선발 (c++)https://www.acmicpc.net/problem/10442025.02.21 - [Competitive Programming] - 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개dnsldprp.tistory.comN명의 선수가 있고 각 선수들은 A팀 B팀에 속할 때 팀장..

[백준/BOJ] 9663 N-Queen (c++)https://www.acmicpc.net/problem/96632025.02.21 - [Competitive Programming] - 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개dnsldprp.tistory.com최대 15*15의 체스판에 Queen을 배치하는 경우..

백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개의 Queen을 서로 공격하지 못하도록 배치하는 경우의 수를 찾는 문제가 대표적인 백트래킹 문제입니다. N=4 인 경우를 예시로 들면, Queen을 서로 공격하지 못하게 하려면 같은 row에 존재해서는 안되기 때문에, 백트래킹으로 한개의 row씩 확장해 나갈 수 있습니다. 아래와 같은 형태로 row 마다 queen을 배치후 다음 row로 진행 시키면서 현재 상태가 유효한 상태인지를 확인하다보면 마지막 level에 도달한 경우 queen 들이 서로 공격하지 못하도록 배치된 경우가 됩니다.  2025.02.21 -..

완전 탐색 (Complete Search)?완전 탐색은 어떤 알고리즘 문제라도 해결할 수 있는 일반적인 방법입니다. 이 방법은 가능한 모든 해결책을 만들고 그 문제에서 원하는 최고의 해결책을 선택합니다. 이 방법은 항상 정답을 도출할테니, 문제에 대해 완전 탐색할 시간이 주어진다면 아주 좋은 방법이겠지만 문제를 해결하는데 있어 너무 느리다면 다른 방법들을 사용해야할 것입니다.Subset 만들기완전 탐색문제를 해결하기 위해 N개의 요소에 대하여 가능한 모든 부분집합(subset)을 생성할 필요가 있습니다.예를들면 {A, B, C}의 subset은 {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}입니다. 이는 A, B, C 3가지 요소에 대해 가능한 모든 경우의 수를 도출..

자료 구조(Data Structures)? 메모리에 데이터를 저장하는 방법입니다. 각각의 자료 구조들은 저마다의 장단점을 가지고 있기 때문에 문제를 풀기위해 적절한 자료 구조를 선택하는 것이 중요합니다. C++의 standard 라이브러리에는 중요한 자료 구조들이 내장되어 있어 그 것들을 사용하는 것이 좋습니다.Dynamic Arrays프로그램의 실행 중에 크기가 변할 수 있는 배열입니다. 그 중 C++에서 가장 많이 사용되는 것은 vector 입니다.일반적인 배열과 거의 유사하게 사용할 수 있습니다. vector의 사이즈가 증가하면 새로운 배열이 할당되고 새로운 배열로 요소들을 옮기는 식으로 동작합니다.  그러나 자주 발생하는 작업은 아니고, 평균적인 push_back 의 시간 복잡도는 O(1) 입니다..

[백준/BOJ] 2110 공유기 설치 (c++)https://www.acmicpc.net/problem/21102025.02.18 - [Competitive Programming] - 06. 정렬 (Sorting Theory) - Binary Search 06. 정렬 (Sorting Theory) - Binary SearchBinary Search? 배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생dnsldprp.tistory.com20만개의 집이 주어지고 그 집에 C개의 공유기를 배치해야 합니다. 그런 경우 C개를 잘 설치해서 가장 인접한 두 공유기 사이의 최대 거..

[백준/BOJ] 3649 로봇 프로젝트 (c++)https://www.acmicpc.net/problem/36492025.02.18 - [Competitive Programming] - 06. 정렬 (Sorting Theory) - Binary Search 06. 정렬 (Sorting Theory) - Binary SearchBinary Search? 배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생dnsldprp.tistory.com100만개의 레고 조각이 주어지고, 레고 조각 2개를 사용해서 특정 숫자를 만들 수 있는지를 찾는 문제입니다. 특정 숫자는 최대 20억..