[2020_하계_모각코] 08주차(08/04)

오늘의 목표 : <자료구조와 함께 배우는 알고리즘 입문 C언어편> 03장 학습 + BOJ 파이썬으로 1문제 해결하기

 

<자료구조와 함께 배우는 알고리즘 입문 C언어편> 03장 학습

 

검색 알고리즘

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다.

 

#include <stdio.h>
#include <stdlib.h>

int search(const int a[], int n, int key)
{
	int i = 0 ;
    while(1) {
    	if (i == n)
        	return -1;
        if (a[i] == key)
        	return i;
        i++;
       }
      }
int main(void)
{
	int i, nx, ky, idx ;
    int *x;
    puts("선형 검색");
    printf("요소 개수 : ");
    scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    for(i=0; i<nx; i++) {
    	printf("x[%d] : ", i);
        scanf("%d", &x[i]);
       }
       printf("검색값 : ");
       scanf("%d", &ky);
       idx = search(x, nx, ky);
       if (idx == -1)
       	puts("검색에 실패했습니다.");
       else
       	printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
       free(x);
       
       return 0;
}

2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다.

#include <stdio.h>
#include <stdlib.h>

int bin_search(const int a[], int n, int key)
{
	int p1 = 0;
    int pr = n - 1;
    int pc;
    do {
    	pc = (pl + pr) / 2 ;
        if (a[pc] == key)
        	return pc;
        else if(a[pc] < key)
        	pl = pc + 1 ;
        else
        	pr = pc + 1 ;
       } while(pl <= pr);
       return -1;
    }
int main(void)
{
	int i, nx, ky, idx;
    int *x;
    puts("이진 검색"):
    printf("요소 개수 : ");
    scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    printf("오름차순으로 입력하세요.\n");
    printf("x[0] : ");
    scanf("%d", &x[0]);
    for (i=1; i<nx; i++) {
    	do {
        	printf("x[%d] : ", i);
            scanf("%d", &x[i]);
           }while(x[i] < x[i-1]);
         }
    printf("검색값 : ");
    scanf("%d", &ky);
    idx = bin_search(x, nx, ky);
    if (idx == -1)
    	puts("검색에 실패했습니다.");
    else
    	printf("%d는(은) x[%d]에 있습니다. \n", ky, idx);
       free(x);
       
    return 0;
  }

3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.

 -체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

 -오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

BOJ 파이썬으로 1문제 해결하기

11652 카드

https://www.acmicpc.net/problem/11652

11652번: 카드

#BOJ 11652

n=int(input())
num={}
for i in range(n):
    k=int(input())
    if k in num.keys():
        num[k]+=1
    else:
        num.setdefault(k, 1)

max_v=0
max_k=0
for k,v in num.items():
    if v>max_v:
        max_v=v
        max_k=k
    elif v==max_v:
        max_k=min((max_k, k))

print(max_k)

 

08주차 회고록

C언어로 기본적인 자료구조 알고리즘을 복습할 수 있어서 유익했다. C언어를 더욱 연습한 이후에 C++이나 C#까지 도전해보고 싶은 마음이 생겼다. 파이썬은 계속해서 백준 알고리즘으로 연습하다 보니까 익숙해진 것 같다. 문제를 해결하는 과정에서 알고리즘을 떠올리는 게 시간을 많이 잡아 먹지만 코드로 구현하는 것은 단축된 것 같아서 뿌듯하다.