chap5 Backtracking Algorithm design approach 해가 될 가능성이 있는지 promising을 확인한 수 필요없으면 가지치기 prune을 한다. DFS = 깊이 우선 탐색 DFS는 스택 자료구조 또는 재귀 함수를 이용한다. DFS backtracking 푸는법 Tree 형태로 visualize한다 branch를 제거하는 메커니즘을 설계한다. 조건에 따라 단일 leaf node에 도달하거나 여러개의 leaf node에 도달할 것이다. 이후 조건에 따라 이중에서 하나를 선택한다. DFS 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 ..
[level 2] 타겟 넘버 - 43165 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.3 MB, 시간: 1.50 ms 구분 코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS） 채점결과 Empty 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1..
chap4 Greedy algorithm design pattern =과거 미래에 상관없이 현재 순간에 최선을 고르는 방식. = local optimal 해결책임 , global optimal solution이 아닐 수 있음. greedy 알고리즘의 반복순서 selection step = solution set에 들어갈 현재의 최선을 선택함 feasibility check = 타당한지 확인함(가능한지) solution checking step = 새로운 solution set이 문제를 만족하는 해답인지 확인. global optimal solution을 얻기 위해 local optimal을 선택하는 과정 Minimum spanning Tree 문제 = 최소 비용 신장트리 Select an edge Cyc..
chap3. Dynamic programming(planning) 작은 문제가 반복되는 경우에 작은 문제를 계산하여 한번 계산한 값을 저장하고 검색 후 재사용하는 방식. = recomputing 대신 look up table 만들기. fibonacci number DP의 핵심 스텝 DP는 schedule을 사용하여 문제를 효율적으로 풀지만 메모리를 추가로 사용하고 divide and conquer는 문제를 blindly(무턱대고) 풀며, 스케줄링과 planning이 없다. - 겹치는 계산이 없을 때 쓰면 좋음. Compute binomial coefficient=이항계수 문제 계속 이전 항끼리의 합을 구하는 방식이라 겹치는(over lapping)부분과 반복되는 계산이 많다. basic operation..
chap2. Divide and conquer problem을 subproblem으로 나누어 따로 풀고 합치는 방식. = top→ down approach 3-basic step Divide conquer(solve subP) if necessary combine binary search = sorted input = T(n) = T(n/2) -> time complexity = logn every time complexity recurrence relation Master Theorem 재귀방식에 적용 가능한 time complexity 구하는 법 재귀함수가 몇번 불렸는지(a) 몇 개로 나누어 푸는지(b)를 구하고, 함수 T(n)의 재귀 외의 나머지 함수에 대해서 n^d 형태로 만들어 d를 구한다. 그..
알고리즘 중간범위 알고리즘의 정의, 수학적 귀납법, 알고리즘 효율성의 점근적 분석법 등을 배운다. 그 후 분할정복 divide and conquer, 동적 계획법 dynamic programming, 그리디 방법 greedy approach, 퇴각검색 backtracking, 분지한정 branch and bound 등의 알고리즘 설계 기법을 공부한다. 강의 후반에는 효율적인 알고리즘이 존재하지 않는 문제가 있다는 사실을 배우고 이를 다뤄본다. chap1. algorithm efficiency algorithm = step by step procedure for solving problem 알고리즘은 input을 받아 output을 내보낸다. - 문제에 따라 형태는 다르다. 왜 알고리즘을 공부하냐? pra..
델타 탐색이란 현재 위치를 기준으로 우-하-좌-상 으로 방향 전환이 고정되어 있다는 점을 활용하여 방향 전환 횟수 및 각 방향에서 움직이는 횟수에 대한 규칙을 사용하는 풀이이다. 예시 문제 swexpertacademy : 1954_달팽이 숫자 문제 문제풀이 아이디어 N자리 달팽이 숫자에서 방향 전환은 (2N-1)번 일어난다. 각 방향에서 움직임 횟수는 N ~ N-1 ~ N-1 ~ N-2 ~ N-2 ~ … ~ 2 ~ 2 ~ 1 ~ 1 순으로 발생한다는 것을 알 수 있습니다. dr = (0, 1, 0, -1) dc = (1, 0, -1, 0) for tc in range(1, int(input()) + 1): N = int(input()) snail = [[0] * N for _ in range(N)] r,..
BFS 란? BFS와 DFS의 차이는 어떤 자료구조를 사용하느냐로 너비 우선 탐색인지, 깊이 우선 탐색인지 갈리게 된다. BFS는 Queue 자료구조를 사용하여 들어온 순서대로 나가는 FIFO 원칙에 따라 너비 우선 탐색이 수행된다. 코드 정리 V, E = map(int, input().split()) # Vertex, Edge 갯수 adj_matrix = [[0] * (V + 1) for _ in range(V + 1)] # 인접행렬 기본틀 for _ in range(E): # 간선 갯수만큼 돌면서 연결 정보를 받음 start, end = map(int, input().split()) # 시작점과 끝점 adj_matrix[start][end] = 1 adj_matrix[end][start] = 1 # ..
[level 2] 전력망을 둘로 나누기 - 86971 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.4 MB, 시간: 54.22 ms 구분 코딩테스트 연습 > 완전탐색 채점결과 Empty 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를..
[level 2] 피로도 - 87946 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.2 MB, 시간: 0.09 ms 구분 코딩테스트 연습 > 완전탐색 채점결과 Empty 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나..
