본문 바로가기

programming study/Algorithm

 (275)
[동빈나]이코테 2021 강의 몰아보기 (17)(2021.1.21) 본 내용은 해당 강의 토대로 작성 벨만 포드 알고리즘 1. 음수 간선인 포함된 상황에서의 최단 거리 문제 BOJ '타임머신' 문제 : https://www.acmicpc.net/problem/11657 N개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0 인 경우는 타임머신으로 시간을 돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하라. 도시의 개수: N(1
[동빈나]이코테 2021 강의 몰아보기 (16)(2021.1.20) 본 내용은 해당 강의 토대로 작성 자료구조 : 트리(Tree) 가계도와 같은 계층적인 구조를 표현할 때 사용하는 자료 구조 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개 이다. 트리 관련 용어 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드(leaf node): 자식이 없는 노드 크기(size): 트리에 포함된 모든 노드의 개수 깊이(depth): 루트 노드부터의 거리 높이(height): 깊이 중 최댓값 차수(degree): 각 노드의 (자식 방향) 간선 개수 이진 탐색 트리 (Binary Search Tree) 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 부모 노드를 기준으로, 왼..
[동빈나]이코테 2021 강의 몰아보기 (15)(2021.1.18) 본 내용은 해당 강의 토대로 작성 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 1. 우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위에 따라 처리하고 싶을 때 사용 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐 구현 방법 단순히 리스트를 이용하여 구현 힙(Heap)을 이용하여 구현 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 2. 힙(Heap)의 특징 완..
[동빈나]이코테 2021 강의 몰아보기 (14)(2021.1.17) 본 내용은 해당 강의 토대로 작성 개발형 코딩 테스트 정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것을 요구하는 코딩 테스트 유형 일부 기업은 해커톤을 통해 채용을 진행 해커톤(Hackathon) : 단기간에 아이디어를 제품화하는 프로젝트 이벤트 1~2일 진행 분야에 따라 상세 요구사항이 다르다. 모바일 클라이언트 개발 : 안드로이드, iOS 앱 개발 웹 서버 개발 : 스프링(Spring), 장고(Django) 등의 서버 개발 프레임워크 활용 분야에 상관없이 꼭 알아야 하는 개념과 도구는 학습해야 한다. 서버, 클라이언트, JSON, REST, API, … 서버와 클라이언트 클라이언트가 요청(Request)을 보내면 서버가 응답(Response)한다. 웹 클라이언트 웹 서버 PC 워크스테이션..
[동빈나]이코테 2021 강의 몰아보기 (13)(2021.1.16) 본 내용은 해당 강의 토대로 작성 기타 알고리즘 1. 소수 (Prime Number) 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 코딩 테스트에서 어떤 자연수가 소수인지 아닌지를 판별해야 하는 문제 자주 출제 기본적인 알고리즘 # 소수 판별 함수(2 이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어 떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is_prime_number(7)) O(X) 시간 복잡도 약수의 성..
[동빈나]이코테 2021 강의 몰아보기 (12)(2021.1.15) 본 내용은 해당 강의 토대로 작성 기타 그래프 이론 1. 크루스칼 알고리즘 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 한다. 일부 간선만 활용 일부 간선을 사용하지 않아도 모든 노드를 이을 수 있으므로 유용한 경우가 있다. 최소 신장 트리 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치 포함되는 간선의 합이 최소가 되도록 한다. 최종적으로 만들어지는 최소 신장 트리의 포함된 간선 개수는 전체 노드 개수의 -1이다. ..
[동빈나]이코테 2021 강의 몰아보기 (11)(2021.1.14) 본 내용은 해당 강의 토대로 작성 기타 그래프 이론 1. 서로소 집합 서로소 집합(Disjoint Sets) : 공통 원소가 없는 두 집합 서로소 집합 자료 구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료 구조 두 종류의 연산 지원 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지를 알려주는 연산 합치기 찾기(Union Find) 자료 구조라고도 불림 서로소 집합 자료 구조 동작 과정 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 A와 B의 루트 노드 A', B'를 각각 찾는다. A'를 B'의 부모 노드로 설정 모든 합집합(Union) 연산을 처리할 때까지 1..
[동빈나]이코테 2021 강의 몰아보기 (10)(2021.1.12) 본 내용은 해당 강의 토대로 작성 최단 경로 알고리즘 1. 최단 경로 알고리즘 개요 가장 짧은 경로를 찾는 알고리즘 다양한 문제 상황 한 지점 -> 다른 한 지점 한 지점 -> 다른 모든 지점 모든 지점 -> 다른 모든 지점 각 지점은 노드로 표현 지점 간 연결된 도로는 간선으로 표현 2. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘 개요 특정 노드에서 출발하여 다른 모든 노드를 가는 최단 경로 계산 음의 간선이 없을 때 정상적으로 동작 현실 길찾기 문제에서 사용 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 알고리즘 동작 과정 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 ..

티스토리툴바