일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- Articulation_Point
- data_structure
- '0'
- 구현
- 백준
- list
- 문법
- 5397
- Pair
- qsort
- connected_component
- c++
- 자료구조
- singly Linked List
- Biconnected_Component
- 알고리즘
- sstream
- template
- Heap
- red-black tree
- Algorithm
- 예제
- 13305
- sort
- STL
- 총정리
- Critical_Path_Analysis
- deletion
- function_template
- class_template
- Today
- Total
- Today
- Total
- 방명록
목록분류 전체보기 (85)
어제의 나보다 성장한 오늘의 나
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/pqrbL/btrH3SlcWEo/4KVAJiHZW9vtvRTUbPcXrk/img.png)
백준 10828 문제 자료 구조 Stack 구현 Stack Class를 직접 구현하여 사용하였다. Code // BaekJun 10828 // Title : Stack // URL : https://www.acmicpc.net/problem/10828 /* 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cTXp6t/btrH75EwTDH/63uZHkg2vvErI3LV4NN8Z0/img.png)
백준 5397 문제 시간 제한은 1초 문자열의 길이는 최대 100만 시간 복잡도 O(N^2) 으로는 풀 수 없고 시간 복잡도 O(nlogn) or O(N) 으로 풀어야 한다. Linear 만에 풀기 위해 list + iterator를 사용하였다. Code // BaekJoon 5397 // Title : 키로거 // URL : https://www.acmicpc.net/problem/5397 /* 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/co1ac0/btrH1CwUpfO/IWhC4KYyLufNFkaZNpXB3K/img.png)
오늘은 C 와 C++에서 사용되는 Malloc 의 구현 방식인 Implicit allocator에 대해서 공부해 보려고 한다. 그 전에 사전 지식을 조금 먼저 이야기를 해보겠다. Dynamic Memory Allocation 이란?? @ 프로그램이 작동하는 도중 (런타임 동안) 필요한 메모리를 할당 받고자 할 때 사용 하는 할당 방법 @ 프로세스의 Heap 공간에 저장 -> 단편화(Fragmentation) 문제 발생 가능 @ 단편화 문제를 해결하고 효과적으로 메모리들을 저장하기 위한 Dynamic allocator로 Explicit Allocator , Implicit Allocator 등 이 존재한다. 사용 이유 : 효율적인 메모리 관리 Block 이란? 메모리를 관리하는 단위 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bnKdzI/btrH32OFPcm/8GAYlSE9jKbSyeOJufOZgk/img.png)
오늘은 C 와 C++에서 사용되는 Malloc 의 구현 방식인 Explicit allocator에 대해서 공부해 보려고 한다. 그 전에 사전 지식을 조금 먼저 이야기를 해보겠다. Dynamic Memory Allocation 이란?? @ 프로그램이 작동하는 도중 (런타임 동안) 필요한 메모리를 할당 받고자 할 때 사용 하는 할당 방법 @ 프로세스의 Heap 공간에 저장 -> 단편화(Fragmentation) 문제 발생 가능 @ 단편화 문제를 해결하고 효과적으로 메모리들을 저장하기 위한 Dynamic allocator로 Explicit Allocator , Implicit Allocator 등 이 존재한다. 사용 이유 : 효율적인 메모리 관리 Block 이란? 메모리를 관리하는 단위 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bjp6jN/btrH09t0NOV/QKnt5U0XsZ1DJ69DKQliU0/img.jpg)
Trie ◎ 문자열들을 저장하기 위해 사용되는 트리 자료구조 ◎ 각 노드가 26개의 자식 포인터를 가짐 ◎ 빠른 문자열 탐색 속도 1) 작동 원리 문자열들이 저장되어 있는 Trie 의 모습이다. 저장된 문자열 [ rebro , replay , hi , high , algo ] 문자열 한 글자씩 노드에 저장 해두었고 끝나는 지점을 bool finish 변수를 통해 표시 해두었다. ( 빨간색 동그라미 부분 -> finish 변수 true) 문자열 탐색하는 과정 문자열 "High" 를 찾는 다고 가정을 해보겠다. 제일 꼭대기에 있는 Root 노드 에서 High의 첫 글자인 H를 먼저 찾는다. 자식 노드 들 중 H 노드가 존재하기에 H 노드로 이동 할 수 있다. 이동한 뒤 두 번째 글자인 I 를 찾는다. I 노..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/m1vDf/btrH1a7LfU4/nTEen9HBVAsYvnJz6U9at1/img.png)
Map STL 구현 우리는 Map STL을 코딩하면서 정말 많이 사용한다. Pair로 저장할 수 있고 , 자동으로 정렬이 되고 , 삽입 / 삭제가 빠르고, … 장점이 되게 많기 때문이다. 오늘은 Map STL을 C++로 구현 해보고 Map에서 사용 된 기능 , 그 구조에 대해서 알아볼 것이다. 한 마디로 Map STL을 완전 뜯어 볼 생각이다. 많은 공부가 될 것이다. Map STL 구현 Full Code Github 주소 : https://github.com/ohinhyuk/MCNL-Study/blob/main/%EA%B3%A0%EC%9C%A4%EB%AF%BC%EA%B5%90%EC%88%98%EB%8B%98%20%EC%8A%A4%ED%84%B0%EB%94%94/week%202/RedBlack%20Tre..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/HNdCu/btrGitGORAG/jZfhk7FfQTvUxKTSECLmH0/img.png)
Union - Find 알고리듬을 사용하면 쉽게 해결할 수 있는 문제이다. 다만 이 문제는 시간 초과가 발생하기 때문에 시간을 줄이기 위해 코드를 완성도 있게 짤 필요가 있다. 문제 알고리듬 ① 0 a b 형태로 주어진 경우 union을 통해 집합을 합쳐 주면 된다. ② 1 a b 형태로 주어진 경우 a , b의 find 값이 같다면 YES 출력 다르다면 NO 출력 위의 과정을 모든 입력값에 대하여 시행 하면 된다. 시간 단축 방법 1) stdio 스트림 과의 동기화 취소 cin.tie(NULL);cout.tie(NULL); ios_base::sync_with_stdio(false); 위의 코드를 추가해 주면 cin , cout이 훨씬 빠르게 돌아간다. 자세한 설명은 아래 글 참고..! 2022.07.0..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cK91CH/btrGgozQN4R/UM9a105uHCcQ5kyUC0r84k/img.png)
백준 1197번 문제는 MST( Minimum - Spanning -Tree )를 구하는 문제이다. 알고리듬으로 Union - Find 를 이용하여 구하면 간단하게 구할 수 있다. 문제 알고리듬 ① 입력 Edge들을 먼저 가중치 기준으로 오름차순 정렬 한다. - 정수 A,B,C 를 tuple 사용하여 묶어서 vector에 저장 - algorithm stl의 sort 함수 사용 (가중치 기준 정렬이므로 cmp 함수 추가) ② 정렬된 Edge들을 하나씩 꺼내며 싸이클이 생기는 지 확인 (Tree 이기 때문에 싸이클이 생기면 안됨) - 정렬된 edge들을 하나씩 꺼내며 정수 A,B의 find 값이 같은 지 확인 - 같다면 Union(A,B) 해주고 다르다면 무시 - 같을 때 Union 해주면서 그 edge의 ..