본문 바로가기

삼성전자 알고리즘/자료구조 알고리즘

(16)
7. 이진 탐색 [Binary Search] 이진 탐색 형태 : #include #include // 여기서부터 작성 int N, T; int arr[50001]; //50,000개의 데이터 int bsearch(int s, int e, int d) { int m; while (s d) { e = m - 1; } } //못 찾은 경우 리턴 0 return 0; } int main(void) { // freopen("input.txt", "r", stdin); int i, data; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &arr[i]); } scanf("%d", &T); for (i = 0; i < T; i++) { scanf("%d", &data); //찾을 데이터 printf("%d\n..
6. 힙(Heap) 힙 문제 : [백준 11066] 파일 합치기 원본 출처 : https://www.acmicpc.net/problem/11066 문제 풀이 : https://gudwns999.tistory.com/109 :예를 들어 C1, C2, C3, C4가 있을 때 최솟값이 나오기 위해서는 가장 작은 값1 + 가장 작은 다음 값2 가 먼저 연산이 되어야 한다. 그리고 이 연산 결과가 다시 힙트리에 들어가면 된다. 이를 반복 [정올 1318] 못생긴 수 원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=50&sfl=wr_subject&stx=%EB%AA%BB%EC%83%9D%EA%B8%B4&sop=and 문제 풀이 : https://gudwns..
5. 우선순위 큐 우선 순위가 높은 데이터가 먼저 나가는 자료구조. : 우선 순위를 가진 항목들을 저장하는 큐 우선순위 큐 활용 분야 : 1. 시뮬레이션 시스템 2. 네트워크 트래픽 제어 3. OS 작업 스케줄링 출처 : https://hannom.tistory.com/36 우선순위 큐의 구현 방법 3가지 1. 배열 2. 연결리스트 3. 힙(Heap) 배열 / 연결리스트를 이용해서 구현 시 장점 : 간단하게 구현 가능 단점 : 1. 데이터 삽입 및 삭제 시 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다. 2. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다. (이 경우 우선순위가 가장 낮은 데이터를 저장할 때 최악의 경우가 발생) 이러한 단점들 때문에 우선순위 큐는 힙(He..
4. 순열, 조합 1. 모든 경우의 수를 나열하는 알고리즘. 2. 작은 범위의 문제에 대해서 완전 탐색 알고리즘에 적합. 조합 조합의 점화식 구하는 방법 : http://bitly.kr/nW9lZ Combination, n개 중 k개를 고르는 방법의 수 문제)Combination nCk 는 n개 중 k개를 고르는 방법의 수이다. nCk를 구하는 일반식은 다음과 같다. 위 식은 n!을 이용하기 때문에 n이 커지면 overflow가 발생하여 정확한 값을 구할 수가 없다. 물론 위 방법 외.. huiyu.tistory.com 조합 수 구하는 방법 : #include using namespace std; int Comb(int n, int r){ //n개의 수중 r개 선택 if(r==n){ return 1; }else if(r=..
3. 재귀함수를 비재귀함수로 변환 재귀함수 장점 : 직관적인 알고리즘 설계가 가능 재귀함수 단점 : 함수 호출 오버헤드 (Context Switch) -> 시간 성능 저하, 자신을 다시 호출하면서 생성되는 변수 때문에 메모리 문제가 생길 수 있음. (출처 : http://bitly.kr/DNHtU3http://bitly.kr/DNHtU3) -최적화 단계에서 비재귀 함수로 변환해야 함.- 1. 재귀함수와 비재귀 함수의 성능 차이 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; //재귀함수 long long recursiveFactorial(int n) { if (n < 1) { return 1; } else { return n * recursiveFactoria..
2. 링크드 리스트 [Linked List] Why? 1. 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점이 있기 때문. How? 1. 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당 2. 링크드 리스트의 종류 2-1. 단일 연결 리스트 #include using namespace std; //Linked List //https://hojak99.tistory.com/274 class Node{ public : Node *nextNode = nullptr; int data; }; class Link { public : Node *head = new Node(); void insert(Link *linkedList, int data); void printList(Link *linkedList); }; void Lin..
1. 해싱 [Hashing] Why ? 1.하나의 문자열을 보다 빨리 찾을 수 있도록 사용. How? 1.인덱스에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환. 2.다양한 구현 기법 존재. 2-1. 나눗셈 방법 (The division method) : h(k) = k mod m 2-1-a. m = 2^p인 경우는 피하는 것이 좋다. 2-1-b. m= 2^p - 1 인 경우도 피하는 것이 좋다. 2-1-c. 2^p에 너무 가깝지 않은 소수를 선택하는 것이 좋다. ex) 키의 수가 2,000 일 때 해쉬 테이블의 크기를 m = 701로 잡으면 좋다. (amortized analysis에 의해 3으로 나누는 것이 효율적이라 고 밝혀짐. 출처 : Tacademy_10강 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(1) | T아카데미..
0.SW 역량테스트 B형 파악하기 보호되어 있는 글입니다.