안 쓰던 블로그

17408 수열과 쿼리24 최대값의 위치를 구하는 문제 각 구간의 최대값을 저장한 세그먼트 트리를 만들어서 쿼리를 처리해 주기만 하면 된다 업데이트나 트리 값을 바꿀 때 그냥 리턴하지 않고 임시로 값을 저장해 두고 앞쪽 쿼리, 뒷쪽 쿼리 값을 비교해서 최대값을 갱신하는 식으로 구현했다 근데.. 아래 코드에서 5 5 4 3 9 5 1 2 3 5 하면 14가 나와야 하는데 왜 12가 나오는지 알 수가 없다ㅜ 2 4 5 하면 14가 나오는 거 보면 3-9-5부분이 갱신이 안 된 듯한데 아무리 코드를 봐도 왜 저기만 업데이트가 안 되는지 모르겠다.. 너무 안 풀려서 일단 코드 올리고 패스 https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/17408%2..

스택 개념 -스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 -top의 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 구조 -마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)됨. 이런 구조를 후입선출 구조 (LIFO, Last-In-First-Out)라고 한다 –스택에서의 삽입 연산 : push –스택에서의 삭제 연산 : pop 스택의 원소 삽입/삭제 과정

그래프 순회=그래프 탐색: 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 깊이 우선vs너비 우선 깊이 우선 탐색 순회 방법 -시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없을 때, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하는 식 -가장 마지막에 만났던 갈림길 간선의 정점으로 돌아가야 하기 때문에 후입선출 구조 스택을 사용한다 구현 1. visited라는 방문 체크 배열을 전부 false(하나도 방문하지 않은 상태)로 초기화 2. 스택 생성 3. visited[v]=true; 시작하는 첫번째 위치는 방문했다고 표시 4. 스택이 empty가 아닐 때까지, 현재 노드의 인..

그래프 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 그래프 G는 객체를 나타내는 정점(V)와 객체를 연결하는 간선(E)의 집합이다 G=(V,E) 종류 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프 (Vi, Vj)로 표현한다 V정점은 ABCD E간선은 AB, AD, BC, BD ,CD 방향이 없음 방향 그래프 =다이그래프 간선에 방향이 있는 그래프 Vi->Vj를 로 표현한다 는 A->B 는 B->C 완전 그래프 각 정점에서 다른 모든 정점이 연결된, 최대로 많은 간선 수를 가진 그래프 정점이 n개인 무방향 그래프에서 최대 간선 수: n(n-1)/2개 정점이 n개인 방향 그래프에서 최대 간선 수: n(n-1)개 G5의 간선 수: 정점의 개수는 4개고 무방향 그래프이므로 완전 그래..

HEAP 완전 이진 트리에 있는 노드 중에서 특정 노드(키 값이 가장 큰 노드나 가장 작은 노드)를 찾기 위해서 만든 자료구조 최대 힙 max heap 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 (이진 트리: https://foxtrotin.tistory.com/184 ) {부모 노드의 키 값>자식 노드의 키 값} 루트 노드: 키 값이 가장 큰 노드 최소 힙 min heap 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 삽입 원소의 키값} 관계가 성립되지 않으면 서로 자리를 바꾸면서 제 자리를 찾는다 예를 들어 17을 삽입하는 경우 완전 이진 트리의 무게를 맞출 수 있는 곳인 오른쪽 맨 아래 노드에다가 17짜리 노드 추가 값 비교 하면서 17이 있어야 할 자리로 옮긴..

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회) https://foxtrotin.tistory.com/187 자료구조-이진탐색트리 BST https://foxtrotin.tistory.com/190 AVL트리가 왜 필요한가? 이진탐색트리 탐색의 특징 때문에 편향 트리에서 탐색 시간이 비효율적 예를 들어 저번 글의 코드에서 입력값이 이랬다 이런 경우 이쁘게 트리가 완성이 되어서 80을 찾는 데 50->70->80을 지나 3번만 탐색하면 된다 근데 아래 코드와 같은 입력일 경우 #include #include typedef struct node { int key; struct node* left,..

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회) https://foxtrotin.tistory.com/187 이진 탐색 트리 이진 트리를 탐색용 자료구조로 쓰기 위해 원소 크기에 따라 노드 위치를 정의한 트리 -모든 원소는 서로 다른 유일한 키를 갖는다 -왼쪽 서브 트리에 있는 원소의 키는 루트의 키보다 작다 -오른쪽 서브 트리에 있는 원소의 키는 루트의 키보다 크다 -왼쪽/오른쪽 서브 트리도 이진 탐색 트리다 이진 탐색 트리의 탐색 연산 1. 루트에서 시작한다 2. 탐색할 키 값 x과 노드의 키 값을 비교 2-1. (x==루트 노드의 키 값)인 경우: 찾음 2-2. (x루트 노드의 키 값)인..