여러 개의 컴퓨터를 연결하면 강력한 성능의 컴퓨터를 만들 수 있다는 생각, 클럭을 올리거나, CPI를 개선하는 것보다 에너지 측면에서 더욱 유리한 상황 -> 멀티프로세서(2개 이상의 프로세서로 구성된 컴퓨터 시스템)의 등장 장점으로 소프트웨어가 프로세서를 효율적으로 사용할 수 있다고 가정하면 작고 효율적인 프로세서로 단위 에너지당 성능을 개선할 수 있다. 프로세서를 늘리기만 하면 되므로 확장성있는 컴퓨터 시스템을 만들 수 있다. 또한, 소프트웨어가 확장성이 있다면 일부 하드웨어가 고장이 나도 처리를 그대로 수행할 수 있으므로 가용성을 개선할 수 있다. 멀티프로세서에서 실행하는 프로그램의 유형에 따라 다른 용어를 사용한다. 독립적인 프로그램을 여러 개 실행하는 것을 태스크 수준 병렬성(task-level ..
이번 문제는 스도쿠를 푸는 문제입니다. 스도쿠의 규칙에 위배되지 않도록 빈칸을 적절하게 채움으로써 간단하게 문제를 해결할 수 있었습니다. 스도쿠의 빈칸을 채우기 위해 모든 경우를 탐색하는 백트래킹 기법을 사용하였습니다. 빈 칸의 좌표를 저장한 후 빈 칸의 개수만큼의 높이를 가진 트리를 탐색하는 재귀함수를 통해 백트래킹을 구현하였습니다. 재귀함수를 한번씩 통과할 때마다 빈 칸이 한 개씩 채워지며 모든 빈 칸이 채워지면 스도쿠를 출력하도록 하였습니다. 문제에서 제약조건으로 c언어의 경우 80ms 내에 처리하도록 하였으며, 작성한 코드는 76ms에 스도쿠를 처리할 수 있었습니다. 백트래킹을 빠르게 실행하기 위해서는 필요없는 경우를 무시하는 가지치기가 필요합니다. 재귀 함수에서 스도쿠를 출력하자 마자 프로그램이..
이 문제는 N*N 체스판에서 N개의 퀸을 놓을 수 있는 경우를 계산하는 아주 유명한 문제이다. 이 문제를 풀기 위해 N개의 퀸을 놓는 경우를 모두 조사하는 방식으로 진행하였고 따라서 백트래킹 기법을 사용하였다. 백트래킹은 트리 형태로 모든 경우를 탐색하는 기법이므로 재귀함수의 형태로 구현할 수 있고 재귀 함수의 탈출 조건에 문제에서 원하는 답을 얻기 위한 마지막 처리를 추가하는 식으로 코드를 작성할 수 있었습니다. N*N 체스판을 배열로 선언하여 직접 퀸을 체스판에 배치하고 퀸의 이동가능방향에 다른 퀸이 존재하는 지 확인하는 방식으로 문제를 해결할 수 있지만 이번에는 배열 사용을 줄이는 방향으로 코드를 작성해보았습니다. 가로, 세로, 대각선 방향으로 오직 1개의 퀸만이 놓일 수 있다는 사실에서 아이디어를..
이번 문제는 중복조합으로 생성된 수열 중 비내림차순에 해당하는 수열만 출력하는 문제입니다. N과 M(3) 문제와 비슷한 코드를 사용하며 다른 점은 M 길이의 수열을 출력하기 전 해당 수열이 비내림차순인지 확인하는 과정을 거친다는 점입니다. N과 M(3)에 대한 설명은 아래 글에 있습니다. 2021.06.21 - [알고리즘] - [BOJ 15651번] N과 M (3) [BOJ 15651번] N과 M (3) 2021.06.21 - [알고리즘] - [BOJ 15649번] N과 M (1) [BOJ 15649번] N과 M (1) 15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구 ark-hive.tistory.com 작성한 코드는 다음..
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); ..
계수 정렬에서 배열로 숫자의 빈도를 세는 방식을 응용해서 코드를 작성해보았습니다. #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..
계수정렬은 n개의 입력원소가 있고 각각의 원소가 0부터 k 사이에 있는 정수이며. k=O(n) 일 때 Θ(n) 시간에 수행되는 정렬이다. 계수 정렬은 각 입력 원소 x에 대해 x보다 작은 원소의 개수를 센다. 이 수는 출력 배열에서 원소 x의 위치를 정하는 데 사용된다. 예를 들어, x보다 작은 원소가 5개라면 x는 출력 배열에서 6번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다. 같거나 작은 원소의 개수를 구하여야 하며, 안정성을 유지하기 위해 입력 원소를 뒤에서부터 확인하여 출력배열의 적절한 위치에 넣어야 한다. 계수정렬의 코드에서는 입력 배열과 출력배열, 같거나 작은 원소의 개수를 저장하기 위한 임시 배열이 필요하다. 입력 원소..
수 체계와 변환 R 진법 체계 : 숫자의 자릿수와 관련이 있는 표기법으로 각 자리의 숫자에 자릿수에 비례하는 가중치가 부여된다는 점이 특징이다. 어떤 R 진법의 경우, 0 ~ R-1의 숫자를 사용하며 R> 10인 경우, 수를 표기하기 위해 알파벳을 사용하기도 한다. R 진법에서 소수는 가중치인 거듭제곱에서 지수의 음과 양을 나눈다. 2진법에서는 소수점 아래 첫 번째 자리의 가중치가 과 같다. 각 체계에서 다른 체계로 변환할 수 있다. 다만 10진법이 아닌 진법에서 10진법이 아닌 진법으로 변환하는 것은 추천되지 않는다. 해당 진법에서의 연산규칙(연산 테이블)을 고려해야 하며 그것은 우리가 익숙하지 않아 시간이 오래 걸리기 때문이다. 예로 들면 다음과 같다. 쉬운 예이지만 4진법의 곱셈과 덧셈을 해야 한다..
루프 불변성은 알고리즘이 타당한지 확인하기 위해 사용되는 성질 중 하나이다. 쉽게 설명하자면 우리가 작성한 알고리즘 내부에 for나 while 같이 반복문이 삽입되어 있을 때 그것이 원하는 결과를 출력하는지 루프 불변성을 통해 확인하는 것이다. 루프 불변성을 통해 알고리즘의 타당성을 증명하기 위해 만족시켜야 하는 3가지 조건들이 있다. 1. 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 유지되어야 한다. 2. 루프가 반복되기 전에 루프 불변성이 유지되었다면 다음 반복이 시작되기 전까지도 계속 유지되어야 한다. - 위의 2가지만 만족시키더라도 루프 불변성이 유지됨을 알 수 있다. 3. 루프가 종료될 때 유지된 루프 불변성이 알고리즘 타당성 증명에 의미가 있어야 한다. - 확인한 루프 불변성을 알고리즘..
어떤 입력을 받았을 때 출력을 내놓는 일련의 계산 과정. 입출력 관계를 지탱하는 계산 과정이라고 할 수 있다. 지금까지 많은 알고리즘이 개발되었지만 모든 문제에서 최적의 해를 도출하는 알고리즘은 찾기 힘들기 때문에 상황에 따라 필요한 알고리즘을 선택하거나 개발해서 사용해야 한다. 알고리즘이 모든 입력에 대해 올바른 출력을 내놓고 종료한 다면 그 알고리즘은 타당하다고(Correct) 하며 문제에 대해 그런 알고리즘을 찾는 것을 푼다고(Solve) 한다. 알고리즘과 항상 함께 하는 것이 있다. 바로 자료구조다. 자료구조는 알고리즘을 사용할 때 자료에 쉽게 접근하고 변경하기 위해서 자료를 저장하고 조직하는 방법이다. 알고리즘의 중요성은 날이 갈수록 커지고 있다. 우리 주위를 둘러싼 시스템들의 성능이 하드웨어 ..
- Total
- Today
- Yesterday
- 영어 어휘
- BFS
- 구조체
- 구현
- 완전탐색
- backtracking
- BOJ
- 취미
- 백트래킹
- Push
- C언어
- recursive
- 스택
- 백준
- 메이플스토리
- Verilog
- 큐
- 정렬
- 재귀함수
- 영화
- Git
- 너비우선탐색
- 이진탐색
- 알고리즘
- 베릴로그
- 애니메이션
- 건이의 특제 떡국 끓이기
- 이분법
- C++
- gem5
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |