![]()
🟩 힙 = 퇴적물 바닷속 퇴적물처럼 아래에 큰 바위, 중간 정도의 돌, 그 위에 작은 모래 순으로 쌓여있다. 🟩 그래프의 트리 구조 중 하나(완전 이진트리) 각 노드의 키 값이 그 자식의 키 값보다 작지 않거나(최대힙), 크지 않은(최소힙) 완전 이진트리 완전 이진트리는 중복을 허용하지 않지만 힙은 허용한다. 🟩 정렬을 효율적으로 수행하는 트리 '우선순위 큐'를 구현할 때 사용 최댓값과 최솟값을 빠르게 찾기 위해 고안됨 배열을 사용하면 O(n)만큼 시간이 걸리지만, 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값, 최댓값을 구할 수 있다. 🟩 힙에서의 부모-자식 관계 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 ..
![]()
해시함수와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장 특정 키값 K를 갖는 데이터를 찾는 문제에서 활용 원하는 데이터를 선형탐색으로 구할 수는 있지만, 데이터 양에 비례해서 계산시간이 늘어난다는 단점이 있다. 배열 탐색에 시간이 걸리므로, 적합하지 않은 구조 👉 해시테이블의 등장 🟩 배열을 만들고 데이터를 추가할 때, '해시 함수' 이용 키 값을 해시 테이블의 주소로 변환하는 함수 계산이 용이해야 하며, 적은 충돌 발생 👉 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 🌟 해시 함수의 종류 1. 제산잔여법 키 값을 해시 함수에 넣어 나오는 해시값을 배열의 갯수로 나누어 나머지를 구한다. 예) 4928 % 5 = 3 구한..
![]()
🟩 LIFO (Last In First Out) 🟩 DFS (깊이우선탐색) 후보 중에서 항상 최신의 것을 선택 🟩 헤더 추가 🟩 주요 동작 push 삽입 pop 추출 peek 가장 최상단에 있는 데이터가 무엇인지 알 수 있음 🟩 삽입/삭제가 단방향으로 이루어짐 데이터를 추가할 때, 가장 위에 추가된다. 삭제도 가장 위에서 이루어진다는 단점이 있다. 데이터 접근도 스택의 가장 위에 있는 데이터만 가능하기 때문에, 원하는 데이터가 필요하면 그 때까지 pop해야 한다. 멤버 함수 기능 s.size() s의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴 s.empty() s의 사이즈가 0인지 아닌지를 확인 s.top() s에 가장 나중에 들어간 원소를 리턴 s.push(val) s의 뒤에 val를 추가..
![]()
🟩 FIFO (First In First Out) 🟩 BFS (너비우선탐색) 에서 활용 탐색 후보 중에서 항상 가장 오래된 것을 선택 🟩 헤더 추가 🟩 주요 동작 enqueue : 삽입 dequeue : 추출 peek : 추출할 데이터의 값을 알 수 있음 🟩데이터 추가/삭제 방향이 반대 1 : 삽입 연산만 발생 (가장 위에 추가됨) 2 : 삭제 연산만 발생 🟩 중간에 있는 데이터에 접근 불가 필요한 데이터가 나올 때까지 dequeue 멤버 함수 기능 q.size() q의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴 q.empty() q의 사이즈가 0인지 아닌지를 확인 q.front() q에 가장 먼저 들어간 원소를 리턴 q.back() q에 가장 나중에 들어간 원소를 리턴 q.push(val)..
![]()
데이터를 1열로 나열 🟩 접근 어려움 흩어져서 저장되어 있기 때문에 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근 가능 🟩 추가, 삭제 용이 추가시 추가할 위치의 앞뒤 포인터만 변경하면 된다. 삭제도 동일 cf. 삭제시, 메모리에는 데이터가 남지만 어디에도 접근할 수 없으므로 일부러 삭제할 필요없다. 이후에 이 영역이 다시 사용될 때 덮어쓰여 재사용 가능하다. 🟩 데이터가 메모리 사이의 연속된 위치에 저장되지 않는다 데이터의 물리적인 순서와 관련없음 연결 정보의 논리적 순서를 결정한다. 🌟 head 시작점, 선형 구조에서 첫 번째 노드를 가리키는 용어 노드(node) = data + pointer 전체 리스트를 탐색하거나 데이터 추가/삭제시 기준점으로 사용한다. 🟩 계산시간 검색 O(n) 추..
![]()
데이터를 1열로 나열한 자료구조 같은 자료형, 같은 크기의 기억 공간 🌟 배열의 선두는 왜 0번인가? 더보기 배열의 인덱스는 첫 번째 요소에서 얼마나 떨어져 있는가를 통해 정한다. 첫 번째 요소는 0만큼 떨어져 있으므로 a[0]이다. 🟩 접근(검색) 용이 연속된 영역에 저장되어 메모리 주소 계산 가능 각 데이터에 바로 접근 가능 🟩 추가, 삭제가 어려움 1. 데이터 추가시 배열의 마지막에 추가로 공간 확보 2. 공간이 비므로 앞으로 하나씩 옮긴다. 3. 원하는 공간에 데이터 추가 cf. 삭제 시에는 삭제 후 빈공간에 맞춰 하나씩 매꾸기 🟩 로 구성 index : 컴퓨터 구조, 메모리 주소와 무관하게 정의된다. 🟩 원소의 메모리 공간의 물리적인 위치를 '순서'적으로 결정 배열의 순서 : 메모리 공간에서 저..
A, B 두 사람이 가위바위보 게임을 합니다. 총 N번의 게임을 하여 A가 이기면 A를 출력하고, B가 이기면 B를 출력한다. 비기면 D를 출력한다. 가위 바위 보는 1 2 3으로 정한다. 두 사람의 각 회의 가위바위보 정보가 주어지면 각 회를 누가 이겼는지 출력하는 프로그램을 작성하세요. 입력 첫 줄에 N 두 번째 줄에 A의 정보 N개 세 번째 줄에 B의 정보 N개 5 2 3 3 1 3 1 1 2 2 3 출력 각 회의 승자 출력, 비겼을 경우 D 출력 A B A B D 1트 (성공) 맞기는 한데 복잡한가? 😟 #include using namespace std; int main(void){ freopen("input.txt", "rt", stdin); int n, a, b; cin >> n; int a..
![]()
한 줄에 앉은키 정보가 주어지면 뒷사람 모두의 시야를 가려 영화 시청이 불가능하게 하는 분노유발자가 그 중에 몇 명이 있는지 구하는 프로그램을 작성하세요. 입력 첫 줄에 한 줄에 앉은 학생 수가 주어진다. 두 번째 줄에 N명의 앉은 키 정보가 앞 자리 학생부터 차례대로 주어진다 (45~100) 10 56 46 55 76 65 53 52 53 55 50 출력 자신의 뒷 사람 모두를 시청방해하는 학생 수를 출력 3 1트 (실패) #include using namespace std; int main(void){ freopen("input.txt", "rt", stdin); int n, height, count = 0; cin >> n; int h[n]; for(int i = 0; i < n; ++i){ cin..
아파트 내 진동센서 존재. 층간 진동소음 측정치를 초단위로 아파트 관리실에 실시간으로 전송. 한 세대의 측정치가 M값을 을 넘으면 세대호수와 작은 경보음이 관리실 모니터에서 울린다. 한 세대의 N초 동안의 실시간 측정치가 주어지면 최대 연속으로 경보음이 울린 시간을 구하라. 경보음이 없으면 -1을 출력한다. 입력 첫 줄에 자연수 N과 M이 주어진다. 두 번째 줄에 N개의 측정값(1000 이하)이 초 순서대로 입력된다. 10 90 23 17 120 34 112 136 123 23 25 113 출력 최대 연속 경보음이 울린 시간을 출력하세요 3 1트 (강의 풀이) max = -2147000000 사용 방법 까먹음.. 풀이보니까 충분히 풀 수 있었다.. #include using namespace std; i..
현수네 반은 학생이 N명 있다. 각 학생들에게 숫자가 적힌 카드를 줬다. 각 학생들은 1부터 자기 카드에 적힌 숫자까지의 합을 구해야 한다. 자동 채점하는 프로그램을 만들어라. 입력 반 학생 수 (각 학생들은 1부터 N까지 번호가 부여되어 있다 가정) 카드의 수와 정답 3 10 55 20 350 100 5050 출력 정답이면 YES, 틀리면 NO YES NO YES 1트 성공 #include using namespace std; int GetSum(int num){ int sum = 0; for(int i = 1; i > num; string answer[num]; int a, b; for(int i = 0; i > a; cin >> b; sum = GetSum(a); a..
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라 한다. 예를 들어 AbaAeCe 와 baeeACA는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 알파벳과 그 개수가 모두 일치한다. A(2), a(1), b(1), c(1), e(2). 즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 한다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 입력 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력된다. 단어의 길이는 100을 넘지 않는다. 출력 YES/NO 1트 (실패) 시간초과 & 답 도출 실패 와 반복문에 '\0' 넣..
![]()
이진 트리의 노드를 순회활 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함 스레드 트리 : '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 하는 것 '스레드' : 순회 방법에 따른 방문순서를 유지하는 포인터 스레드 트리 구현방법 1. 포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가하는 것 -> 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고 왼쪽 스레드 : 그 노드의 선행 노드를 가리킴 추가된 포인터 필드에 의한 스레드 구현 - 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 가능 - 하지만 스레드..
