Python (37) 썸네일형 리스트형 DFS 완벽 구현하기 [Python] 1. DFS의 기본 개념 2. 스택/큐를 활용한 DFS 구현하기 3. 재귀함수를 이용한 DFS 구현하기 1. DFS의 기본 개념 (1) 기본개념 DFS란 Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘입니다. 한 번 예시를 들어 보겠습니다. 오른쪽에 보이다 싶이 A부터 J까지 노드가 연결되어 있는 그래프 자료를 볼 수 있습니다. 그래프에서 특정 노드를 찾으려고 할 때, 위에서 부터 찾느냐 혹은 옆에서부터 찾느냐 그 차이가 있겠죠. 위에서 아래로 찾는 방식을 바로 DFS(Depth First Search)라고 부르는 것입니다. BFS(Breadth First Search)는 차후 포스팅에서 다루도록 하겠습니다. 참고로 위에서 아래로 탐색할 때 왼쪽으로 가냐 오른쪽으로.. 그래프의 이해 - 고도 알고리즘을 위한 기초 개념 1. 그래프(Graph)란? 2. 그래프(Graph)의 관련 개념 및 용어 정리 3. 그래프(Graph)의 종류 4. 그래프(Graph)와 트리(Tree)의 구조적 차이점 1. 그래프(Graph)란? (1) 정의 : 실제 사물이나 현상을 정점(Vertex), 노드(Node), 그리고 간선(Edge)으로 표현하기 위해 사용되는 컴퓨터 프로그래밍 개념입니다. 1) 예시 - 집에서 회사로 갈 수 있는 가능한 모든 경로를 그래프로 표현한 것 (출처: www.fun-coding.org) 2. 그래프(Graph)의 관련 개념 및 용어 정리 (1) 노드(Node) : 위치를 말합니다. 원으로 표현되며, 정점(Vertex)라고 표현하기도 합니다. (2) 간선(Edge) : 위치 간 관계를 표시한 선으로, 노드 간 연결.. 프로그래머스 - 해쉬 - 전화번호 목록 1. 문제의 출처 프로그래머스 - 해쉬 - 전화번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 2. 코드 해답 (1) Best 해답 1 2 3 4 5 6 7 8 9 10 11 def solution(phone_book): answer = True phone_book.sort() for prefix, number in zip(phone_book, phone_book[1:]): if number.startswit.. 프로그래머스 - 해쉬 - 완주하지 못 한 선수 1. 문제의 출처 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 2. 문제의 설명 우선 두개의 리스트가 주어집니다. 첫 번째는 참여자 리스트가 있고, 두 번째는 완주자 리스트가 있습니다. 두 리스트 간 길이가 무조건 1이 차이가 난다고 할 때, 누가 과연 완주를 못 했는지 파악하는 문제입니다. 문제의 함정은 동명이인이 있고, 이중 한 명이 완주하지 못 했을 경우 어떻게 이들을 걸러낼 것인가 입니다. 3.. 데이터 구조 5. 트리(Tree) 마스터하기 1. 트리(Tree)의 구조 2. 이진 트리와 이진 탐색 트리 3. 트리의 구현 - 코딩 클래스 높이기 4. 트리 Class의 전체 구현 코드 1. 트리(Tree)의 구조 (1) 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 말합니다. 실제로 이런 트리 데이터 구조는 이진 트리(Binary Tree) 형태로 탐색 알고리즘 구현을 위해 많이 사용됩니다. (2) 트린 관련 용어 총 정리 - 이미지와 함께 보시면 이해가 빨라요!! 1) Node: 트리에서 데이터를 저장하는 기본 요소 2) Root Node: 트리 맨 위에 있는 노드 3) Level: 최상위 노드를 Lvl0으로 했을 때, 하위 Branch로 연결된 노드의 깊이 4) Parent Node: 어떤 노드의 상.. 백준 - 1920번 - 수 찾기 오늘 포스팅에서는 백중 중 1920번 문제 수 찾기를 파이썬으로 풀어보는 시간을 갖도록 한다. 기본적인 문제이니 잘 풀어보길 권장한다. 목차 1. 문제의 출처 - 백준 1920번 2. 백준 1920번 Python 해설 3. 정답 인증 1. 문제의 출처 - 백준 1920번 문제의 출처: 백준 실전 문제 풀이 사이트 이번 문제의 핵심은 내가 원하는 정수가 정말 있는지 판단하는 것이다. 이번 문제의 유형은 탐색과 정렬의 문제라고 보는 것이 맞고, 이것을 어떻게 해결했는지 코딩 테스트 해설을 해보고자 한다. 2. 백준 1920번 Python 해설 이번 문제 풀이의 기본적인 것은 input과 map함수이다. 문제 풀이할 때 핵심적인 것은 for과 if문의 기본적인 제어이다. 1 2 3 4 5 6 7 8 9 10 .. 백준 - 10930번 - SHA 256 1. 문제의 출처 - 백준: SHA-256 문제의 출처로 이동하기 - 백준 SHA (1) SHA-256의 기본 개념 특정 string 값을 받았을 때, 이것을 하나의 key와 value 값을 가진 hash구조로 반환해주는 함수로서, 최대 2256 의 경우수를 반환할 수 있습니다. 이 SHA-256에 관련해서 더 관심이 있으신 분은 아래의 링크를 통해 공부하는 것도 추천드립니다. SHA-256이란? 2. 코드 해답 1 2 3 4 5 6 import hashlib input_data = input() encoded_data = input_data.encode() result = hashlib.sha256(encoded_data).hexdigest() print(result) Colored by Color S.. 탐색 알고리즘 - 이진 탐색 1. 이진 탐색(Binary Search)의 기본 개념 2. 이진 탐색의 손코드 구현 3. 이진 탐색의 코드 구현 4. 문제 풀이 해답 1. 이진 탐색(Binary Search)의 기본 개념 (1) 이진 탐색의 개념 이진 탐색은 쉽게 말해서 원하는 데이터를 찾을 때 "중간을 기준으로 찾는 것"입니다. 중간에 없으면 다시 왼쪽 오른쪽을 나누어서, 거기서 또 중간 지점을 들여다 보는 방법입니다. 그냥 개념적으로 보면 이게 무슨 뻘짓인가 싶기도 하지만, 탐색 문제에서 시공간 복잡도를 굉장히 절약해줄 수 있는 강력한 Tool될 수도 있습니다. (2) 예시를 통한 코테 대비 - 병뚜껑 찾기 - 출처: www.fun-coding.org 잔재미코딩 온라인 강의 사이트입니다 잔재미코딩에서 만든 온라인 강의 리스트를 공.. 이전 1 2 3 4 5 다음
