기록보관소

2021.06.21 - [알고리즘] - [BOJ 15649번] N과 M (1) [BOJ 15649번] N과 M (1) 15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구현합니다. 재귀함수로 구현할 때는 함수 내에서 동일한 함수 ark-hive.tistory.com 2021.06.21 - [알고리즘] - [BOJ 15650번] N과 M (2) [BOJ 15650번] N과 M (2) 이번 문제는 BOJ 15649번 N과 M(1)과 동일한 문제입니다. 다만, 오름차순의 수열만을 출력해야하므로 재귀함수의 탈출조건에서 수열을 출력하기 전에 수열이 오름차순으로 정렬되어 있는지 확인하 ark-hive.tistory.com 이번 문제는 N과..

이번 문제는 BOJ 15649번 N과 M(1)과 동일한 문제입니다. 다만, 오름차순의 수열만을 출력해야하므로 재귀함수의 탈출조건에서 수열을 출력하기 전에 수열이 오름차순으로 정렬되어 있는지 확인하는 과정을 추가하여야 합니다. BOJ 15649번에 대한 설명은 하단의 링크에서 확인부탁드립니다. https://ark-hive.tistory.com/14 작성한 코드는 다음과 같습니다. #include int N, M; int sequence[10]; int check[10]; //back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다. //기능 특성상 재귀함수 형태로 구현됩니다. void final_process(){ for (int i = 0; i < M-1; i++) { printf("%d ..

15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구현합니다. 재귀함수로 구현할 때는 함수 내에서 동일한 함수를 활용하여 부분 문제를 풀 수 있도록 작성하여야 합니다. 공통적으로 재귀함수는 탈출조건과 호출부로 나누어지게 됩니다. 해당 문제에서는 탈출조건은 depth가 M일 때이며 이때 탐색한 수열을 출력하고 재귀함수를 종료하게 됩니다. 작성한 코드는 다음과 같습니다. #include int N, M; int sequence[10]; int check[10]; //back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다. //기능 특성상 재귀함수 형태로 구현됩니다. void final_process() { for (i..

원래 좌표, 압축된 좌표, 순서를 저장할 수 있도록 구조체를 선언한 후 처음에는 원래 좌표를 기준으로 정렬하여 압축된 좌표를 찾고, 그 후 입력받은 순서대로 정렬하여 압축된 좌표를 문제의 답과 같은 순서로 출력할 수 있도록 하였습니다. 작성한 코드는 다음과 같습니다. #include #include int N; typedef struct point { int x; int x_; int order; } POINT; POINT points[1000020]; int compare(const void* first, const void* second) { if (((POINT*)first)->x x) return -1; else if (((POINT*)first)->x > ((..

나이, 순서 정보를 함께 저장한 후 문제에서 요구하는 기준에 따라 c언어에 내장된 qsort 함수로 정렬시켰습니다. #include #include int N; typedef struct member { int age; char name[200]; int order; } MEMBER; MEMBER members[100020]; int compare(const void* first, const void* second) { if (((MEMBER*)first)->age age) { return -1; } else if (((MEMBER*)first)->age > ((MEMBER*)second)->age) { return 1; } else if (((MEMBER*)firs..

1181번 문제를 풀기 위해서 문제에서 주어진 정렬 조건을 확인하고, 조건에 맞춰 compare함수를 작성하였습니다. c언어에 내장된 qsort와 문자열 함수를 활용하여 문제를 간단하게 해결할 수 있었습니다. 작성한 코드는 다음과 같습니다. #include #include #include int N; typedef struct word { char word_[55]; int length; } WORD; WORD words[20020]; int compare(const void* first, const void* second) { if ((((WORD*)first)->length) length)) { return -1; } else if ((((WORD*)first)->..

BOJ 11650번 좌표 정렬하기와 동일한 문제였습니다. 단지, 좌표를 정렬할 때 먼저 y좌표를 기준으로 오름차순으로 정렬한 후 y좌표가 동일할 때는 x좌표를 기준으로 오름차순 정렬하는 것으로 변경되었습니다. BOJ 11650번에 대해 작성한 글의 링크입니다. https://ark-hive.tistory.com/9 BOJ 11650번 좌표 정렬하기 구조체를 활용하여 좌표를 저장하였습니다. 저장된 좌표를 c언어의 라이브러리에 내장된 퀵 정렬을 사용하여 좌표를 정렬하였습니다. 이때 문제에서 요구하는 순서로 좌표를 출력하기 위해 comp ark-hive.tistory.com #include #include int N; typedef struct point { int x; int y; } POINT; POINT..

구조체를 활용하여 좌표를 저장하였습니다. 저장된 좌표를 c언어의 라이브러리에 내장된 퀵 정렬을 사용하여 좌표를 정렬하였습니다. 이때 문제에서 요구하는 순서로 좌표를 출력하기 위해 compare 함수를 다음과 같이 작성하였습니다. #include #include int N; typedef struct point { int x; int y; } POINT; POINT points[100020]; int compare(const void* first, const void* second) { if ((((POINT*)first)->x) x)) return -1; else if ((((POINT*)first)->x) == (((POINT*)second)->x)) { if ((..

정렬에서는 최악의 경우의 수행시간이 중요하다. 그런데 각 원소를 비교하며 정렬하는 비교정렬의 경우(ex) 병합정렬, 퀵 정렬, 힙정렬 etc) 최악의 경우의 Ω(nlgn) 비교가 필요한다고 한다. 입력에 대해 순서를 결정하기 위해 필요한 비교를 트리로 나타낸 것을 결정트리라고 한다. 어떠한 입력에 대해서도 정렬된 순열을 출력하기 위해서는 입력에 대해 가능한 모든 순열을 만드는 결정트리가 존재해야 한다. 이때 결정트리의 루트와 리프 사이의 가장 긴 거리가 비교 횟수가 가장 많은 최악의 경우이며 이 값은 트리의 높이에 해당한다. n개의 입력에 대해 가능한 순열은 n!이며 이때 트리의 높이는 lg(n!) = Ω(nlg(n)) 이다. 따라서 최악의 경우는 하한은 nlg(n)이다. 즉, 비교 정렬의 경우 아무리 ..

숫자에서 가장 큰 자리수를 구한 후 각 자리수의 숫자들이 0~9라는 사실을 활용하여 계수정렬을 시켰습니다. 작성한 코드는 다음과 같습니다. #include int N; int count[10]; int in_number = 0; //각 자리수는 0~9까지 제한된 범위 -> 계수정렬 O(N) int main(void) { scanf("%d", &N); for (int i = 1000000000; i >= 1; i /= 10) { if (N / i > 0 || in_number == 1) { in_number = 1; count[N / i]++; N -= (N / i * i); } } for (int i = 9; i >= 0; i--) { if (count[i] != 0) { printf("%d", i); ..