# 백트래킹 해를 찾는 도중에 '막히면' (해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'No'가 답하는 문제 미로 찾기, n-Queen 문제, 부분 집합의 합 등.. 정의를 보면 앞서 봤던 DFS-깊이 우선 탐색과 비슷한 것 같다. 미로 찾기 예를 통해서 어떤 차이가 있는지 알아보자. 미로 찾기 아래 그림과 같이 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제 이동할 수 있는 방향은 4가지로 제한된다. 내가 지나가는 경로를 스택에 저장해준 후 pop을 이용해 다시 경로를 되돌아 갈 수 있다. # 백트래킹과 깊이우선탐색의..

LIFO 구조의 Stack을 이용하여 계산기를 구현해보자. 여기서의 계산기는 중위 표기법(infix notation) (A+B)를 후위 표기법(postfix notation)(AB+)으로 변경하여 스택을 이용하여 계산한다. 중위 표기식의 후위 표기식 변환 방법 1 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 괄호를 제거한다. 변환 알고리즘 2 (스택 이용) 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지..

1ㄷ1 관계는 선형구조라고 불렀고 1ㄷN의 관계는 트리라고 불렀다. 그럼 N:N의 관계는 어떤 구조일까? 바로 그래프 구조라고 부른다. 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 특히, 그래프와 비슷한 트리와의 큰 차이점은, 순환(Cycle) 할 수 있다는 것 이를 위한 탐색 방법 2가지가 있는데 오늘은 우선 DFS에 대해 알아볼 것이다. 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) 두 방법의 차이 DFS는 탐색을 한 뒤 이전의 정점으로 돌아온다 이것은 백트래킹(Backtracking)이라고 부른다 # DFS - 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 ..

앞에서 보았던 피보나치 수를 재귀 함수로 구하는 프로그램은 "엄청난 중복 호출" 이라는 큰 문제가 존재한다. 이를 해결하기 위해 동적 계획법의 핵심 기술인 memoization에 대해 먼저 알아보자 # memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 글자 그대로 해석하면 '메모리에 넣기 (to put in memorty)'라는 의미 앞서 구했던 fibo(n)의 값을 계산하자 마자 저장하면 O(2^n) 시간을 O(n)으로 줄일 수 있다. 이제 memoization을 활용한 Dynamic Programming에 대해서 알아보자 # DP(Dynamic Programming) 동적 계획 알고리즘은 그리..

문제 참고 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 키와 몸무게가 주어질 때 두 가지 모두 커야 덩치가 크다. 각각 리스트에 넣어준 후 for문을 이용해 모두 큰 경우에만 카운팅을 해주었다. 하지만 문제에서 원하는 결과는 '내가 몇번 째로 크냐'가 아닌 '나보다 큰 사람이 몇명인가' 였다. N = int(input()) height = [] # 키를 담을 리스트 weight = [] # 몸무게를 담을 리스트 cnt = N f..

문제 참고 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. 정..