본문 바로가기

분류 전체보기75

스택(Stack), 큐(Queue) 스택- 제일 나중에 들어온 원소가 제일 먼저 나가는 구조 ( LIFO - Last In First Out )- 알고리즘보다는 자료구조에 가까운 개념이다.  -> 알고리즘은 이러한 스택이나 큐를 이용해서 문제를 해결하는 방법이다. #include#includeusing namespace std;int main(){ stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while(!s.empty()){ cout - STL 라이브러리 문법을 이용해 사용한다.- 직접 구현해 볼 수 있지만 너무 간단하므로 생략하기로 한다. 큐- 들어온 것이 먼저 나가는 구조 ( FIFO - First In First Out ) #incl.. 2022. 2. 15.
계수 정렬 ( Counting Sort ) 계수 정렬'범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 -> 속도 : O(N)단순하게 '크기를 기준'으로 세는 알고리즘 문제) 주어진 5 이하 자연수 데이터들을 오름차순 정렬하시오.     1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기를 기준으로 갯수만 세주면 되기 때문에 다른 정렬들처럼 위치를 바꿀 필요가 없다.모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적이다. 초기 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1크기 = 1크기 = 2크기 = 3크기 = 4크기 = 500000 1. 첫번째 상태1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 .. 2022. 2. 15.
백준 1431번 ( 시리얼 번호 ) 문제)다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.A와 B의 길이가 다르면, 짧은 것이 먼저 온다.만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.  어.. 2022. 2. 14.
배열의 크기를 넘어가서 사용할 경우 1. 배열 색인의 유효성 체크 char str[8]; 이 경우 str 배열의 범위를 벗어난 str[8]을 사용하여 값을 대입하면 어떤 일이 발생할까? [ 문법 오류가 아니다. ] - str[8]이라는 표현은 배열 문법이긴 하지만 메모리 주소를 표현하는 하나의 형식이기 때문에 컴파일러는 해당 주소에 대한 유효성 검사를 하지 않는다. 따라서 str[8]이 명백하게 str 배열의 범위를 벗어났다고 해도 컴파일러는 이 명령문에 대해 오류 처리를 하지 않는다. - 이런 경우 오류 처리를 하지 않기 때문에 컴파일이 잘 된다. 하지만 프로그램의 메모리 할당 구조에 따라 운 좋게 아무 문제 없이 동작하거나, 오류가 나서 프로그램이 중단되거나 혹은 오류는 발생하지 않지만 원하는 결과가 나오지 않는 경우가 생길 수 있다... 2022. 2. 14.
힙 정렬 ( Heap sort ) 힙정렬시간복잡도가 O(nlogn)으로 퀵정렬, 병합정렬과 같은 시간복잡도를 가진 정렬 알고리즘병합정렬과는 다르게 추가적인 메모리 필요 X항상 O(nlogn)의 성능을 보여주기 때문에 최악의 경우 O(n^2)의 성능을 보이는퀵정렬보다 안정적인 성능을 보인다.이론적으로는 퀵 정렬 병합 정렬보다 우위에 있지만, 단순히 속도만 가지고 본다면 퀵 정렬이평균적으로 더 빠르기 때문에 힙 정렬이 많이 사용되지는 않는다.배열을 최대힙 or 최소힙으로 만들어 root에 있는 값을 정렬하는 식으로 구현한다.힙(Heap)완전이진트리 형태의 자료구조힙은 최소힙과 최대힙 두가지로 나뉜다.힙은 일반적인 배열로 표현할 수 있다.  최대 힙 : "부모 노드 > 자식 노드"를 모든 노드에서 만족하는 완전이진트리   최소 힙 : "부모 .. 2022. 2. 11.
C++ STL sort() 함수 다루기 실제 알고리즘 대회에서 정렬 문제가 나올 때 빠르게 풀기 위해 sort()를 사용해 간단하게 정렬을 구현한다. sort() 헤더에 정의되어 있다. default 설정 => 오름차순으로 정렬 퀵 정렬을 기반으로 구현되어 있다. 퀵 정렬과 달리 모든 경우에 시간 복잡도 O(N * logN)을 보장한다. sort(start, end, 정렬기준); 사용 예시 1) sort(arr, arr + n); => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨 2) sort(v.begin(), v.end()); => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨 3) sort(v.begin(), v.end(), greater()); => 내림차순으로 정렬 4) sort(arr, arr + n, compa.. 2022. 2. 10.

티스토리툴바