분류 전체보기502

• 

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

• 

  [이것이 코딩 테스트다 with Python] 16강 스택과 큐 자료구조 https://www.youtube.com/watch?v=7iLoLcna7Hw&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=16 그래프 탐색 알고리즘: DFS/BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다 DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다 스택 동작 예시 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 삽입(5) - 삽입(2.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 15강 구현 유형 문제 풀이 https://www.youtube.com/watch?v=QhMY4t2xwG0&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=15 시각: 문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다 00시 02분 55초 01시 27분 45초 시각: 문제 조건 시각: 문제 해결 아이디어 이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제이다 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 14강 구현 유형 개요 https://www.youtube.com/watch?v=puH2p1CQEg4&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=14 구현: 시뮬레이션과 완전 탐색 구현(Implementation) 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다 흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다 구현 유형의 예시는 다음과 같다 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 알고리즘 문제에서의 2차원 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 13강 그리디 알고리즘 유형 문제 풀이 https://www.youtube.com/watch?v=_TG0hVYJ6D8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=13 1이 될 때까지: 문제 설명 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다 N에서 1을 뺀다 N을 K로 나눈다 예를 들어 N이 17, K가 4라고 가정하면. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이 후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 12강 그리디 알고리즘 개요 https://www.youtube.com/watch?v=5OYlS2QQMPA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=12 그리디 알고리즘 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 그리디 해법은 그 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토함 [문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶음 Q. 최적의 해는 무엇인가? 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 하지만 코딩 테스트에서 대부분의 그리디 문.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 11강 파이썬 문법: 자주 사용되는 표준 라이브러리 https://www.youtube.com/watch?v=W1SO2e5IaSo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=11 실전에서 유용한 표준 라이브러리 내장 함수: 기본 입출력 함수 부터 정렬 함수까지 기본적인 함수들을 제공 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있음 itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공 특히 순열의 조합 라이브러리는 코딩 테스트에서 자주 사용됨 heapq: 힙(Heap) 자료구조를 제공 일반적으로 우선순위 큐 기능을 구현하기 위해 사용 bisect: 이진 탐색(Binary Search) 기능을 제공 collections: 덱(deque), 카운터(Coun.. CodingTest 2021. 1. 4.