자료구조 [자료구조] Stack : JAVA로 구현하기 JAVA 코드로 구현해보자 1. Stack클래스 생성 T타입을 받는 Stack 클래스 생성 T타입의 data 생성 다음 Node생성, 생성자를 생성한 후, data를 받고 내부 변수에 저장한다. pop메소드 Node 타입의 top 변수를 선언한다. public 필드이고 반환값이 T이고, 메소드명은 pop이다. 만약에 top이 null 이면, 예외처리를 해준다. top.data를 T 타입의 변... stack자료구조stack 알고리즘 선행개념 — 1. 시간복잡도 현재 위치에서 가고 싶은 곳으로 가는 길과 방법을 한 번 떠올려 볼 때, 여러 갈래와 교통편을 선택할 수 있습니다. Ο (Big-O) : 점근적 상한. ‘최악의 경우 n² 정도의 시간복잡도를 갖는다.’ ‘평균적으로 log n 정도의 시간복잡도를 갖는다.’ 👉 코드의 시간복잡도를 계산할 때 우리가 중점적으로 볼 것은 위의 ‘계산할 때 포함되는 요소들’이고, 계산한 결과에 대한 후처리는 ‘규칙’... 알고리즘자료구조알고리즘 [Java] 자료구조 - Stack, Queue, Deque 맨 마지막 위치(top)에서만 요소를 추가,삭제, 꺼내올 수 있다. 제일 늦게 들어간 요소가 제일 먼저 나온다. Last In First Out (LIFO) 구조 Stack 은 직접 클래스를 제공한다. push() : 요소 추가 pop() : 요소 삭제 peek() : 요소 조회 맨 앞(front)에서 요소를 꺼내거나 삭제하고, 맨 뒤(rear)에서 요소를 추가한다. 제일 먼저 들어간 요소가... 자료구조자료구조 [자료구조] Queue구현하기: (JAVA) Queue는 First In First Out으로 FIFO라고 부른다. Queue를 구성하는 함수는 add() : 맨 끝에다가 data를 넣는것 remove() : 맨 앞에서 data를 꺼내는 것 peek() : 맨 앞에 있는 data 보는 것 isEmpty : Queue가 비어있나 확인 하는 것 코드로 구현을 해보자! 1. Queue 클래스 생성 Queue클래스의 data 타입은 T이다. ... queue자료구조queue 4/19 스터디 문제 1번 문제. -> N번째 큰 수 1-1번 문제 풀이 코드 (메모리 초과) 메모리 초과!!! 다른 블로그들을 찾아보니, 힙큐를 사용해서 푸는 것을 추천한다. 1-2번 문제 풀이 코드(정답) 그 다음에 13이 온다. [5, 7, 9, 15, 12, 13][7, 12, 9, 15, 13] 최솟값 5 제거 후 그 다음 최솟값이 앞에 채워짐 힙큐 문제들을 몇 번 더 풀어봐야 할 듯 하다.... 파이썬백준알고리즘자료구조백준 [Java] 자료구조 - Array, List, Map, Set, Stack, Queue 배열 크기만큼의 연속된 메모리 영역이 할당된다. 배열을 출력하면 메모리 상의 배열 주소가 출력된다. 배열의 내용을 출력하려면 Arrays.toString(arr) 메서드를 사용한다. 👍 Array의 장점 여러개의 데이터를 한꺼번에 다룰 수 있다. 첫 번째 위치만 알면 index로 상대적 위치를 빠르게 찾을 수 있다. 👎 Array의 단점 미리 공간을 확보해놓고 써야 한다. List 인터페이스... 자료구조자료구조 [자료구조] 다항식 - ADT, 표현 방법, 다항식 덧셈 알고리즘 ✅다항식(Polynomial) a * x^e e =지수(exponent) p(x) = a1 x^e1 + a2 x^e2 + ... <e, a> : 지수(exponent), 계수(coefficient)의 순서쌍 Polynomial ZeroP() : return p(X)=0 Boolean IsZeroP(p) : if (poly) return FALSE else return TRUE Coeffici... 자료구조자료구조 [자료구조] 배열의 표현 - 1차원배열, 2차원배열, 3차원배열, 다차원배열 ✅ 선언과 정의 선언 메모리 상의 주소가 정해지지 않고 이름만 알려줌 대상의 이름에 대해 대응하는 메모리 상의 주소가 정해지는 것 예시 int a; int x( ); int a = 1; int x( ) { return 0; } 배열 선언 및 정의 ✅ 1차원 배열 배열의 선언 a[n] a : 배열이름 / n : 원소 최대 수 순차사상 : 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현... 자료구조자료구조 Red Black Tree 구현 각 노드는 red or black 노드이다. 모든 리프노드(실제 내부노드가 아니라 nil 노드)는 black 노드이다. 즉, red 노드가 연속해서 나올 수 없다. 하지만, 이러한 이중 탐색 트리는 leaf노드의 레벨이 차이가 날 경우 시간복잡도가 o(n)의 근접할 수 있기 때문에 각 leaf 노드의 레벨을 균일하게 맞춰 주어야한다. (1) case1: 삼촌 노드가 레드노드인 경우 (2) c... RedBlackTree자료구조RedBlackTree [알고리즘] DFS와 백트래킹 backtracking(+ N queen, 부분수열의 합) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 최적화 및 결정 문제의 해법이 됨 DFS 백트래킹의 일종이며, 재귀를 활용함 N*N의 체스판에 queen N개를 놓을 때, 서로 모두 공격 불가능한 상태로 배치하는 경우의 수를 체크하는 문제 - queen은 가로, 세로, 대각선 모두 공격가능! code 재귀방식과 DFS 가지치기를 머릿속에 그리며 알고리즘을 짜는 것이... 알고리즘자료구조알고리즘 [Java] 데드풀도 사랑하는 자료구조 Queue 구현 자바 여러가지 방안을 찾아보면서 꾸역꾸역 구현을 하면 만들기는 했겠지만, 그렇게 구현하는 것 보다 제대로 구현하는게 더 낫겠다 싶어서 풀이를 찾아보게 되었다. 풀이를 보니 Queue를 직접 구현해보고 아는 것이 중요하다고 해서 물론 Queue의 자료구조를 모르는 것도 아니고 구현을 안해본 것도 아니지만, 이전에 Queue를 구현했던 것은 C언어를 통해서 구현한 것이 전부였기 때문에 java를 통해... queueJavaalgorithm자료구조Java 책 리뷰 - 문제 해결력을 높이는 알고리즘과 자료 구조 읽기 전의 상황 내 당시 상황 : BOJ. 주의 : 일단 책 읽기 전에 C / C++을 할 줄 알아야 한다. 책을 읽으면 좋을 사람 / 아직 아닌 사람 / 굳이 읽을 필요 없는 사람 책을 읽으면 좋을 사람 문제풀이를 해보고 싶은 사람 복잡도 계산에 대해 궁금한 사람 백준에서 알고리즘 분류(스택, 큐, DFS 등등)를 보고 뭔 말인지 잘 모르겠는 사람 문제를 풀 때 생각이 아니라 손이 먼저 가... 알고리즘자료구조책 리뷰알고리즘 [About 자료구조] 2.Linked List 0. 배열의 단점. 1. 링크드 리스트란 무엇인가요? Linked List란 선형구조의 형태로 형성되는 node의 집합이라고 한다. 각 노드는 데이터를 담당하는 부분과 다음 node의 주소를 참조하는 부분으로 나누어져있다. Singly Linked List(단일 연결 리스트)는 다음과 같은 형식으로 이루어져있다. 만약 Singly Linked List의 Tail을 찾기위해서는 Head에서 시... linkedlist링크드리스트자료구조linkedlist [SWEA] 1223번: 계산기2 (Java) SWEA(SW Expert Academy) 1223번 계산기2 [D4] 스택을 이용하여 후위표기식을 작성/계산하는 문제 후위표기식 변환 만약 숫자일 경우, 바로 출력(여기에는 후위표기식 문자열carr에 저장)하고 연산자일 경우, 우선순위에 따라 스택에 pop/push. 스택에서 자신보다 낮은 우선순위 연산자가 나올 때까지 계속 pop하여 출력한다. 즉, 자신보다 높거나 같은 우선순위 연산자를... 자료구조자료구조 알고리즘 복잡도 분석 (Big-O) 일반적으로 입력의 개수 𝑛과 시간 복잡도 함수 𝑇(𝑛)의 관계는 상당히 복잡할 수 있다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 Big-O 표기법이라고 한다. 예를들어 알고리즘이 𝑛에 비례하는 수행시간을 가진다고 말하는 대신 해당 알고리즘의 시간 복잡도가 𝑂(n)이라고 한다. 두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 ... 알고리즘시간 복잡도자료구조Big OBig O 프로그래머스 코딩테스트 - 정수 삼각형(Lv3) 계산 방법의 경로를 역추적하면 바로 위에서 오거나, 그 옆에서 오거나 두가지 경우임. 양 끝에 있는 건 예외처리 고고.... 알고리즘자료구조알고리즘 자료구조 01 : 알고리즘 분석 알고리즘 + 데이터 구조 메모리 셀은 순번으로 나열되고, 임의의 수/문자 데이터를 저장 실험적 방법을 통한 실행시간 추정 알고리즘을 구현하는 프로그램을 작성 여러 알고리즘을 비교시 동일한 HW, SW환경 필요 특징 ← 실험적 방법의 한계 해결 원시작업 수 : 5n+3 T(n) : 알고리즘 T에 대한 최악의 실행시간 a : 가장 빠른 원시작업의 실행 시간 b : 가장 느린 원시작업의 실행 시간... 학부자료구조자료구조 자료구조 02 : 재귀 알고리즘 자신을 사용하여 정의된 알고리즘 비재귀적 알고리즘과 대비됨 작동원리 보류된 재귀호출을 위한 변수들에 관련된 저장/복구 → 컴퓨터에 의해 자동적으로 수행 장단점 장점 : 복잡한 문제를 적은 양의 코드로 가독성 좋게 서술 가능 단점 : 컴퓨터 성능부담 재귀 케이스 베이스 케이스 아래 규칙을 따르지 않으면 재귀적으로 문제 해결 불가 베이스 케이스 : 항상 재귀없이 해결가능한 베이스 케이스... 학부자료구조자료구조 Heap(힙) 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선순위가 높은 요소가 먼저 나가는 특징을 가진다. 루트가 가장 큰 값이 되는 최대 힙(Max heap)과 루트가 가장 작은 값이 되는 최소 힙(Min heap)이 있다. 자바스크립트에선 직접 구현해서 사용해야 한다. 힙은 추가,삭제가 핵심 로직이다. 힘 요소 ... heap자료구조heap 자료구조 03 : 기초 데이터 구조(배열, 연결리스트) 끝첨자 : UB 또는 N-1 배열표시(선언) V[LB..UB] LB=0, UB=5인 1차원 배열은 V[5..10]와 같이 선언 베이스 : 배열의 첫 원소 ( e.g. V[5] ) → 어떤 셀 V[k]의 offset = k-LB ( e.g. V[9]의 offset = 9-5 = 4 ) (e.g.) V[0..2, 5..7] 인 2차원 배열의 메모리 할당 상태 V[0,5] V[0,6] V[0,7]... 학부자료구조자료구조 [자료구조] 순환 정의, 종류, 순환함수, 반복과 비교 ✅ 순환(recursion) 정의 정의 하려는 개념 자체를 정의 속에 포함하여 이용 함수의 똑같은 이름을 계속 불러줌으로써 같은 일을 반복하는 것 종류 직접순환 : 함수가 직접 자신을 호출 간접순환 : 다른 제 3의 함수 호출 → 3의 함수가 다시 자신 호출 적용 분할정복(divide and conquer)의 특성을 가진 문제에 적합 복잡한 문제를 작은 문제로 분할하여 해결하는 방법 분할한 ... 자료구조자료구조 4/18 스터디 문제 1번 문제. -> 균형잡힌 세상 1-1번 문제 풀이 코드 (틀림) 1-2번 문제 풀이 코드(정답) 진짜 괜히 다른 곳에서 찾을게 아니라 조건을 어떻게 줬는지를 잘 생각해볼 것 오늘은 여기까지.... 파이썬백준알고리즘자료구조백준 [C] 우선순위 큐(Heap) 및 Heap Sort 구현 Heapify의 Sift Down동작과 Sift Up동작을 재귀함수로 구현함으로써, heapify, heap_push, heap_pop heap sort동작을 간결하고 아름답게 구현할 수 있었다. 참고로 코드는 Max Heap을 구현한 내용이다. Min Heap은 각 heapify 함수에서 크기비교 부호만 반대로 하면 된다. Sift Down 방식 Heapify build_heap 에서 fo... 힙소트heap자료구조Heap Sortpriority queueheapifyHeap Sort [About 자료구조] 1.Array(배열) 1. 배열이 무엇인가요? 배열(Array)이란 같은 데이터 타입을 가지는 변수들을 유한개 모아놓은 집합을 의미한다. 예를 들어 정수형 배열, 문자형 배열등이 있다. 배열 내부에 저장되는 각각의 값을 원소(element)라 하고, 배열 내부에서 원소들을 찾는 주소를 인덱스(index)라고 한다. 2. 배열을 선언하는 방법 배열을 선언할때는 저장하려는 원소의 자료형을 선언하고 대괄호[] 를 붙이... 배열자료구조배열 3/21 스터디 문제 1번 문제. -> 회전하는 큐 테스트 케이스 이해하기 1번 문제 풀이 코드 오늘은 생일이므로 기분은 좋지만, 축하 연락을 많이 받아서 약간 집중이 흐트러졌다..ㅋㅋ 내일은 더 열심히 하는걸로!! ** pop을 사용해서 했을때 시간이 더 올래걸림!! del을 이용해서 풀었더니 성공이다.... 파이썬백준자료구조알고리즘백준 [Python] 힙 자료구조 / heapq 최근에 이것이 취업을 위한 코딩테스트다 with Python에서 2019년도 카카오 그리디 알고리즘 문제를 푸는데 우선순위 큐(heapq) 라이브러리를 몰라서 많이 어려웠던 경험이 있었다. 이번 포스팅에서는 heap 자료구조는 무엇이고, 파이썬의 heapq 모듈을 사용하는 방법에 대해서 알아보려고 한다. 최소 힙(Min Heap): 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 heap... python자료구조python 신장트리와 위상정렬 신장트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 👉 신장 트리가 아닌 부분 그래프를 보면, 1번 노드는 연결되어 있지 않고, 사이클이 존재하기 때문에 신장 트리라고 할 수 없다. 👉 즉, 모든 노드가 서로 연결되어 이동이 가능하도록 만들되, 최소한의 비용으로 전체 신장 트리를 구성하고자 하는 문제 ◾ 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.... 신장트리자료구조알고리즘코딩테스트코테이코테위상정렬신장트리 3/18 스터디문제 1번 문제. -> 프린터 큐 테스트 케이스 이해하기 출력 값이 왜 1, 2, 5..? 1번 문제 풀이 코드 모의 코테 이후로 나의 부족함이 여실 없이 드러났다. 싱숭생숭하고, 문제 푸는데 집중도 못하고, 이해를 더 못하는 기분이 들어서 속상했다.. 엎친데 덮친 격으로 몸은 또 왜 이리 아픈지.. ㅜㅠㅠ 기초문제부터 풀어나가보자는 마음으로 한 문제라도 풀어보고자 했다. 마음을 다잡자. 스프린트... 파이썬백준자료구조알고리즘백준 트라이(Trie) 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 어떤 노드는 word의 원소에 대한 정보를 담고 있는데 이는 해당 노드까지 탐색하게 되면 탐색 과정에서 등장한 알파벳으로 이뤄진 단어가 현재 트라이에 존재한다는 의미를 나타낸다. 시간 복잡... 문자열자료구조알고리즘트라이백준문자열 이전 기사 보기
[자료구조] Stack : JAVA로 구현하기 JAVA 코드로 구현해보자 1. Stack클래스 생성 T타입을 받는 Stack 클래스 생성 T타입의 data 생성 다음 Node생성, 생성자를 생성한 후, data를 받고 내부 변수에 저장한다. pop메소드 Node 타입의 top 변수를 선언한다. public 필드이고 반환값이 T이고, 메소드명은 pop이다. 만약에 top이 null 이면, 예외처리를 해준다. top.data를 T 타입의 변... stack자료구조stack 알고리즘 선행개념 — 1. 시간복잡도 현재 위치에서 가고 싶은 곳으로 가는 길과 방법을 한 번 떠올려 볼 때, 여러 갈래와 교통편을 선택할 수 있습니다. Ο (Big-O) : 점근적 상한. ‘최악의 경우 n² 정도의 시간복잡도를 갖는다.’ ‘평균적으로 log n 정도의 시간복잡도를 갖는다.’ 👉 코드의 시간복잡도를 계산할 때 우리가 중점적으로 볼 것은 위의 ‘계산할 때 포함되는 요소들’이고, 계산한 결과에 대한 후처리는 ‘규칙’... 알고리즘자료구조알고리즘 [Java] 자료구조 - Stack, Queue, Deque 맨 마지막 위치(top)에서만 요소를 추가,삭제, 꺼내올 수 있다. 제일 늦게 들어간 요소가 제일 먼저 나온다. Last In First Out (LIFO) 구조 Stack 은 직접 클래스를 제공한다. push() : 요소 추가 pop() : 요소 삭제 peek() : 요소 조회 맨 앞(front)에서 요소를 꺼내거나 삭제하고, 맨 뒤(rear)에서 요소를 추가한다. 제일 먼저 들어간 요소가... 자료구조자료구조 [자료구조] Queue구현하기: (JAVA) Queue는 First In First Out으로 FIFO라고 부른다. Queue를 구성하는 함수는 add() : 맨 끝에다가 data를 넣는것 remove() : 맨 앞에서 data를 꺼내는 것 peek() : 맨 앞에 있는 data 보는 것 isEmpty : Queue가 비어있나 확인 하는 것 코드로 구현을 해보자! 1. Queue 클래스 생성 Queue클래스의 data 타입은 T이다. ... queue자료구조queue 4/19 스터디 문제 1번 문제. -> N번째 큰 수 1-1번 문제 풀이 코드 (메모리 초과) 메모리 초과!!! 다른 블로그들을 찾아보니, 힙큐를 사용해서 푸는 것을 추천한다. 1-2번 문제 풀이 코드(정답) 그 다음에 13이 온다. [5, 7, 9, 15, 12, 13][7, 12, 9, 15, 13] 최솟값 5 제거 후 그 다음 최솟값이 앞에 채워짐 힙큐 문제들을 몇 번 더 풀어봐야 할 듯 하다.... 파이썬백준알고리즘자료구조백준 [Java] 자료구조 - Array, List, Map, Set, Stack, Queue 배열 크기만큼의 연속된 메모리 영역이 할당된다. 배열을 출력하면 메모리 상의 배열 주소가 출력된다. 배열의 내용을 출력하려면 Arrays.toString(arr) 메서드를 사용한다. 👍 Array의 장점 여러개의 데이터를 한꺼번에 다룰 수 있다. 첫 번째 위치만 알면 index로 상대적 위치를 빠르게 찾을 수 있다. 👎 Array의 단점 미리 공간을 확보해놓고 써야 한다. List 인터페이스... 자료구조자료구조 [자료구조] 다항식 - ADT, 표현 방법, 다항식 덧셈 알고리즘 ✅다항식(Polynomial) a * x^e e =지수(exponent) p(x) = a1 x^e1 + a2 x^e2 + ... <e, a> : 지수(exponent), 계수(coefficient)의 순서쌍 Polynomial ZeroP() : return p(X)=0 Boolean IsZeroP(p) : if (poly) return FALSE else return TRUE Coeffici... 자료구조자료구조 [자료구조] 배열의 표현 - 1차원배열, 2차원배열, 3차원배열, 다차원배열 ✅ 선언과 정의 선언 메모리 상의 주소가 정해지지 않고 이름만 알려줌 대상의 이름에 대해 대응하는 메모리 상의 주소가 정해지는 것 예시 int a; int x( ); int a = 1; int x( ) { return 0; } 배열 선언 및 정의 ✅ 1차원 배열 배열의 선언 a[n] a : 배열이름 / n : 원소 최대 수 순차사상 : 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현... 자료구조자료구조 Red Black Tree 구현 각 노드는 red or black 노드이다. 모든 리프노드(실제 내부노드가 아니라 nil 노드)는 black 노드이다. 즉, red 노드가 연속해서 나올 수 없다. 하지만, 이러한 이중 탐색 트리는 leaf노드의 레벨이 차이가 날 경우 시간복잡도가 o(n)의 근접할 수 있기 때문에 각 leaf 노드의 레벨을 균일하게 맞춰 주어야한다. (1) case1: 삼촌 노드가 레드노드인 경우 (2) c... RedBlackTree자료구조RedBlackTree [알고리즘] DFS와 백트래킹 backtracking(+ N queen, 부분수열의 합) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 최적화 및 결정 문제의 해법이 됨 DFS 백트래킹의 일종이며, 재귀를 활용함 N*N의 체스판에 queen N개를 놓을 때, 서로 모두 공격 불가능한 상태로 배치하는 경우의 수를 체크하는 문제 - queen은 가로, 세로, 대각선 모두 공격가능! code 재귀방식과 DFS 가지치기를 머릿속에 그리며 알고리즘을 짜는 것이... 알고리즘자료구조알고리즘 [Java] 데드풀도 사랑하는 자료구조 Queue 구현 자바 여러가지 방안을 찾아보면서 꾸역꾸역 구현을 하면 만들기는 했겠지만, 그렇게 구현하는 것 보다 제대로 구현하는게 더 낫겠다 싶어서 풀이를 찾아보게 되었다. 풀이를 보니 Queue를 직접 구현해보고 아는 것이 중요하다고 해서 물론 Queue의 자료구조를 모르는 것도 아니고 구현을 안해본 것도 아니지만, 이전에 Queue를 구현했던 것은 C언어를 통해서 구현한 것이 전부였기 때문에 java를 통해... queueJavaalgorithm자료구조Java 책 리뷰 - 문제 해결력을 높이는 알고리즘과 자료 구조 읽기 전의 상황 내 당시 상황 : BOJ. 주의 : 일단 책 읽기 전에 C / C++을 할 줄 알아야 한다. 책을 읽으면 좋을 사람 / 아직 아닌 사람 / 굳이 읽을 필요 없는 사람 책을 읽으면 좋을 사람 문제풀이를 해보고 싶은 사람 복잡도 계산에 대해 궁금한 사람 백준에서 알고리즘 분류(스택, 큐, DFS 등등)를 보고 뭔 말인지 잘 모르겠는 사람 문제를 풀 때 생각이 아니라 손이 먼저 가... 알고리즘자료구조책 리뷰알고리즘 [About 자료구조] 2.Linked List 0. 배열의 단점. 1. 링크드 리스트란 무엇인가요? Linked List란 선형구조의 형태로 형성되는 node의 집합이라고 한다. 각 노드는 데이터를 담당하는 부분과 다음 node의 주소를 참조하는 부분으로 나누어져있다. Singly Linked List(단일 연결 리스트)는 다음과 같은 형식으로 이루어져있다. 만약 Singly Linked List의 Tail을 찾기위해서는 Head에서 시... linkedlist링크드리스트자료구조linkedlist [SWEA] 1223번: 계산기2 (Java) SWEA(SW Expert Academy) 1223번 계산기2 [D4] 스택을 이용하여 후위표기식을 작성/계산하는 문제 후위표기식 변환 만약 숫자일 경우, 바로 출력(여기에는 후위표기식 문자열carr에 저장)하고 연산자일 경우, 우선순위에 따라 스택에 pop/push. 스택에서 자신보다 낮은 우선순위 연산자가 나올 때까지 계속 pop하여 출력한다. 즉, 자신보다 높거나 같은 우선순위 연산자를... 자료구조자료구조 알고리즘 복잡도 분석 (Big-O) 일반적으로 입력의 개수 𝑛과 시간 복잡도 함수 𝑇(𝑛)의 관계는 상당히 복잡할 수 있다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 Big-O 표기법이라고 한다. 예를들어 알고리즘이 𝑛에 비례하는 수행시간을 가진다고 말하는 대신 해당 알고리즘의 시간 복잡도가 𝑂(n)이라고 한다. 두 개의 함수 𝑓(𝑛)과 𝑔(𝑛)이 주어졌을 ... 알고리즘시간 복잡도자료구조Big OBig O 프로그래머스 코딩테스트 - 정수 삼각형(Lv3) 계산 방법의 경로를 역추적하면 바로 위에서 오거나, 그 옆에서 오거나 두가지 경우임. 양 끝에 있는 건 예외처리 고고.... 알고리즘자료구조알고리즘 자료구조 01 : 알고리즘 분석 알고리즘 + 데이터 구조 메모리 셀은 순번으로 나열되고, 임의의 수/문자 데이터를 저장 실험적 방법을 통한 실행시간 추정 알고리즘을 구현하는 프로그램을 작성 여러 알고리즘을 비교시 동일한 HW, SW환경 필요 특징 ← 실험적 방법의 한계 해결 원시작업 수 : 5n+3 T(n) : 알고리즘 T에 대한 최악의 실행시간 a : 가장 빠른 원시작업의 실행 시간 b : 가장 느린 원시작업의 실행 시간... 학부자료구조자료구조 자료구조 02 : 재귀 알고리즘 자신을 사용하여 정의된 알고리즘 비재귀적 알고리즘과 대비됨 작동원리 보류된 재귀호출을 위한 변수들에 관련된 저장/복구 → 컴퓨터에 의해 자동적으로 수행 장단점 장점 : 복잡한 문제를 적은 양의 코드로 가독성 좋게 서술 가능 단점 : 컴퓨터 성능부담 재귀 케이스 베이스 케이스 아래 규칙을 따르지 않으면 재귀적으로 문제 해결 불가 베이스 케이스 : 항상 재귀없이 해결가능한 베이스 케이스... 학부자료구조자료구조 Heap(힙) 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선순위가 높은 요소가 먼저 나가는 특징을 가진다. 루트가 가장 큰 값이 되는 최대 힙(Max heap)과 루트가 가장 작은 값이 되는 최소 힙(Min heap)이 있다. 자바스크립트에선 직접 구현해서 사용해야 한다. 힙은 추가,삭제가 핵심 로직이다. 힘 요소 ... heap자료구조heap 자료구조 03 : 기초 데이터 구조(배열, 연결리스트) 끝첨자 : UB 또는 N-1 배열표시(선언) V[LB..UB] LB=0, UB=5인 1차원 배열은 V[5..10]와 같이 선언 베이스 : 배열의 첫 원소 ( e.g. V[5] ) → 어떤 셀 V[k]의 offset = k-LB ( e.g. V[9]의 offset = 9-5 = 4 ) (e.g.) V[0..2, 5..7] 인 2차원 배열의 메모리 할당 상태 V[0,5] V[0,6] V[0,7]... 학부자료구조자료구조 [자료구조] 순환 정의, 종류, 순환함수, 반복과 비교 ✅ 순환(recursion) 정의 정의 하려는 개념 자체를 정의 속에 포함하여 이용 함수의 똑같은 이름을 계속 불러줌으로써 같은 일을 반복하는 것 종류 직접순환 : 함수가 직접 자신을 호출 간접순환 : 다른 제 3의 함수 호출 → 3의 함수가 다시 자신 호출 적용 분할정복(divide and conquer)의 특성을 가진 문제에 적합 복잡한 문제를 작은 문제로 분할하여 해결하는 방법 분할한 ... 자료구조자료구조 4/18 스터디 문제 1번 문제. -> 균형잡힌 세상 1-1번 문제 풀이 코드 (틀림) 1-2번 문제 풀이 코드(정답) 진짜 괜히 다른 곳에서 찾을게 아니라 조건을 어떻게 줬는지를 잘 생각해볼 것 오늘은 여기까지.... 파이썬백준알고리즘자료구조백준 [C] 우선순위 큐(Heap) 및 Heap Sort 구현 Heapify의 Sift Down동작과 Sift Up동작을 재귀함수로 구현함으로써, heapify, heap_push, heap_pop heap sort동작을 간결하고 아름답게 구현할 수 있었다. 참고로 코드는 Max Heap을 구현한 내용이다. Min Heap은 각 heapify 함수에서 크기비교 부호만 반대로 하면 된다. Sift Down 방식 Heapify build_heap 에서 fo... 힙소트heap자료구조Heap Sortpriority queueheapifyHeap Sort [About 자료구조] 1.Array(배열) 1. 배열이 무엇인가요? 배열(Array)이란 같은 데이터 타입을 가지는 변수들을 유한개 모아놓은 집합을 의미한다. 예를 들어 정수형 배열, 문자형 배열등이 있다. 배열 내부에 저장되는 각각의 값을 원소(element)라 하고, 배열 내부에서 원소들을 찾는 주소를 인덱스(index)라고 한다. 2. 배열을 선언하는 방법 배열을 선언할때는 저장하려는 원소의 자료형을 선언하고 대괄호[] 를 붙이... 배열자료구조배열 3/21 스터디 문제 1번 문제. -> 회전하는 큐 테스트 케이스 이해하기 1번 문제 풀이 코드 오늘은 생일이므로 기분은 좋지만, 축하 연락을 많이 받아서 약간 집중이 흐트러졌다..ㅋㅋ 내일은 더 열심히 하는걸로!! ** pop을 사용해서 했을때 시간이 더 올래걸림!! del을 이용해서 풀었더니 성공이다.... 파이썬백준자료구조알고리즘백준 [Python] 힙 자료구조 / heapq 최근에 이것이 취업을 위한 코딩테스트다 with Python에서 2019년도 카카오 그리디 알고리즘 문제를 푸는데 우선순위 큐(heapq) 라이브러리를 몰라서 많이 어려웠던 경험이 있었다. 이번 포스팅에서는 heap 자료구조는 무엇이고, 파이썬의 heapq 모듈을 사용하는 방법에 대해서 알아보려고 한다. 최소 힙(Min Heap): 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 heap... python자료구조python 신장트리와 위상정렬 신장트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 👉 신장 트리가 아닌 부분 그래프를 보면, 1번 노드는 연결되어 있지 않고, 사이클이 존재하기 때문에 신장 트리라고 할 수 없다. 👉 즉, 모든 노드가 서로 연결되어 이동이 가능하도록 만들되, 최소한의 비용으로 전체 신장 트리를 구성하고자 하는 문제 ◾ 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.... 신장트리자료구조알고리즘코딩테스트코테이코테위상정렬신장트리 3/18 스터디문제 1번 문제. -> 프린터 큐 테스트 케이스 이해하기 출력 값이 왜 1, 2, 5..? 1번 문제 풀이 코드 모의 코테 이후로 나의 부족함이 여실 없이 드러났다. 싱숭생숭하고, 문제 푸는데 집중도 못하고, 이해를 더 못하는 기분이 들어서 속상했다.. 엎친데 덮친 격으로 몸은 또 왜 이리 아픈지.. ㅜㅠㅠ 기초문제부터 풀어나가보자는 마음으로 한 문제라도 풀어보고자 했다. 마음을 다잡자. 스프린트... 파이썬백준자료구조알고리즘백준 트라이(Trie) 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 어떤 노드는 word의 원소에 대한 정보를 담고 있는데 이는 해당 노드까지 탐색하게 되면 탐색 과정에서 등장한 알파벳으로 이뤄진 단어가 현재 트라이에 존재한다는 의미를 나타낸다. 시간 복잡... 문자열자료구조알고리즘트라이백준문자열 이전 기사 보기