ComputerScience (25) 썸네일형 리스트형 [알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / 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. 컴퓨터는 어떻게 산술처리를 할까요? 우리는 수식을 한번에 눈으로 훑은 후에, 무엇을 우선적으로 해야하는지 쉽게 알 수 있습니다. 근데 컴퓨터는 수식에서 연산자의 우선순위 파악을 어려워합니다. 또한 순차적으로 처리하기 때문에, 컴퓨터는 괄호, 연산자의 우선순위를 따로 처리하지 않습니다. 그 대신, 왼쪽에서 오른쪽으로 표기된 순서대로 처리를 하면 결과가 올바르게 나오는 후위 표기법을 사용합니다. 중위 표기법 : 연산자를 피연산자의 가운데에 표기하는 방법입니다. 우리가 일반적으로 사용하는 일반적인 식입니다. 원래 연산자는 반드.. [C언어] 연결리스트(linkedList)와 원형 연결리스트! _C로배우는 쉬운 자료구조 C로 배우는 쉬운 자료구조를 참고했습니다. 안녕하세요!! (순차 자료구조와 연결 자료구조의 차이점을 알고 싶다면?) (아래 링크 참고해주세요!!) 2021.08.28 - [자료구조] - [C언어] 2차원, 3차원 배열을 통한 순차 자료구조의 사용 예시(테트리스 블록, 휴대폰 판매량, 선형 list) 삽입, 삭제 연산 이후 '연속적' 성질을 유지하기 위해 데이터의 추가 이동을 해주어야 하는 순차 자료와 달리!! 연결 자료구조란? '동적할당' 필요한 갯수만큼의 (데이터) 노드를 각각 동적 할당 후, 해당 데이터들을 이어주는 방식입니다. 다시 말해서 데이터와 데이터가 연결되어 구현되는 방식이라서, 메모리 사용의 비효율성 문제가 없습니다. 줄줄이 소시지, 또는 화물칸을 실은 기차를 연상할 수 있습니다. 어라? .. [C언어] 2차원, 3차원 배열을 통한 순차 자료구조의 사용 예시(테트리스 블록, 휴대폰 판매량, 선형 list) 순차 자료구조란? 데이터는 다양한 방식으로 저장될 수 있는데, 메모리에 저장된 물리적 위치가 연속적으로 저장된 경우를 순차 자료구조라고 합니다. C에서는 배열을 통해서 순차 자료구조를 표현합니다. 그래서 메모리에 저장된 시작 위치를 알면 특정 자료의 위치를 쉽게 알 수 있다는 장점이 있습니다. 반면에 자료들이 연속적으로 저장되어있어, 특정 자료를 특정 위치에 삽입하거나, 삭제할 경우 특정위치 뒤에있는 자료들을 모두 한칸씩 뒤로 이동해서 자리를 비워주거나, 특정위치에 삭제할 자료 뒤에있는 자료들을 모두 한칸씩 앞 당겨야 한다는 번거로운 단점이 있습니다. 순차 자료구조의 사용 예시 순차 표현의 사용 예시로 첫번째는 테트리스의 블록 표현 방법이 예시가 있습니다. 테트리스 블록 한개를 예로들어서, 이 블록의 표.. 이전 1 2 3 4 다음
