문제 참고 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 이해부터 조금 난해한 문제였다.. 결론은 서류 성적과 면접 성적 중 그 누구와 비교해도 두 성적 모두 낮지만 않으면 된다. 브루트포스와 같이 2중 for문을 통한다면 정말 쉽게 구할 수 있을 줄 알았다. # 시간초과 1 #입력받은 성적을 순회하며 두 성적 모두 떨어진다면 제외 for j in range(len(grade)): for k in range(len(..

문제 참고 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정해진 시간 동안 가장 많이 회의를 진행하는 문제였다. 시작 시간과 끝나는 시간에 대한 정렬을 통하여 비교 기준을 저장해주고 반복문을 통해 비교를 해주었다. 처음엔 정렬을 하지않고 2중 for문을 통하여 기준을 그때그때 바꿔주려고 하였다. # 1931_회의실 배정 # N개의 회의에 대해 회의실 사용표를 만든다. # 각 회의 I에 대해 시작 시간과 끝나는 시간이 있고 회의가 겹치지 않으며 사용할 수 있는 최대 개수 # 회의는 중간에 중단 불가하고 회의의 시작 시간과 끝나는 시간이 같을 수 있다. # 전체..

문제 참고 (https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 문제에 맞게 접근 방법을 우선 찾게 되었고, 시간 초과의 문제를 해결하기 위해 많이 고민하였다. 처음 내가 푼 코드이다. import sys N = int(input()) weight_restric = (map(int, sys.stdin.readline().split())) M = int(input()) weight = map(int, sys.stdin.read..

예전 글에서 완전검색(Exaustive Search) 즉, 브루트 포스에 대해서 알아보았다. 경우의 수를 이용하여 문제를 푸는 것이 아닌 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다. 검색(Search) 탐색 키(search key) : 자료를 구별하여 인식할 수 있는 키 종류 순차 검색(sequential search) 이진 검색(binary search) 해쉬(hash) 순차 검색 (Sequential Search) 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율 1. 정..

완전검색 기법으로 모든 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 어떻게 계산할 수 있을까? 부분 집합의 생성 부분 집합의 수를 우선 구해보자 집합의 원소가 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) 과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것!! 그렇다면 좋은 알고리즘이란 무엇일까? 정확성 : 얼마나 정확하게 동작하는가 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량 : 얼마나 적은 메모리를 사용하는..