본문 바로가기

알고리즘

 (44)
[BOJ 3009] 네 번째 점 문제 링크 : https://www.acmicpc.net/problem/3009 문제 분류 : 수학 문제 자체가 어렵진 않지만, XOR연산으로도 풀 수 있다는 걸 생각 못했다. 처음 구현한 코드 #include int x, y; int point[3][2]; int main() { for (int i = 0; i < 3; i++) { scanf("%d %d", &point[i][0], &point[i][1]); } point[0][0] == point[1][0] ? x = 2 : point[0][0] == point[2][0] ? x = 1 : y = 0; point[0][1] == point[1][1] ? y = 2 : point[0][1] == point[2][1] ? y = 1 : y = 0; pr..
[BOJ 15552] 빠른 A+B 문제 링크 : www.acmicpc.net/problem/15552 문제 분류 : 입출력 사용 언어에 맞는 빠른 입출력을 요구하는 문제이다. 문제 풀이는 했지만, 다른 사람들의 풀이를 보고 새롭게 알게된 내용이 있어서 정리 차원에서 기록을 남긴다. 속도 향상을 위한 방법 컴파일 속성 조정 (최적화 옵션 및 타겟 설정) 빠른 입출력 사용 참고) 더보기 register 변수를 사용하는 경우도 있는데, C++17부터 이 키워드는 사용되지 않는다고 한다. 기존 코드에 register 키워드가 있어도, 실제 레지스터를 사용하는 것은 컴파일러나 CPU에 따라 다르다고 한다. C언어의 경우 해당 키워드가 적용된다. RAM대신 CPU의 Register를 사용하게 되어 자주 사용 되는 변수를 register키워드로 선언..
백트래킹(back tracking) Goal 백트래킹에 대해 설명할 수 있다. DFS와 백트래킹을 설명할 수 있다. 백트래킹(backtracking)이란? 솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법 DFS와 Backtracking DFS : 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 모든 노드를 방문하는 것을 목표로 한다. Back-tracking : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법 => 일단 가보고 후보해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 나온다. DFS와 Back-tracking 둘다 재귀 호출 형태로 자주 구현이 되기 때문에 헷갈린다...
브루트 포스(brute force) Goal brute force에 대해서 설명할 수 있다. 브루트 포스(brute force)란? 완전 탐색(exhaustive search) 알고리즘 기법으로, 가능한 모든 경우의 수를 탐색하면서 문제 요구 조건을 만족 시키는지 확인하는 방법이다. *brute : 무식한, *force : 힘 즉, 무식하게 모든 경우에 대해 확인해 나가는 방법이다. 이 알고리즘은 자원이 충분하다면 100% 문제 해결이 가능한 알고리즘이다. 하지만 시간적 제한과 같이 자원의 제약이 있을 경우 적합하지 않을 수 있다. 완전 탐색 방법 선형 구조 : 순차 탐색 비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) *BFS, DFS에서 search는 일반적으로 생각하는 특정 값을 찾기 위한 탐색이 아니라, 순회(t..
Prim 알고리즘 Goal Prim 알고리즘에 대한 이해 Prim 알고리즘을 구현할 수 있다. Prim 알고리즘이 사용되는 예시를 들 수 있다. Prim(Prim's algorithm) 트리를 확장해 나갈 때 인접 정점 중 간선 가중치가 가장 작은 정즘을 선택하여 트리를 확장해 나가는 알고리즘 Prim알고리즘 동작 과정 그래프에서 정점 하나를 선택해서 트리를 만든다. 현재 트리가 n-1개의 간선을 가질 때 까지 다음 과정을 반복한다. (n은 그래프 전체 노드 개수) 트리에 포함되지 않은 인접 정점 중, 간선 가중치가 가장 작은 정점을 트리에 추가한다. 트리에 정점 v가 추가 되면, 트리에 인접한 정점이 갱신 될 수 있다. (v에 연결 되어 있으면서 트리에 없는 정점) 또한, 트리와 인접 정점 사이의 최소 가중치가 갱신 될..
유클리드 알고리즘(최대 공약수, 최소 공배수) Goal 유클리드 알고리즘(Euclidean algorithm)이란? 최대 공약수(GCD)를 구하는 알고리즘으로, 두 자연수 또는 두 다항식 사이에서 최대 공약수를 구할 때 사용되는 알고리즘이다. (유클리드 호제법이라고도 한다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.) 성질 2개의 자연수(또는 다항식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉, a와 b의 최대 공약수를 gcd(a, b)라고 하면, gcd(a, b) = gcd(b, r) 이 성립한다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 ..
모듈로 연산(modulo operation) Goal 모듈로 연산에 대한 이해 모듈로 덧셈, 뺄셈, 곱셈 연산에 대한 이해 모듈로 연산(Modulo Operation)이란? 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 정수론에서 모듈라 연산(modular arithmetic)이란, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. *나눗셈 정리(division theorem) 더보기 두 정수로부터 몫과 나머지를 얻는 연산 나머지 있는 나눗셈(division with remainders) 또는 유클리드 나눗셈(Euclidean division)이라고도 한다. *정의 정수 a와 양의 정수 b에 대하여 $a = bq + r$을 만족하는 q, r이 유일하게 존재한다. (q는 몫, r은..
소수 찾기 Goal 소수 찾기 알고리즘에 대해 설명할 수 있다. 상황에 맞게 소수 판별 알고리즘을 사용할 수 있다. 소수찾기 방법 2~n-1 까지 수와 나눠보고 소수 판별 n/2 범위까지 홀수 값으로 소수 판별 제곱수까지 확인해보고 소수 판별 에라토스테네스의 체 1. 2 ~ n-1 까지 수와 나눠보고 소수 판별 구현 코드 bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 시간 복잡도 : O(n) 3. n/2 범위까지 홀수 값으로 소수 판별 구현 코드 bool isPrime(int n) { if (n < 2) return false; // ..

티스토리툴바