차곡차곡

백트래킹 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다. 해를 찾는 도중에 막히면 해당 상태로 더 탐색하지 않고 돌아가서 해를 찾아나가는 방식이다. 이때 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다. 모든 경우의 수를 체크하지 않게 되므로 시간을 단축할 수 있다. 유사한 알고리즘으로 DFS(깊이 우선 탐색)이 있다. DFS와 백트래킹의 차이는 DFS는 모든 경우의 수를 탐색하지만 백트래킹은 DFS와 다르게 백트래킹은 불필요한 탐색을 하지 않는다. 사용 문제 의사결정 문제 최적화 문제 열거 문제 핵심 아이디어 재귀 호출 : 문제를 해결하..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 시작 단어 begin, 도착 단어 target이 주어지고 변환할 수 있는 단어의 배열 words가 주어진다. 변환할 수 있는 조건은 한번에 한 개의 알파벳만 바꿀 수 있고, words안에 있는 단어로만 변경이 가능하다. 최소 몇단개에 걸쳐 begin의 단어를 target으로 변환 가능한지 Retrun해준다. 만약 변환할 수 없는 경우 0을 Retrun 해준다. 해결법 d..

https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 자연수 n개로 이루어진 집합이 있다. 집합 원소들의 합은 s와 동일하다. 이때 가능한 집합 중 각 원소의 곱이 최대가 되도록 하는 집합을 Return해주어야 한다. 만약 집합이 존재하지 않는 경우에는 [-1]을 Return 한다. 접근법 우선 집합이 존재하지 않는경우는 집합 원소의 수(n)가 원소의 합 (s)보다 크면 집합이 없다. (원소가 자연수이기 때문에 각 원소의 ..

완전 탐색 (Brute Force) 가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과를 가져오는 알고리즘 이다. 해가 존재한다는 가정을 세우고 완전 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘을 생각하지 않고 모든 경우를 단순히 살펴본다고 볼 수 있다. 완전 탐색 알고리즘을 풀 때는 탐색해야할 전체 데이터 개수가 100만개 이하일 때 완전 탐색을 사용해야한다. 완전 탐색 종류 1. 선형 구조를 전체 탐색하는 순차 탐색 2. 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 사용 조건 1. 문제에 대한 해결책이 잘 정의 되어 있어야 한다. - 해결책이 정의되어 있어야 브루트 포스를 사용한 해결책이 올바른 방법인지 확인할 수 있다. 2. 문제를 해..

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 삼각형 모양으로 꼭대기에서 바닥까지 이어지는 경로 중 숫자의 합이 최대가 되는 경우의 합을 Return해준다. 아래칸으로 이동할때 대각선 방향으로 한칸 오른쪽 왼쪽 으로만 이동 가능하다. 접근법 삼각형 꼭대기 한칸 아래에서부터 위에서 내려올 수 있는 경우에 대해 최대 값을 더해준다. 만약 양끝에 있는 경우에는 가능한 값이 하나밖에 없으므로 별..

동적 계획법(Dynamic Progamming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법이다. 각 하위 문제를 먼저 해결하고 저장하기 때문에 같은 하위 문제가 나왔을 경우 저장한 값을 이용하여 간단하게 해결할 수 있다. 이를 통해 계산 횟수를 줄이기 때문에 하위 문제의 수가 기하 급수적으로 증가할 때 유용하다. 사용 용도 최단 경로 문제 행렬의 제곱 문제 최적화 문제 ex) 문제의 숫자 범위가 크고, 경우의 수가 많은 경우 사용 조건 - 아래 두 조건이 만족하는 경우 다이나믹 프로그래밍을 이용하여 문제를 해결하는데 유용하다. 부분 중복(반복) 문제 - 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산되는 문제 최적..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 [출발지,도착지] 형태로 적힌 항공권 정보 List가 주어진다. 출발지는 항상 ICN 공항에서 출발하며 모든 항공권을 사용해야 한다. 이를 만족하는 경로를 Return하고 만약 만족하는 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 Return한다. 접근법 스택에 ICN을 넣어준다. 출발지와 도착지 정보가 담긴 dictionary 배열의 key(출발지) 와 valu..

너비 우선 탐색 (BFS, Breadth First Search) 한 노드에서 시작한 후 시작 노드의 인접한 노드부터 탐색하는 방법이다. 가까운 노드부터 탐색하는 알고리즘 이다. 시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 있는 노드는 마지막에 방문하는 방식이다. 넓게 탐색하는 방식이다. 일반적으로 선입선출 방식인 큐 자료구조를 활용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색이 이루어진다. 특징 여러 갈래중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우에는 DFS는 무한루프에 빠져 종료되지 못하지만, BFS는 동시에 탐색이 진행되기때문에 탐색이 완료될 수 있다. 모든길을 한번씩 탐색하기 때문에..

깊이 우선 탐색 알고리즘 (DFS) 한 루트로 들어가 가장 깊이 들어가서 탐색후 돌아가 다시 다른 루트로 가장 깊이 탐색하는 방식이다. 넓게 탐색하는 것이 아닌 깊이 탐색하는 방식이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용한다. 구현 방법 재귀 호출 스택 배열 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다. 사용 용도 순회를 하는 경우에 많이 사용된다. 백트레킹에 사용된다. 자동 미로 생성에 많이 사용된다. 유향 그래프에서 ..

그래프 이론 알고리즘 정점들과 간선들로 이루어진 집합을 "그래프"라고 한다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 표현한다. 그래프의 종류 트리 : 부모, 자식 계층 구조를 가진다. (특징 : 간선 수 = 노드 수 - 1) 이진트리 : 각 노드의 자식 노드 수가 2개 이하로 구성되어 있는 트리를 의미한다. 정 이진 트리 자식 노드가 0 또는 2개인 이진 트리를 의미 한다. 완전 이진 트리 왼쪽부터 채워져 있는 이진트리, 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있다. 변질 이진 트리 자식 노드가 하나밖에 없는 이진 트리를 의미한다. 포화 이진 트리 모든 노드가 꽉 차 있는 이진 트리를 의미한다. 균형 이진 트리 모든 노드의 왼쪽 ..