분류 전체보기502

• 

  [이것이 코딩 테스트다 with Python] 34강 서로소 집합을 활용한 사이클 판별 https://www.youtube.com/watch?v=Mw8W56qNL8U&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=34 서로소 집합을 활용한 사이클 판별 서로소 집합은 무방항 그래프 내에서의 사이클을 판별할 때 사용할 수 있다 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다 사이클 판별 알고리즘은 다음과 같다 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행한다 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다 서로소 집합을 활용한 사이클 판별: 동작 과정 살펴보기 [초기 단.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 33강 서로소 집합 자료구조 https://www.youtube.com/watch?v=Ha0w2dJa2Nk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=33 기타 그래프 이론 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원한다 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다 여러 개 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 32강 최단 경로 알고리즘 기초 문제 풀이 https://www.youtube.com/watch?v=liuUazQaLuU&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=32 전보: 문제 설명 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘 https://www.youtube.com/watch?v=hw-SvAR3Zqg&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=31 플로이드 워셜 알고리즘 개요 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다 각 단계마다 특정한 노드 𝑘를 거쳐 가는 경우를 확인한다 𝑎에서 𝑏로 가는 최단 거리보다 𝑎에서 𝑘를.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘 https://www.youtube.com/watch?v=F-tkqjUiik0&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=30 다익스트라 최단 경로 알고리즘 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다 현실 세계의 도로(간선).. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 29강 다이나믹 프로그래밍 기초 문제 풀이 https://www.youtube.com/watch?v=tWX6FZwwQMI&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=29 개미 전사: 문제 설명 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다 따라서 개미 전사가 정찰병에 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다 예.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 28강 다이나믹 프로그래밍 개요 https://www.youtube.com/watch?v=rWbjQphRE9A&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=28 다이나믹 프로그래밍 다이나믹 프로그래밍은 동적 계획법이라고도 부른다 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다 다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 27강 이진 탐색 기초 문제 풀이 https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27 떡볶이 떡 만들기: 문제 설명 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다 절단기에 높이(H) 를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 26강 이진 탐색 개요 https://www.youtube.com/watch?v=-Gx0T92-7h8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=26 이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다 이진 탐색 동작 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자 [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거) [Step 2] 시작점:0, 끝점: 3, 중간점: 1 (소수점 이하 제거) [Step 3] 시작점.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 25강 정렬 알고리즘 비교 및 기초 문제 풀이 https://www.youtube.com/watch?v=_kdE7ykab4Q&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=25 정렬 알고리즘 비교하기 앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을 보장하도록 설계되어 있다 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N²) O(N) 아이디어가 매우 간단하다 삽입 정렬 O(N²) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠르다 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠르다 계수 정렬 O(N + K) O(N + K) 데이터의 크기가 한정되어 있.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 24강 계수 정렬 https://www.youtube.com/watch?v=65Ui3RNibRA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=24 계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수가 𝑁, 데이터(양수) 중 최댓값이 𝐾일 때 최악의 경우에도 수행 시간 O(N + K) 를 보장한다 계수 정렬 동작 예시 [Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다 [Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다 [Step 2] 데이터를 하나.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 23강 퀵 정렬 https://www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=23 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다 퀵 정렬 동작 예시 [Step 0] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터.. CodingTest 2021. 1. 4.