PS (25) 썸네일형 리스트형 백준 1874번: 스택 수열 C++ code https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 처음에 input, output 값을 보고 문제에서 제시한 스택을 이용해서 풀기보다는 오류 상황을 처리하기 위해 복잡한 규칙을 적용한 알고리즘을 만들었다. 그 결과 가독성도 떨어지고 이해하기 알고리즘이 탄생했고 평가를 통과할 수 없었다. 다음으로 작성한 알고리즘은 스택을 이용한 알고리즘인데, 문제 입력 배열을 arr.. 자료구조 Hash 정의 해시 테이블은 연관배열 구조를 이용하여 key에 value를 저장하는 자료구조 이 다. 특징 data의 검색과 저장이 빠르다. O(1) 암호화에 사용된다. 입력받은 데이터를 다른 형태로 변환한다. 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. ->해시 테이블은 기본적으로 많은 공간(메모리)를 이용해 시간을 단축시킨 원리이다. 해시함수 데이터의 value 값을 배열의 인덱스 정수로 변환하는 과정이 필요하고 이때 해시함수를 이용한다. 해시함수는 임의의 크기를 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. key -> mapping(hashing) -> hash value 1) 나눗셈법 해시함수 중에서 가장 간단한 알고리즘에 속한다. 입력 값을 테이블의 크기.. Sorting Method 기본정렬(오름차순)의 몇가지 방법에 대해서 알아보자 코드는 C로 작성하였고 main함수는 다음과 같다. 0. main function 요소의 갯수를 입력받아 calloc함수를 통해 동적으로 배열을 할당하였다. calloc앞에 (int*)형 변환을 하면 더 명시적이지만 없어도 상관은 없다. #define SWAP(a, b, type) do { \ type temp; \ temp = a; \ a = b; \ b = temp; \ } while (0) swap함수를 매크로 설정 해놓는다. do while구문을 통해 매크로 안에서 변수를 선언할 수 있도록 했다. 1. Bubble sorting 개선된 형태의 bubble sorting 인덱스 K앞의 배열은 정렬이 완료 되었다. 가장 기본적인 형태의 bubble .. 백준 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 이전 1 2 3 4 다음 목록 더보기
