전체 글 (134) 썸네일형 리스트형 백준 15649번 N과 M(1) C++ code 가장 기본적인 back-tracking 문제이다. n-queen problem의 축소판이라고 생각해도 될 듯 반복문 안에 재귀형태가 들어있는 구조라 처음 코드를 접했을 때 이해하기 어려운 부분이 많았다. 그래서 직접 값을 대입해보면서 어떻게 흘러가는지 파악하였다. (재귀호출 부분에 함수의 코드를 통채로 치환시켜서 이해해봐도 될 듯) 스택(재귀)를 이용하여 모든 경우를 탐색한다는 점에서 dfs와 일맥상통하는 부분도 있다. 디테일한 조건은 check와 다른 변수를 통해 설정 사이클 범위를 잘 파악하여 돌아왔을 때 해제해줘야 하는 값이 있는지 확인하자. iterator삭제 연산에서 재정의 또는 이번 코드의 check배열 등. while문으로 구성하려 해보았으나, check해제하는 게 힘들더라. 자료구조 List 배열은 인덱스를 통해 직접 접근할 수 있다는 장점이 있지만, 배열의 데이터를 삭제했을 때 빈 공간으로 남아 메모리가 낭비될 수 있다. 리스트는 배열이 가지고 있는 인덱스라는 장점대신 메모리 효율을 취한 자료구조이다. 리스트의 특징 데이터가 선형적으로 연결된 sequence 구조 리스트의 종류 단순 연결 리스트(Simple List) 이중 연결 리스트(Doubly List) 환형 연결 리스트(Circular List) C++ STL list 이중연결리스트이다. 벡터에 비해 순회시간이 길다는 것이 단점. 단일연결리스트를 사용하고 싶다면 forward lis를 사용하자 자료구조 Graph 그래프의 정의 노드와 그 노드를 연결하는 간선으로 이루어진 자료구조 ;연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 그래프의 종류 (1)방향에 따른 분류 무방향 그래프(undirected Graph) 무방향 그래프의 간선은 연결 된 노드간 양 방향으로 이동 가능하다 정점 A와 정점 B를 연결하는 간선은 (A, B)로 표현한다. 방향 그래프(Directed Graph) 간선에 방향성이 존재하는 그래프 두 개의 정점 A->B로 가는 간선을 로 표현한다. (2)가중치 그래프 간선에 비용이나 가중치가 할당된 그래프 네트워크라고도 한다. 그 외에도 비연결 여부, 사이클 존재 여부로 구분 가능하다. 그래프의 구현 (1)인접 행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다... 자료구조 Heap Heap이란? heap은 완전이진트리 기반의 자료구조이다. 다음 두가지로 나뉜다. max heap: 자식 노드 C의 key 값이 부모 노드 P의 key값 보다 작거나 같아야 한다. min heap: 자식 노드 C의 key 값이 부모 노드 P의 key값 보다 크거나 같아야 한다. 힙의 응용 반복적으로 우선순위에 있는 값들을 제거해야할 때 유용하다. 우선순위 큐 힙정렬 다익스트라 prims 최소신장 트리 (1)우선순위 큐(Priority Queue, C++ STL) (2)힙정렬(Heap sort) 자료구조 Trie trie란? trie 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 목적 정수형 자료에 대해 이진검색트리를 하면 O(log N)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 L이라면 O(LlogN)의 시간 복잡도를 가지게 될 것이다. 하지만 트라이를 사용하면 O(L)의 시간만에 원하는 문자열을 검색할 수 있다. 시간복잡도 가장 긴 문자열의 길이를 L, 총 문자열의 수를 N이라고 할 때 시간 복잡도는 다음과 같다 생성시: O(N*L) 삽입, 탐색시: O(L) 직접 구현 백준 5052 https://twpower.github.io/187-trie-concept-and-basic-problem 자료구조 Tree 트리(Tree)의 개념: 트리란 비선형 구조(계층적 or 망)로 노드와 가지로 연결된 그래프의 특수현 형태로 계층 구조를 가진다.중요한건 사이클이 존재해서는 안된다는 것 트리의 기본 용어-루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.-단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.-내부(internal) 노드: 단말 노드가 아닌 노드-간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)-형제(sibling): 같은 부모를 가지는 노드-노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수-노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수-노드의 레.. 이전 1 ··· 14 15 16 17 다음
