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 ((..
숫자에서 가장 큰 자리수를 구한 후 각 자리수의 숫자들이 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); ..
계수 정렬에서 배열로 숫자의 빈도를 세는 방식을 응용해서 코드를 작성해보았습니다. #include #include int N; int sum; int max = -5000, min = 5000; int count[10000]; int temp; int first_mode; int second_mode=999999; int mode; //count sort //ceil - 올림, floor - 내림 //반올림은 floor(x+0.5) int main(void) { scanf("%d", &N); for (int i = 0; i max) max = temp; if (temp < min) min = temp; t..
- Total
- Today
- Yesterday
- 재귀함수
- 백트래킹
- 구현
- 건이의 특제 떡국 끓이기
- 취미
- 정렬
- 완전탐색
- BFS
- 알고리즘
- 백준
- gem5
- recursive
- C++
- 구조체
- 이분법
- 이진탐색
- Verilog
- BOJ
- 영어 어휘
- backtracking
- Git
- 너비우선탐색
- 스택
- C언어
- 큐
- Push
- 메이플스토리
- 베릴로그
- 애니메이션
- 영화
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |