포시코딩

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(numbers, target): # 출력: target이 되는 방법의 수 # 조건: # 2

문제 [자식폴더, 부모폴더]의 폴더구조에 대한 리스트 folders, [파일이름, 파일크기, 속한폴더이름]의 파일 속성에 대한 리스트 files, 확인할 폴더 목록을 담은 리스트 selected, 확인하지 않을 파일 목록을 담은 리스트 excepted 이렇게 네 개의 파라미터가 주어질 때, 확인할 파일들에 대해 [확인해야 할 파일의 크기(단위 제외), 파일 개수] 의 형태로 반환하시오. 단, 파일 크기는 B 단위로 변환되어야 합니다. 예시 1) folders = [['animal', 'root'], ['fruit', 'root']] files = [['cat', '1B', 'animal'], ['dog', '2B', 'animal'], ['apple', '4B', 'fruit']] selected = [..

순열(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..

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..

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(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 * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

DFS란? 자료의 검색, 트리나 그래프를 탐색하는 방법으로 사용되며 한 노드를 시작으로 인접한 다른 노드를 통해 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS의 특징 DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 따라서 공간을 적게쓰지만 최단 경로를 탐색하기가 쉽지 않다. DFS 구현 방법 1. 재귀함수 DFS는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문 또 그 노드를 방문해서 깊이 우선으로 인접한 노드 방문 만약 끝에 도달했다면 리턴 -> 반복.. 반복하다가 갈 수 없게 되면 탈출 -> 재귀 함수를 쓰면 되겠구나 코드로 직접 살펴보자 graph = {..