포시코딩

순열(Permutation) 서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것 nPr로 표현되며 공식으로는 아래와 같이 나타낼 수 있다. n! / (n-r)! DFS 트리와 체크리스트를 사용하는 방법이 가장 쉽다. 체크리스트는 말 그대로 내가 어디로 갔었는지를 기억해야 하기 때문에 임시로 사용하는 체크용 리스트 순열 알고리즘 코드는 그냥 외우는걸 추천 구현 코드 n = [1, 2, 3] r = 2 result = [0] * r checklist = [0] * len(n) def DFS(L): if L == r: print(result) else: for i in range(len(n)): if checklist[i] == 0: result[L] = n[i] check..

결과 arr = list(map(int, input().split())) # [1, 2, 3, 4, 5] 급한 사람은 위에꺼 갖다 쓰자 개요 지금껏 프로그래머스에서만 문제를 풀어오다 처음으로 백준 문제를 접하게 됐는데 입력값 받는거부터 난관이었다. python의 경우 input()을 통해 값을 입력받는데 숫자 하나면 몰라도 '1 2 3 4 5' 처럼 문자열로 틱 던져주고 이걸 숫자형 리스트로 활용해야 하는 빡치는 상황이 너무 많았다. 그래서 이걸 애초에 입력 받을 때 어떻게 처리해야 할지 정리해봄 과정 arr = input() # 1 2 3 4 5 받은 그대로 출력하면 문자열 '1 2 3 4 5' 그대로다. arr = input().split() # ['1', '2', '3', '4', '5'] spli..

탐욕 알고리즘이란? 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종적인 값을 구하는 방식 예시 문제 문제 1. 동전 문제 지불해야 하는 값이 4720원일 때 10원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불하는 방법으로 구현 가능 탐욕 알고리즘으로 매 순간 최적이라고 생각되는 경우를 선택 코드 coin_list = [500, 100, 50, 10] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) # 큰..

DFS 알고리즘 구현 스택, 큐 자료구조 활용 need_visit stack visited queue * BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있다. 개념 위 그래프에 대해 DFS를 구현한다면 다음과 같은 순서로 진행된다. 1. 제일 처음 노드 A를 need_visit stack에 추가한다. (시작) 2. need_visit stack에서 pop한 뒤 temp_node로 가져온다. (BFS에서 dequeue하던 것과 대조됨) 3. temp_node가 visited queue에 존재하는지 확인 4-1. 없다면 visited queue에 A를 추가 4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작 5. temp_node였던 A를 graph_dict..

BFS 알고리즘 구현 큐 자료구조 활용 need_visit queue visited queue 개념 위 그래프에 대해 BFS를 구현한다면 다음과 같은 순서로 진행된다. 1. 제일 처음 노드 A를 need_visit queue에 추가한다. (시작) 2. need_visit queue에서 dequeue 한 뒤 temp_node로 가져온다. (코드에선 list를 사용하기 때문에 pop(0)을 통해 dequeue했다.) 3. temp_node가 visited queue에 존재하는지 확인 4-1. 없다면 visited queue에 A를 추가 4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작 5. temp_node였던 A를 graph_dict에서 key로 찾아 나온 value를 need_visit queu..

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search:BFS) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search:DFS) 정점의 자식들을 먼저 탐색하는 방식 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J * 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. DFS 방식: A - B - D - E - F - C - G - H - I - J * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

그래프(Graph)란? 노드(Node)와 간선(Edge)로 이루어진 자료구조. 노드(Node): 위치를 뜻한다. 버텍스(Vertex), 정점이라고도 불림 간선(Edge): 위치 간의 관계를 표시한 선. 노드를 연결한 선으로 링크(link) 또는 브랜치(branch)라고도 한다. 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고용어 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path): 처음 정점과 끝 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(triangle): # 거쳐간 숫자의 합 # 1 A vs B 라고 할 때 # A, B의 x는 1씩 커지고 # A, B의 y는 F[x][y]에 대해 y, y+1 # for x in range(len(triangle)): # c1 += triangle[x][F] # if triangle[x+1][F] # case 2. 4가 시작인 경우 # x는 1씩 작아짐 # y..

자료구조에서 탐색에 대한 알고리즘을 배운 바 있다. 순차 탐색 해시 이진 탐색 트리 여기에 추가로 이진 탐색에 대해 알아보자 이진 탐색 이분 탐색으로도 불리는 이진 탐색은 '업다운 게임'을 떠올리면 이해하기 쉽다. 30개의 정렬된 원소 중 정확히 70이 든 값을 찾으려면 중간을 까서 이하인지 이상인지 확인하는 방식으로 찾아 나아가면 된다. 순차 탐색에 비해 이진 탐색의 찾는 속도가 훨씬 빠른 것을 볼 수 있다. 이진 탐색은 병합 정렬과 더불어 분할 정복 알고리즘(Divide and Conquer)의 대표적인 예이기도 하다. Divide: 리스트를 두 개의 서브 리스트로 나눈다. Conquer: 검색할 숫자 > 중간 값이면 뒷 부분에서, 반대면 앞 부분에서 검색할 숫자를 찾는다. 코드 def binary_..

병합 정렬(Merge Sort) 분할 정복 알고리즘의 기법을 사용하는 정렬 알고리즘 중 하나 (분할 정복 알고리즘의 대표적인 예 중 하나기도 하다.) 데이터를 잘게 쪼개 정렬한다. Memoization을 사용하지 않음 재귀 용법을 활용 사용방법 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 구현 재귀 용법으로 데이터를 나누는 함수, 나눠진 데이터를 병합하는 함수 두 단계를 함수로 만들어 사용 def merge_sort(data): return split(data) def split(data): if len(data) lp and len(right) > rp: if left..