자료구조 [백준] 트리의 독립집합 : TreeDP O(2N)의 풀이를 생각할 수 있다. O(N)의 시간복잡도를 생각할 수 있다. O(NlogN) 풀이는 잠시 보류할 수 있다. O(N)풀이를 생각해보자. 모든 경우의 수를 고려하고 그 중에서 최댓값을 골라야 하는 문제이기 때문에 이전에 사용한 기록을 사용하는 알고리즘을 생각할 수 있다. 선택할 수 있는 알고리즘은 Memoization/DP 이다. 그리고 이 문제의 풀이는 트리 상황에서의 DP로... 트리DP백준자료구조알고리즘백준 [Data Structure] 3. Circular List 특징 순환 구조 헤드포인터와 마지막 노드의 pLink가 가리키는 곳이 모두 첫번째 노드 원소가 1개일 경우 첫번째 노드의 pLink는 자기 자신(첫번째 노드)을 가리킴 첫번째 포지션에 노드 추가 시 마지막 노드의 pLink를 수정해줘야 함 첫번째 노드 삭제 시 헤드포인터를 수정해줘야 함 - 원소가 1개일 경우 헤드포인터가 NULL을 가리키도록 함 - 원소가 1개이상일 경우 헤드포인터는 현재 ... 원형연결리스트circularlist자료구조CdatastructureC 최소 공통 조상 LCA O(N)만에 찾는 방법과 O(logN)만에 찾는 방법이 있다. O(logN)만에 찾는 방법을 설명하는 것에 중점을 둔 글이므로 Linear하게 찾는 방법은 간단히 설명하고 넘어가겠다. 1. 두 노드의 깊이를 동일하게 맞춰준다. O(logN)에 찾는 방법을 알아보자. O(logN) 만에 찾는 방법에서도 두 노드의 깊이를 동일하게 맞춰주는 과정을 거친다. O(logN) 만에 깊이를 동일하게 맞출... LCA자료구조알고리즘백준최소공통조상LCA [백준] 문자열 게임2 : 문자열, 슬라이딩 윈도우 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다. 가장 긴 문자열은 문제에서 첫 번째와 마지막 글자가 같아야 한다고 명시가 되어 있다. 사실 가장 짧은 연속 문자열도 마찬가지다. 어떤 문자열에서 알파벳 ‘a’를 3번 포함하는 가장 짧은 문... 백준문자열자료구조알고리즘슬라이딩윈도우문자열 TIL6. 그래프와 그래프 탐색 정점은 여러 개의 자식을 가질 수 있다. 그래프의 간선은 방향성을 가질 수 있고(갖지 않을 수도 있다), 가중치를 가질 수 있다. 트리와는 달리, 사이클을 가질 수 있다. 인접 행렬 (adjacent matrix) 인접 리스트는 다음과 같이 표현한다. 이 표현은 간선 (u, v)를 탐색하기 위해서는 O(n)의 시간이 소요되지만, 모든 노드에 대하여 탐색할 때에는 더 유리할 수 있다. 인접 행... JavaScript자료구조알고리즘JavaScript 7 - 트라이 (trie) 자료구조 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조를 말한다. 트라이는 자동완성, 사전 찾기 등 문자열을 탐색하는 문제에 자주 사용된다. 문자열을 탐색할때 시간복잡도 측면에서 보다 효율적으로 찾을 수 있다. 보통 문자열 탐색은 문자열의 갯수 * 각 문자열의 길이 만큼의 시간복잡도를 가지는데 트라이를 사용하면 찾는 문자열의 길이 즉 O(L) 만큼의 시간복잡도를 가진다. 따라... python자료구조TILTIL (자료구조)대학수업 Matrix Addition, Matrix Multiplication 문제 두 개의 matrix 를 파일 m1.txt, m2.txt 로 입력 받아, matrix addition 을 수행하는 프로그램을 작성하고, 그 결과를 화면에 출력하라. 입력 파일에 사용되는 matrix 들은 첫째줄에 row 와 column 개수, 둘째줄부터 row-major order 로 원소들이 저장되어 있다. Matrix 는 malloc 을 이용하여 입력 파일에 주어진 row 개수ⅹco... CMatrix Addition자료구조Matrix MultiplicationC [C언어] 배열 리스트와 연결 리스트로 스택(Stack) 구현 선형 자료구조 LIFO(Last-In-First-Out, 후입선출) 탑(top): 가장 최근에 스택에 삽입된 자료 자료 삽입 넘침(Overflow) 현상 고려 자료 제거 부족(Underflow) 현상 고려 스택 맨 위 원소(top) 반환 최대 크기 지정 추가한 순서대로 배열에 삽입 👉 top은 currentElementCount -1번째 노드 구조체와 함수 원형 create push pop ... C자료구조C [자료구조] : 최대부분배열 구현하기 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 1) 완전탐색(브루트포스 알고리즘) - 시간복잡도 O(n^3) 데이터의 개수가 n개일 때 for문 하나당 O(n) 시간이 걸린다고 생각하면 편함(for문 안이 상수시간이 걸릴 때) 따라서 3중 반복문이므로 O(n x n x n) = O(n^3) 이다. 특징 : 시간복잡도가 O(n^3) 이기 때문에 데이터... c언어자료구조알고리즘C최대부분배열C [C언어] 원형 연결 리스트(Circular Linked List) 구현 Circular Linked List 마지막 노드가 첫 번째 노드를 가리키는 리스트 순환 구조 데이터를 반복적으로 순회하기 좋음 첫 번째 노드 추가 처음으로 추가하는 노드: 추가되는 노드는 자기 자신을 가리킴 아닌 경우: 마지막 노드는 추가하는 노드를 가리킴 첫 번째 노드가 아닌 경우 앞뒤 연결 첫 번째 노드 제거 노드가 1개인 경우: 헤드 노드가 NULL을 가리킴 아닌 경우: 헤드 노드는 ... C자료구조C [C언어] 연결 리스트로 다항식의 덧셈 구현 단순 연결 리스트(Singly Linked List) 활용 항이 같은 노드의 계수끼리 더한 새 노드를 만들어서 연결 노드 추가 다항식 덧셈 두 다항식을 더한 새로운 리스트를 만들어서 반환 다항식 출력... C자료구조C 10강 자료구조 큐(Queue) 큐는 FIFO ( First In First Out) 규칙의 순차적 자료구조이다. enqueue는 stack의 append에 해당하는 삽입으로 가장바깥에 들어간다. dequeue는 stack의 pop에 해당하는 삭제로 가장 안쪽에 있는것을 없앤다. stack은 말미잘, queue는 동물로 생각하면 편하다. stack은 맨 위만 신경쓰면 됐는데 queue는 가장 안쪽과 바깥쪽, 두개의 인덱스를... 자료구조자료구조 [C언어] 이중 연결 리스트(Doubly Linked List) 구현 Doubly Linked List 앞 노드와 뒤 노드의 주소를 갖는 리스트 장점: 양방향으로 데이터에 접근 가능 단점: 추가 메모리 공간 사용 처음에 헤더 노드는 왼쪽, 오른쪽 모두 자기 자신을 가리킴 이후 헤더는 왼쪽에 마지막 노드, 오른쪽에 첫 번째 노드를 가리킴 1. 새 노드의 왼쪽에 이전 노드 연결 2. 새 노드의 오른쪽에 다음 노드 연결 (현재 포지션에 있는 노드) 3. 이전 노드의... C자료구조C [백준] 오민식의 고민 : 벨만-포드 나는 이 조건을 보고 최단 거리 경로에서 무한한 값을 가지는 경우를 판단하는 알고리즘을 쓸 수 있을 것이라고 판단했다. 1:N의 최단거리, 즉 시작 노드에서 다른 각각의 노드까지 도달 할 때의 최단 거리를 구할 수 있는 알고리즘이다. 음수 사이클이 존재하는 그래프에서 벨만-포드 알고리즘을 사용할 수 있고 그렇지 않은 그래프에서는 다익스트라 알고리즘을 사용한다. 벨만-포드 알고리즘은 모든 간선... ps벨만 포드BFS자료구조알고리즘백준BFS 백준 6549번 히스토그램에서 가장 큰 직사각형 (C++) 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제이다. 이 문제의 포인트는 어떠한 구간에서 최솟값이 넓이를 결정한다는 것과 자신의 index를 기준으로 좌우를 모두 생각해야 한다는 것이다. rans배열은 자신보다 더 큰 index를 가진 수들만 고려한 넓이이고 lans 배열은 자신보다 더 작은 index를 가진 수들만 고려한 넓이이다. 위 정보를 스택에 넣어놓고 자신보다 큰 ind... 스택자료구조알고리즘스택 [자료구조] : 버블정렬(C) 이번 시간에는 버블 정렬에 대해서 알아보겠다. 오름차순으로 배열을 정렬하고자 한다면 왼쪽의 값이 오른쪽의 값보다 작아야 한다. Fist pass를 보면, n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동한다. 이어서 교환을 하면서 pass를 진행한다. 이 작업을 Third pass까지 진행 후에 요소의 정렬이 끝난다. First pass는 n-1회 / Se... c언어자료구조C버블정렬정렬C 스택 - 미로찾기 프로그램 스택 후입선출(LIFO:Last-In First-Out) 가장 최근에 들어온 데이터가 가장 먼저 나감 이를 이용해 미로찾기 알고리즘을 작성할 수 있다! 더블 버퍼링 미로를 출력하는 기존 방식이다. system("cls") 으로 cmd를 통째로 지웠다가 다시 cmd에 미로를 출력하는 기존 방식이다. 200ms마다 cmd를 지웠다가 미로를 출력하는 명령을 반복하는데, 깜빡임이 심한 걸 볼 수 있... 자료구조자료구조 9강 자료구조 스택 활용 - 계산기 2 infix -> postfix 변환 방법 왼쪽괄호 ( 는 우선순위가 가장 낮다. 오른쪽활호 ) 는 우선순위가 가장 높다. 결과값은 리스트 ouststack에 넣고 연산자는 스택 opstack에 넣었다가 oustack으로 옮긴다. 피연산자가 나오면 바로 outstack에 넣고, 연산자가 나오면 opstack에 넣는데 자신보다 우선순위가 높은게 opstack 안에 있다면 pop시키고 push한다... 자료구조자료구조 [알고리즘]퀵 정렬(C) 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다. 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 분할(Divide): 입력 ... c언어자료구조알고리즘C퀵정렬C [백준] 2557. Hello world (feat. Javascript / node.js) 알고리즘 자료구조 공부를 시작해본다. 개발자 유튜버의 조언대로 백준-단계별 학습 12단계까지를 1차 목표로 한다. Hello World!를 출력하시오. 제출 Hello world! 프론트엔드 실력향상을 위해 Javascript 진행하려한다. python 은 print()를 사용하면 된다.... hello world자료구조2557백준초보자2557 [C언어] 연결 리스트로 원형 큐(Circular Queue) 구현 FIFO (First-In-First-Out, 선입선출) 프런트(front): 큐의 제일 앞 리어(rear): 큐의 제일 끝 끝(rear)에 자료 추가 넘침(Overflow) 현상 고려 앞(front)의 자료 삭제 부족(Underflow) 현상 고려 앞(front) 자료 반환 Array list를 이용한 원형 큐 👉 데이터 삭제 시 필요한 연산의 수를 줄이고 남은 데이터 공간을 낭비하지 않기... C자료구조C 재귀함수 호출법 <과제> 🎇<출력화면> 🎊<메인 함수> 🔑<코드+주석>: 📢느낌점 :이번 개인 과제인 재귀함수 (Recursive call) 관련 문제를 풀면서 내가 아직 재귀함수를 통해 능숙하게 프로그램을 만드는 실력이 아님을 깨닫게 되었다. 먼저 이 문제를 풀때 처음에 생각한 것은, 메인 함수에 적혀있는 함수를 어떻게 반복문을 사용하지 않고 재귀함수 호출법으로 함수를 구성하는냐가 제일 중요한 포인트였다. 이는 재... 자료구조자료구조 연결리스트-자료구조 연결리스트를 이야기 하기 전에 배열에 대해 먼저 이야기해보자 우리가 배열을 사용하는 이유는 무엇일까? 배열을 사용하는 이유 2데이터를 저장하기위해서 3데이터를 순차적으로 접근한기 위해서 그렇다 우리가 배열을 사용하는 이유는 데이터를 순차적으로 접근하기 위해서다 이사실을 가진상태로 배열의 동적할당에 대해 이야기해보자 배열의 동적할당은 우리가 기존의 알던 배열의 단점을 많이 상쇄시킨다 데이터의 ... 연결리스트자료구조연결리스트 10. Sorting and Searching Alogorithms 제일 작은 아이템을 제일 위쪽(앞쪽)으로 올리는 방식 ⇒ 제일 작은 아이템과 제일 위쪽의 아이템 swap O(N^2) 정렬되지 않은 부분에 속한 아이템 중 가장 작은 아이템이 위쪽으로 올라가게 됨 O(N^2) 버블 소팅에서는 비정렬 집단에서 가장 작은 아이템을 올리는 구조이지만 Insertion에서는 처음 지정된 아이템을 계속 비교해 가면서 자신의 위치를 찾아주는 구조 O(N^2) root에... 자료구조자료구조 4-1. Stack 생성일: 2021년 10월 1일 오후 6:01 Logical (ADT) level : Stack은 ordered group of homogeneous items. LIFO : "Last in, First out" 가장 나중에 들어온 것이 가장 먼저 나가야한다. template을 사용 할 때는 한파일에 .h와 .cpp (선언과 정의)를 두어야한다. (아니면 linking error발생) 컴파일... 자료구조자료구조 기타 자료 구조 : Linked-list (연결 리스트) '일정한 순서'의 나열 로, 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 물리적 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서, 혹은 배열 원소의 메모리 공간에서 물리적 의미를 의미함. 리스트의 '순서' 개념은 어떤 정의에 의해 결정된 '논리적인 순서'. 1) 포인터를 이용한 방법 다음 원소를 가리키는 위치 정보를 저장하는 공간 을 포... 자료구조알고리즘cpplinked listcpp [C언어] 배열 리스트로 힙(Heap) 구현 부모 노드의 우선순위 ≥ 자식 노드의 우선순위 O(1) 우선순위 큐의 삭제 연산 시 모든 노드를 방문해 우선순위가 높은 것을 기억해 놓고 삭제해야 하기 때문에 시간복잡도가 O(n) O(n)이지만, 힙으로 구현 시 숫자가 클수록 우선순위가 높은 문제: 최대 힙 사용 숫자가 작을수록 우선순위가 높은 문제: 최소 힙 사용 루트 노드의 값: 최댓값 부모 노드의 키 값 ≥ 자식 노드의 키 값 최소 트... C자료구조C 연결리스트-자료구조<3> 하지만 아직까지 연결 리시트의 ADT를 정의하고 정의한 ADT를 구현해보지 않았다 1.자료구조 ADT정의 2.void LInsert(List * plist, LData data) 3.int LFirst(List plist, LData pdata) 4.int LNext(List plist, LData pdata) 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다 5.LData LR... 연결리스트자료구조연결리스트 heap 과 python 'heapq' 모듈 이러한 우선순위 큐는 리스트를 통해 구현 하는 방법과 힙(heap)을 통해 구현하는 방법이 있다. 리스트를 통해 구현하는 방식의 시간 복잡도는 삽입할 때 O(1), 삭제할 때 O(N)이고, 힙을 통해 구현하는 방식의 시간 복잡도는 삽입, 삭제 할 때 모두 O(logN)이다. 힙은 부모 노드와 자식 노드의 값들을 비교하며 우선 순위가 더 높은 노드를 루트 노드가 되게 한다. 힙에는 최소힙(Mi... heap자료구조알고리즘heap 이전 기사 보기
[백준] 트리의 독립집합 : TreeDP O(2N)의 풀이를 생각할 수 있다. O(N)의 시간복잡도를 생각할 수 있다. O(NlogN) 풀이는 잠시 보류할 수 있다. O(N)풀이를 생각해보자. 모든 경우의 수를 고려하고 그 중에서 최댓값을 골라야 하는 문제이기 때문에 이전에 사용한 기록을 사용하는 알고리즘을 생각할 수 있다. 선택할 수 있는 알고리즘은 Memoization/DP 이다. 그리고 이 문제의 풀이는 트리 상황에서의 DP로... 트리DP백준자료구조알고리즘백준 [Data Structure] 3. Circular List 특징 순환 구조 헤드포인터와 마지막 노드의 pLink가 가리키는 곳이 모두 첫번째 노드 원소가 1개일 경우 첫번째 노드의 pLink는 자기 자신(첫번째 노드)을 가리킴 첫번째 포지션에 노드 추가 시 마지막 노드의 pLink를 수정해줘야 함 첫번째 노드 삭제 시 헤드포인터를 수정해줘야 함 - 원소가 1개일 경우 헤드포인터가 NULL을 가리키도록 함 - 원소가 1개이상일 경우 헤드포인터는 현재 ... 원형연결리스트circularlist자료구조CdatastructureC 최소 공통 조상 LCA O(N)만에 찾는 방법과 O(logN)만에 찾는 방법이 있다. O(logN)만에 찾는 방법을 설명하는 것에 중점을 둔 글이므로 Linear하게 찾는 방법은 간단히 설명하고 넘어가겠다. 1. 두 노드의 깊이를 동일하게 맞춰준다. O(logN)에 찾는 방법을 알아보자. O(logN) 만에 찾는 방법에서도 두 노드의 깊이를 동일하게 맞춰주는 과정을 거친다. O(logN) 만에 깊이를 동일하게 맞출... LCA자료구조알고리즘백준최소공통조상LCA [백준] 문자열 게임2 : 문자열, 슬라이딩 윈도우 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다. 가장 긴 문자열은 문제에서 첫 번째와 마지막 글자가 같아야 한다고 명시가 되어 있다. 사실 가장 짧은 연속 문자열도 마찬가지다. 어떤 문자열에서 알파벳 ‘a’를 3번 포함하는 가장 짧은 문... 백준문자열자료구조알고리즘슬라이딩윈도우문자열 TIL6. 그래프와 그래프 탐색 정점은 여러 개의 자식을 가질 수 있다. 그래프의 간선은 방향성을 가질 수 있고(갖지 않을 수도 있다), 가중치를 가질 수 있다. 트리와는 달리, 사이클을 가질 수 있다. 인접 행렬 (adjacent matrix) 인접 리스트는 다음과 같이 표현한다. 이 표현은 간선 (u, v)를 탐색하기 위해서는 O(n)의 시간이 소요되지만, 모든 노드에 대하여 탐색할 때에는 더 유리할 수 있다. 인접 행... JavaScript자료구조알고리즘JavaScript 7 - 트라이 (trie) 자료구조 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조를 말한다. 트라이는 자동완성, 사전 찾기 등 문자열을 탐색하는 문제에 자주 사용된다. 문자열을 탐색할때 시간복잡도 측면에서 보다 효율적으로 찾을 수 있다. 보통 문자열 탐색은 문자열의 갯수 * 각 문자열의 길이 만큼의 시간복잡도를 가지는데 트라이를 사용하면 찾는 문자열의 길이 즉 O(L) 만큼의 시간복잡도를 가진다. 따라... python자료구조TILTIL (자료구조)대학수업 Matrix Addition, Matrix Multiplication 문제 두 개의 matrix 를 파일 m1.txt, m2.txt 로 입력 받아, matrix addition 을 수행하는 프로그램을 작성하고, 그 결과를 화면에 출력하라. 입력 파일에 사용되는 matrix 들은 첫째줄에 row 와 column 개수, 둘째줄부터 row-major order 로 원소들이 저장되어 있다. Matrix 는 malloc 을 이용하여 입력 파일에 주어진 row 개수ⅹco... CMatrix Addition자료구조Matrix MultiplicationC [C언어] 배열 리스트와 연결 리스트로 스택(Stack) 구현 선형 자료구조 LIFO(Last-In-First-Out, 후입선출) 탑(top): 가장 최근에 스택에 삽입된 자료 자료 삽입 넘침(Overflow) 현상 고려 자료 제거 부족(Underflow) 현상 고려 스택 맨 위 원소(top) 반환 최대 크기 지정 추가한 순서대로 배열에 삽입 👉 top은 currentElementCount -1번째 노드 구조체와 함수 원형 create push pop ... C자료구조C [자료구조] : 최대부분배열 구현하기 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 1) 완전탐색(브루트포스 알고리즘) - 시간복잡도 O(n^3) 데이터의 개수가 n개일 때 for문 하나당 O(n) 시간이 걸린다고 생각하면 편함(for문 안이 상수시간이 걸릴 때) 따라서 3중 반복문이므로 O(n x n x n) = O(n^3) 이다. 특징 : 시간복잡도가 O(n^3) 이기 때문에 데이터... c언어자료구조알고리즘C최대부분배열C [C언어] 원형 연결 리스트(Circular Linked List) 구현 Circular Linked List 마지막 노드가 첫 번째 노드를 가리키는 리스트 순환 구조 데이터를 반복적으로 순회하기 좋음 첫 번째 노드 추가 처음으로 추가하는 노드: 추가되는 노드는 자기 자신을 가리킴 아닌 경우: 마지막 노드는 추가하는 노드를 가리킴 첫 번째 노드가 아닌 경우 앞뒤 연결 첫 번째 노드 제거 노드가 1개인 경우: 헤드 노드가 NULL을 가리킴 아닌 경우: 헤드 노드는 ... C자료구조C [C언어] 연결 리스트로 다항식의 덧셈 구현 단순 연결 리스트(Singly Linked List) 활용 항이 같은 노드의 계수끼리 더한 새 노드를 만들어서 연결 노드 추가 다항식 덧셈 두 다항식을 더한 새로운 리스트를 만들어서 반환 다항식 출력... C자료구조C 10강 자료구조 큐(Queue) 큐는 FIFO ( First In First Out) 규칙의 순차적 자료구조이다. enqueue는 stack의 append에 해당하는 삽입으로 가장바깥에 들어간다. dequeue는 stack의 pop에 해당하는 삭제로 가장 안쪽에 있는것을 없앤다. stack은 말미잘, queue는 동물로 생각하면 편하다. stack은 맨 위만 신경쓰면 됐는데 queue는 가장 안쪽과 바깥쪽, 두개의 인덱스를... 자료구조자료구조 [C언어] 이중 연결 리스트(Doubly Linked List) 구현 Doubly Linked List 앞 노드와 뒤 노드의 주소를 갖는 리스트 장점: 양방향으로 데이터에 접근 가능 단점: 추가 메모리 공간 사용 처음에 헤더 노드는 왼쪽, 오른쪽 모두 자기 자신을 가리킴 이후 헤더는 왼쪽에 마지막 노드, 오른쪽에 첫 번째 노드를 가리킴 1. 새 노드의 왼쪽에 이전 노드 연결 2. 새 노드의 오른쪽에 다음 노드 연결 (현재 포지션에 있는 노드) 3. 이전 노드의... C자료구조C [백준] 오민식의 고민 : 벨만-포드 나는 이 조건을 보고 최단 거리 경로에서 무한한 값을 가지는 경우를 판단하는 알고리즘을 쓸 수 있을 것이라고 판단했다. 1:N의 최단거리, 즉 시작 노드에서 다른 각각의 노드까지 도달 할 때의 최단 거리를 구할 수 있는 알고리즘이다. 음수 사이클이 존재하는 그래프에서 벨만-포드 알고리즘을 사용할 수 있고 그렇지 않은 그래프에서는 다익스트라 알고리즘을 사용한다. 벨만-포드 알고리즘은 모든 간선... ps벨만 포드BFS자료구조알고리즘백준BFS 백준 6549번 히스토그램에서 가장 큰 직사각형 (C++) 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제이다. 이 문제의 포인트는 어떠한 구간에서 최솟값이 넓이를 결정한다는 것과 자신의 index를 기준으로 좌우를 모두 생각해야 한다는 것이다. rans배열은 자신보다 더 큰 index를 가진 수들만 고려한 넓이이고 lans 배열은 자신보다 더 작은 index를 가진 수들만 고려한 넓이이다. 위 정보를 스택에 넣어놓고 자신보다 큰 ind... 스택자료구조알고리즘스택 [자료구조] : 버블정렬(C) 이번 시간에는 버블 정렬에 대해서 알아보겠다. 오름차순으로 배열을 정렬하고자 한다면 왼쪽의 값이 오른쪽의 값보다 작아야 한다. Fist pass를 보면, n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동한다. 이어서 교환을 하면서 pass를 진행한다. 이 작업을 Third pass까지 진행 후에 요소의 정렬이 끝난다. First pass는 n-1회 / Se... c언어자료구조C버블정렬정렬C 스택 - 미로찾기 프로그램 스택 후입선출(LIFO:Last-In First-Out) 가장 최근에 들어온 데이터가 가장 먼저 나감 이를 이용해 미로찾기 알고리즘을 작성할 수 있다! 더블 버퍼링 미로를 출력하는 기존 방식이다. system("cls") 으로 cmd를 통째로 지웠다가 다시 cmd에 미로를 출력하는 기존 방식이다. 200ms마다 cmd를 지웠다가 미로를 출력하는 명령을 반복하는데, 깜빡임이 심한 걸 볼 수 있... 자료구조자료구조 9강 자료구조 스택 활용 - 계산기 2 infix -> postfix 변환 방법 왼쪽괄호 ( 는 우선순위가 가장 낮다. 오른쪽활호 ) 는 우선순위가 가장 높다. 결과값은 리스트 ouststack에 넣고 연산자는 스택 opstack에 넣었다가 oustack으로 옮긴다. 피연산자가 나오면 바로 outstack에 넣고, 연산자가 나오면 opstack에 넣는데 자신보다 우선순위가 높은게 opstack 안에 있다면 pop시키고 push한다... 자료구조자료구조 [알고리즘]퀵 정렬(C) 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다. 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 분할(Divide): 입력 ... c언어자료구조알고리즘C퀵정렬C [백준] 2557. Hello world (feat. Javascript / node.js) 알고리즘 자료구조 공부를 시작해본다. 개발자 유튜버의 조언대로 백준-단계별 학습 12단계까지를 1차 목표로 한다. Hello World!를 출력하시오. 제출 Hello world! 프론트엔드 실력향상을 위해 Javascript 진행하려한다. python 은 print()를 사용하면 된다.... hello world자료구조2557백준초보자2557 [C언어] 연결 리스트로 원형 큐(Circular Queue) 구현 FIFO (First-In-First-Out, 선입선출) 프런트(front): 큐의 제일 앞 리어(rear): 큐의 제일 끝 끝(rear)에 자료 추가 넘침(Overflow) 현상 고려 앞(front)의 자료 삭제 부족(Underflow) 현상 고려 앞(front) 자료 반환 Array list를 이용한 원형 큐 👉 데이터 삭제 시 필요한 연산의 수를 줄이고 남은 데이터 공간을 낭비하지 않기... C자료구조C 재귀함수 호출법 <과제> 🎇<출력화면> 🎊<메인 함수> 🔑<코드+주석>: 📢느낌점 :이번 개인 과제인 재귀함수 (Recursive call) 관련 문제를 풀면서 내가 아직 재귀함수를 통해 능숙하게 프로그램을 만드는 실력이 아님을 깨닫게 되었다. 먼저 이 문제를 풀때 처음에 생각한 것은, 메인 함수에 적혀있는 함수를 어떻게 반복문을 사용하지 않고 재귀함수 호출법으로 함수를 구성하는냐가 제일 중요한 포인트였다. 이는 재... 자료구조자료구조 연결리스트-자료구조 연결리스트를 이야기 하기 전에 배열에 대해 먼저 이야기해보자 우리가 배열을 사용하는 이유는 무엇일까? 배열을 사용하는 이유 2데이터를 저장하기위해서 3데이터를 순차적으로 접근한기 위해서 그렇다 우리가 배열을 사용하는 이유는 데이터를 순차적으로 접근하기 위해서다 이사실을 가진상태로 배열의 동적할당에 대해 이야기해보자 배열의 동적할당은 우리가 기존의 알던 배열의 단점을 많이 상쇄시킨다 데이터의 ... 연결리스트자료구조연결리스트 10. Sorting and Searching Alogorithms 제일 작은 아이템을 제일 위쪽(앞쪽)으로 올리는 방식 ⇒ 제일 작은 아이템과 제일 위쪽의 아이템 swap O(N^2) 정렬되지 않은 부분에 속한 아이템 중 가장 작은 아이템이 위쪽으로 올라가게 됨 O(N^2) 버블 소팅에서는 비정렬 집단에서 가장 작은 아이템을 올리는 구조이지만 Insertion에서는 처음 지정된 아이템을 계속 비교해 가면서 자신의 위치를 찾아주는 구조 O(N^2) root에... 자료구조자료구조 4-1. Stack 생성일: 2021년 10월 1일 오후 6:01 Logical (ADT) level : Stack은 ordered group of homogeneous items. LIFO : "Last in, First out" 가장 나중에 들어온 것이 가장 먼저 나가야한다. template을 사용 할 때는 한파일에 .h와 .cpp (선언과 정의)를 두어야한다. (아니면 linking error발생) 컴파일... 자료구조자료구조 기타 자료 구조 : Linked-list (연결 리스트) '일정한 순서'의 나열 로, 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 물리적 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서, 혹은 배열 원소의 메모리 공간에서 물리적 의미를 의미함. 리스트의 '순서' 개념은 어떤 정의에 의해 결정된 '논리적인 순서'. 1) 포인터를 이용한 방법 다음 원소를 가리키는 위치 정보를 저장하는 공간 을 포... 자료구조알고리즘cpplinked listcpp [C언어] 배열 리스트로 힙(Heap) 구현 부모 노드의 우선순위 ≥ 자식 노드의 우선순위 O(1) 우선순위 큐의 삭제 연산 시 모든 노드를 방문해 우선순위가 높은 것을 기억해 놓고 삭제해야 하기 때문에 시간복잡도가 O(n) O(n)이지만, 힙으로 구현 시 숫자가 클수록 우선순위가 높은 문제: 최대 힙 사용 숫자가 작을수록 우선순위가 높은 문제: 최소 힙 사용 루트 노드의 값: 최댓값 부모 노드의 키 값 ≥ 자식 노드의 키 값 최소 트... C자료구조C 연결리스트-자료구조<3> 하지만 아직까지 연결 리시트의 ADT를 정의하고 정의한 ADT를 구현해보지 않았다 1.자료구조 ADT정의 2.void LInsert(List * plist, LData data) 3.int LFirst(List plist, LData pdata) 4.int LNext(List plist, LData pdata) 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다 5.LData LR... 연결리스트자료구조연결리스트 heap 과 python 'heapq' 모듈 이러한 우선순위 큐는 리스트를 통해 구현 하는 방법과 힙(heap)을 통해 구현하는 방법이 있다. 리스트를 통해 구현하는 방식의 시간 복잡도는 삽입할 때 O(1), 삭제할 때 O(N)이고, 힙을 통해 구현하는 방식의 시간 복잡도는 삽입, 삭제 할 때 모두 O(logN)이다. 힙은 부모 노드와 자식 노드의 값들을 비교하며 우선 순위가 더 높은 노드를 루트 노드가 되게 한다. 힙에는 최소힙(Mi... heap자료구조알고리즘heap 이전 기사 보기