본문 바로가기

ComputerScience

 (27)
[Swift/Algorithm] 우선순위 큐 개념 정리, 최소 힙 개념 with 라이노님 Heap 코드 리뷰 라이노님 힙 상세 리뷰(안 까먹기 위해..) + 최소 힙 개념 정리 라이노님 힙 구조 struct Heap where T: Comparable { private var heap = [T]() let compare: (T,T) -> Bool var isEmpty: Bool { return heap.isEmpty } init(compare: @escaping (T,T) -> Bool) { self.compare = compare } init() { self.init(compare: T? { guard !heap.isEmpty else { return nil } guard heap.count != 1 else { return heap.removeFirst() } let res = heap.first! heap..
[Algorithm] 그래프의 의미 및 DFS, BFS 탐색 방법 기본 개념 완전 뿌수기!!!! [Algorithm] 그래프의 탐색 DFS, BFS 탐색 그래프란 무엇인가? 그래프의 개념 그래프 표현 방법 DFS란? BFS란? DFS와 BFS 차이 그래프란 무엇인가? 일반적으로 그래프 하면 떠오르는 개념은 통계 수치를 비교할 때 사용되는 히스토그램(histogram), 방정식 같은 이미지를 떠올린다. 알고리즘에서 그래프는 어떤 현상, 사물을 정점으로 표현하고 연관된 정보를 간선을 통해 표현한다. 이 또한 그래프의 개념에 속한다. 다시 말해 정점은 주요한 대상 정보를 나타내고 간선은 정점과 정점(정보와 정보)을(를) 이어주는 관계가 된다. 즉, 데이터가 존재할 때 각 데이터를 연관 지어 시각적으로 표현한 것을 그래프라고 한다. 위 그림은 네트워크와 연관된 이미지이다. 위에서 흰색 점들은 선으로 연결되..
[알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / heap이 뭐야? 다익스트라 최단 경로 알고리즘 정점 한개를 기준으로(=시작 정점) 다른 모든 정점을 도착하는 단일점에서의 최단 경로 알고리즘 방향 그래프, 무방향 그래프 모두 적용 간선의 가중치가 음수면 다익스트라 알고리즘을 사용할 수 없다. 가장 가까운 정점(방문x 정점)을 선택해 추가할 때, 추가된 새로운 정점에 의해 단축되는 경로가 있다면 해당 경로로 최단 경로를 수정하는 알고리즘이다. 집합 또는 vertex방문체크를 하면서 최단 경로를 구할 경우( 원래의 알고리즘 ) 시간복잡도는 O(E + V^2) == O(V^2)이다. 우선순위 큐를 활용할 경우 시간 복잡도는 O(ElogV)이다. Algorithm 1. set distance 2.시작 정점 방문 체크 3. 방문하지 않은 정점 중 시작점과 최소거리인 정점을 찾아..
[알고리즘] LIS 최장 증가 부분 수열 파해치기!! with Swift Todo : LIS 최장 증가 부분 수열 파해치기 LIS개념을 마주한 순간.. LIS(Longest Increasing Subsequence)란? dp를 통해 LIS 길이를 구하는 방법 이분 탐색을 통해 LIS길이를 구하는 방법 이분탐색 또는 dp를 활용한 문제 LIS개념을 마주한 순간.. 관련 문제 = 14002: 가장 긴 증가하는 부분수열4 ( 포스트 ) dynamic programming문제를 한참 공부 했었을 때(지금도 공부중입니다.ㅏ..) 전깃줄 문제를 풀다 LIS라는 개념을 만나게 되었습니다. 당시에 전깃줄 문제를 풀 때 모든 경우의 수를 파악해 가며 완벽히 구현했다고 생각한 코드를 구현했을 때 문제를 풀 수 없었습니다. 그리고 제가 생각한 코드로는 도저히 해결 할 수 없는 반례들이 나타났습니..
[C언어] 점화식과 점근적 분석 방법(반복대치,추정후 증명, 마스터 정리) 쉽게 배우는 알고리즘 책을 참고했습니다. 안녕하세요!! 점화식 점화식이란? 어떤 함수를 자신과 똑같은 함수를 이용해서 나타내는 것입니다. 다시말해 재귀함수의 구조를 갖는 알고리즘만!! 점화식으로 표현할 수 있다 이말입니다. 재귀함수란? F(n) = n * F(n - 1) ; // 팩토리얼 F(n) = F(n - 1) + F(n - 2) ; // 피보나치 수 F(n) = F(n/2) + C ; //데이터를 두가지로 나누는 정렬! 등.. 자기자신을 호출하는 형식을 갖는 것은 재귀함수라고 표현할 수 있습니다. F(n) = n^2 + n + 1 이런 형식은 쉽게 시간 복잡도를 구할 수 있지만, 자기 자신을 갖는 점화식일 경우에는 점화식의 점근적 분석 방법을 통해서 F(n) = F(n-1)+ ...의 형태를 F(..
[c언어/자료구조] 스택과 순차 큐의 특징, 원형 큐의 특징(삽입 삭제시 빅오 표기법) ,일상에서 큐의 사용 순차 Queue 초 1. 선입선출 FIFO 2.지정된 첫번째 원소 마지막 원소를 Front, rear를 통해 지목할 수 있습니다. -> 데이터가 들어올 경우 rear를 증가시킨 후,그 자리에 데이터가 들어갑니다. => 가장 최근에 들어간 데이터가 가장 마지막에 삭제됩니다. 3. 지정된 front, rear위치를 통해서만 삽입(rear)과 삭제(front)가 이루어집니다. 4. 큐에있는 첫 번째 원소의 이전자리는 front가 해당됩니다.(front==-1시작이므로,) 초기상태 : front==rear==-1 공백상태: front==rear 포화상태 : rear= n-1( n =마지막index) 삽입연산시 ++rear; 삭제 연산시 ++front; 삽입연산 해당위치 삭제연산 해당위치 Stack push to..
[C언어/자료구조] Stack. 스택의 의미와 필수 함수, 응용 여러분 안녕하세요. 이번글에서는 Stack은 무엇인가? stack에 쓰이는 함수를 소개하겠습니다. (stack을 활용한 표기식 변환 방법 아래 링크 참고하세요) 2021.09.16 - [자료구조] - [자료구조] 중위표기식 후위표기식 변환 방법(stack의 응용) 1. Stack이란 무엇인가? (같은 자료형)데이터를 차곡 차곡 쌓아올린 형태를 Stack이라고 합니다. ex) 연탄 아궁이에 연탄을 넣는것과 꺼내는 방법과 같은 개념입니다. 연탄을 넣을 입구는 하나 이고, 가장 처음 넣은 연탄은 가장 마지막에 뺄 수 있습니다. 'top'으로 정한 곳에서만 삽입(push), 삭제(pop)가 가능합니다. 그렇게 정의되어있습니다!!!!!(특징입니다 stack의 특징) 위의 원리에 따라 삽입한 순서대로, 그..
[자료구조] 중위표기식과 후위표기식 간 변환방법 완벽하게 부수기 +_+ | stack의 응용 여러분 안녕하세요:) "C로 배우는 쉬운 자료구조" 책을 공부하며, 컴퓨터가 사용하는 연산 방법인 후위 표기법에 대해 공부한 개념, 방법에 알게된 개념들을 정리하려고 합니다. 1.  컴퓨터는 어떻게 산술처리를 할까요? 우리는 수식을 한번에 눈으로 훑은 후에, 무엇을 우선적으로 해야하는지 쉽게 알 수 있습니다. 근데 컴퓨터는 수식에서 연산자의 우선순위 파악을 어려워합니다. 또한 순차적으로 처리하기 때문에, 컴퓨터는 괄호, 연산자의 우선순위를 따로 처리하지 않습니다. 그 대신, 왼쪽에서 오른쪽으로 표기된 순서대로 처리를 하면 결과가 올바르게 나오는 후위 표기법을 사용합니다. 중위 표기법 : 연산자를 피연산자의 가운데에 표기하는 방법입니다. 우리가 일반적으로 사용하는 일반적인 식입니다. 원래 연산자는 반드..

티스토리툴바