본문 바로가기

삼성전자 알고리즘

 (65)
9. 포인터 [Pointer] 포인터는 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간주소를 가리키는 변수를 말한다. 출처 : 위키피디아 포인터를 사용하는 이유 : call by reference 와 call by address 로 접근하기 위해 1. call by reference : 참조자 &를 붙여줌 (참조자 : 변수의 별칭을 하나 붙여주는 것) #include using namespace std; int main(){ int a = 5; int &b = a; printf("a = %d, b = %d\n", a,b); // a = 5, b = 5 b = b + 1; printf("a = %d, b = %d\n", a,b); // a = 6, b = 6 return 0; } 2. call by address : *를 ..
8. 정렬 1. 버블 정렬 : 정렬 성능은 안좋지만 O(n^2) 빠르고 쉽게 구현 가능. 정렬이 중요한 문제가 아니라면 버블 정렬도 나쁘지 않음. #define SWAP(a,b) {int t; t= b; b=a; a=t;} int arr[5] = { 1,5,3,2,4 }; void bubble_sort(int arr_size) { for (int fixed_p = arr_size -1; fixed_p > 0; fixed_p--) { for (int bubble_p = 0; bubble_p arr[bubble_p+1]) {//5,3 일때 3,5로 바꿔줘야함 SWAP(arr[bubble_p], arr[bubble_p+1]); } } } }..
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..
3. 1240 : 제곱근 문제 출처 : http://www.jungol.co.kr/xpert/viewp.php?bo_table=sm_low&id=1240&alcate=&mtitle=%EB%8B%A8%EA%B3%84%EB%B3%84%ED%95%99%EC%8A%B5&al=001002&altitle=%EC%A4%91%EA%B8%89(Adv.Pro.)&alname=&altag=&page=1 정올::Xpert 임의의 정수 N이 주어졌을 때 N의 양의 제곱근의 정수부분을 출력하는 프로그램을 작성하라. 양의 제곱근이란 다음을 만족하는 수 X 를 뜻한다. N = X2 (X≥0) 주의 : sqrt와 같은 함수를 사용하지 말아야 하며 stdio.h 와 iostream 등 입출력 헤더에 있는 함수만이 사용가능한다. 이를 어길 경우 0점 처리를 한다..
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=..
2. 2961 도영이가 만든 맛있는 음식 문제 출처 : https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 문제 도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다. 지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다. 시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 www.acmicpc.net #include using namespace std; typedef struct ingredient { ..

티스토리툴바