완전검색 기법으로 모든 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 어떻게 계산할 수 있을까? 부분 집합의 생성 부분 집합의 수를 우선 구해보자 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. 예) {1, 2, 3, 4} -> 2 * 2 * 2 * 2 = 16가지 1. 각 원소가 부분집합에 포함되었는지를 loop를 이용하여 확인하고 부분집합을 생성해보자 bit = [0, 0, 0, 0] for i in range(2): bit[0] = i# 0번째 원소 for j in range(2): bit[1] = j..

https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 우리가 흔히 아는 토너먼트에서 서로가 몇 번만에 만나는지를 출력하는 문제이다. 접근 방법 다음 라운드로 진출하는 참가자는 다시 왼쪽부터 1번, 2번.. 순으로 받는다. 즉, (1 2) (3 4) (5 6) (7 8) (9 10) 이렇게 5개의 조가 있을 때 다음 라운드에 받는 번호는 2/2, 4/2, 6/2, 8/4와 같이 변한다. 또한 연속된 수에서 홀수가 작은 수여야만 만날 수 있다. 서로 번호의 차..

저번 글에서는 검색과 순열에 대해서 알아보았다. 이번 시간엔 'Greedy'라고 불리는 최적해를 구하는 방법을 알아보자. 탐욕 최적해를 구하는데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 동작 과정 해 선택 = 선택 절차(Selection Procedure) 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합(Solution Set)에..

앞에서는 배열을 선언하고 그 배열을 정렬하는 방법에 대해서 배웠다. 이번 글에서는 경우의 수를 이용하여 문제 해결을 하는 검색이라는 것에 대해서 배워보자. 완전 검색(Exaustive Search) 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 Brute-force 혹은 generate-and-test 기법이라고도 불림 모든 경우의 수를 테스트한 후, 최종 해법을 도출 일반적으로 경우의 수가 상대적으로 작을 때 유용 특징 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다. 평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확..

알고리즘이라는 말은 많이 들어봤을 것이다. 나도 단순한 흐름이라고만 알고 있었지 이게 왜 필요한 것인지 알아보자! 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 즉, 어떠한 문제를 해결하기 위한 절차 컴퓨터 분야에서 알고리즘을 표현하는 방법을 크게 두 가지이다. 의사 코드(슈도 코드, Pseudocode) 순서도 APS(Algorithm Problem Solving) 과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것!! 그렇다면 좋은 알고리즘이란 무엇일까? 정확성 : 얼마나 정확하게 동작하는가 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량 : 얼마나 적은 메모리를 사용하는..

백준 2292 벌집 접근 방법 벌집 처음엔 1을 둘러싸고 있는 2~7까지의 숫자, 1-> 2 -> 9 -> 22 1,7,13,19와 같이 등차가 6인 등차수열 3 -> 11 -> 25 2, 8, 14와 같이 등차가 6인 등차수열 4 -> 13 -> 28 3, 9, 15와 같이 31 33 3*5와 같이 홀수 번호를 3에 곱한수 5 -> 15 > 31 4, 10, 16 같이 등차가 6인 등차 수열 6 -> 17 -> 34 5, 12, 17 과같이 등차가 5인 등차수열 7 -> 19 -> 37 6, 12, 18과 같이 등차가 6인 등차수열 이렇게 생각했지만 8, 20, 21과 같이 포함되지 못하는 숫자가 발생한다는 것을 알게 되었다. 그림을 자세히 보며 각 층의 숫자들을 써보았고 [1], [2 3 4 5 6 ..