알고리즘47

• 

  [이것이 코딩 테스트다 with Python] 41강 개발형 코딩 테스트 youtube.com/watch?v=4u6tndiG7Iw&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=41 개발형 코딩 테스트 정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것을 요구하는 코딩 테스트 유형 일부 기업은 해커톤을 통해 채용을 진행한다 해커톤(Hackathon)이란 단기간에 아이디어를 제품화하는 프로젝트 이벤트이다 대개 1~2일 정도 진행되며 다수의 해커톤이 대회 형식을 빌려 해커톤이 끝나면 만든 프로그램을 시연하고 발표한 다음 채점을 진행한다 개발형 코딩 테스트는 분야에 따라 상세 요구사항이 다를 수 있다 예시 1) 모바일 클라이언트 개발: 안드로이드, iOS 앱 개발 예시 2) 웹 서버 개발: 스프링(Spring), 장고(Django) 등의.. CodingTest 2021. 1. 5.

• 

  [이것이 코딩 테스트다 with Python] 40강 구간 합 빠르게 계산하기 https://www.youtube.com/watch?v=kqyHnoriStk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=40 구간 합 (Interval Sum) 구간 합 문제: 연속적으로 나열된 N개의 수가 있을 떄 특정 구간의 모든 수를 합한 값을 계산하는 문제 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정하자 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90이다 구간 합 빠르게 게산하기: 문제 설명 𝑁개의 정수로 구성된 수열이 있다 𝑀개의 쿼리(Query)정보가 주어진다 각 쿼리는 𝐿𝑒𝑓𝑡와 𝑅𝑖𝑔ℎ𝑡으로 구성된다 각 쿼리에 대하여 [𝐿𝑒𝑓𝑡,𝑅𝑖𝑔ℎ𝑡] 구간에 포함된 데이터들의 합을 출력해야 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 39강 투 포인터 https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=39 투 포인터 (Two Pointers) 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다 흔히 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 간단히 '2번부터 7번까지의 학생'이라고 부르곤 한다 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다 특정한 합을 가지는 부분 연속 수열 찾기: 문제 설명 N개의 자연수로 구성된 수열이 있다 합이 M인 부분 연속 수열의 개수를 구하라 수행 시간 제한은 O(N.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 38강 에라토스테네스의 체 https://www.youtube.com/watch?v=9rLFFKmKzno&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=38 다수의 소수 판별 하나의 수에 대해서 소수인지 아닌지 판별하는 방법을 알아보았다 하지만 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때는 어떻게 할까? 에라토스테네스의 체 알고리즘을 사용할 수 있다 에라토스테네스의 체 알고리즘 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다 2부터 𝑁까지의 모든 자연수를 나열한다 남은 수 중에서 아직 처리하지 않은 가장 작은 수.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 37강 소수 판별 알고리즘 https://www.youtube.com/watch?v=CyINCmJPjfM&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=37 기타 알고리즘 소수 (Prime Number) 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다 6은 1, 2, 3, 6으로 나누어떨어지므로 소수가 아니다 7은 1과 7을 제외하고는 나누어떨어지지 않으므로 소수이다 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다 소수의 판별: 기본적인 알고리즘 (Python) # 소수 판별 함수(2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i.. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 36강 위상 정렬 4https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=36 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (O) 자료구조 → 고급 알고리즘 → 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다 진입차수가 0인 모든 .. CodingTest 2021. 1. 4.

• 

  [이것이 코딩 테스트다 with Python] 35강 크루스칼 알고리즘 https://www.youtube.com/watch?v=Gj7s-Nrt1xE&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=35 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까? 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해 보자 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다 크루스칼 알고리즘 대표적인 최소 신장.. CodingTest 2021. 1. 4.

• 

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