algorithm50

• 

  [이것이 코딩 테스트다 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] 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.

• 

  [이것이 코딩 테스트다 with Python] 22강 삽입 정렬 https://www.youtube.com/watch?v=DRkL5EBZ7KY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=22 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다 삽입 정렬 동작 예시 [Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다 [Step 1] 이어서 '9'가 어떤 위치로 들어갈지 판단한다 [Step 2] 이어서 '0'이 어떤 위치로 들어갈지 판단한다 [Step 3] 이어서 '3'이 어떤.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 21강 선택 정렬 https://www.youtube.com/watch?v=jpyslMwprao&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=21 정렬 알고리즘 정렬(Sorting) 이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다 선택 정렬 동작 예시 정렬할 데이터를 준비한다 [Step 0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다 [Step 1] 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꾼다 [Step 2] 처리되지 않은 데이터 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 20강 DFS & BFS 기초 문제 풀이 https://www.youtube.com/watch?v=e7_H8SLZlHY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=20 음료수 얼려 먹기: 문제 설명 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 음료수 얼려 먹기: 문제 조건 음료수 얼려 먹기: 문제 해결 아이디어 이 문제는 DFS 혹은 BFS로 해결할 수 있다. 일단 앞에서 배운 대.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘 https://www.youtube.com/watch?v=CJiF-muKz30&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=19 BFS (Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다 BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다 [Step 0] 그래프를 준비한다 (방문 기준: 번호가 낮은 인접 노드부터) 시작 노드: 1 [Step 1] 시.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 18강 DFS 알고리즘 https://www.youtube.com/watch?v=1vLqC1rItM8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=18 DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다 DFS 동작 예시 [Step 0] 그래프를 .. CodingTest 2021. 1. 4.

• [이것이 코딩 테스트다 with Python] 17강 재귀 함수 https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17 재귀 함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다 어느정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력된다 def recursive_function(): print('재귀 함수를 호출합니다') recursive_function() recursive_function() 재귀 함수의 종료 조건 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 합니다 종료 조건을 제대로 명시하지.. CodingTest 2021. 1. 4.