본문 바로가기

알고리즘68

C++ 백준 BOJ 1212 8진수 2진수 8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하는 문제입니다. (난이도는 높지 않지만 출력값의 맨 앞이 0이 되는 경우, 시간초과 예외로 맨탈이..) 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net #include #include using namespace std; int main(){ string octal_str, binary_str = ""; cin >> octal_str; for(int i = 0; i < octal_str.size(); i++){ switch (octal_str[i]){ case '0': if(i == 0){ binary_str += "0"; break; } else{ binar.. 2022. 11. 15.
[기초] 자료구조 / 트리 (Tree) 트리 (Tree) 사이클이 없는 그래프를 트리라고 합니다. 따라서 정점이 V개 이면 간선은 V-1개를 가지는 성질이 있습니다. 루트 있는 트리 (Rooted Tree) 루트가 있는 트리로 아래 그림에서 1이 루트가 됩니다. 루트 부터 아래로 방향을 정할 수 있습니다. 이때 1은 2의 부모, 2는 4의 부모 2는 1의 자식, 4는 2의 자식, 3의 자식은 6과 7 4와 5는 형제, 2와 3도 형제 따라서 루트에 가까운 쪽이 부모가 됩니다. 부모가 없으면 루트, 자식이 없으면 단말정점(Leaf Node)이라 합니다. 같은 부모를 가지면 형제라 합니다. 깊이(Depth) 깊이는 루트부터의 거리를 말합니다. 루트의 깊이를 0으로 하거나 1로 합니다. 조상(Ancestor), 자손(Descendent) p -> .. 2022. 8. 12.
[기초] 자료구조 / 그래프(Graph)의 표현과 탐색 그래프를 저장하는 방식에 대해 알아봅니다. 그래프의 표현 - 위와 같은 그래프는 정점이 6개, 간선이 8개 있다. - 간선에 방향이 없기 때문에, 방향이 없는 그래프이다. - 정점 : {1, 2, 3, 4, 5, 6} - 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} 보통 위 그림과 같이 정점의 개수, 간선의 개수 그리고 m개의 줄에 어떤 간선이 연결되어 있는지 주어집니다. 인접 행렬(Adjacency-matrix) 정점의 개수를 V라 했을 때, V x V 크기의 이차원 배열을 이용합니다. A[i][j] = 1 (i -> j 간선이 있을 때), 0 (없을 때) 이 인접행렬은 없는 간선도 저장하기 때문에 불필요한 배열이 생겨 많.. 2022. 8. 10.
[기초] 자료구조 / 그래프 (Graph) 그래프 그래프는 일종의 자료구조이고, 정점과 간선으로 이루어져 있습니다. 정점은 Node, Vertex / 간선은 Edge라 하며 정점 간의 관계를 나타냅니다. ex) G(V,E) 차수(Degree) 차수는 정점과 연결되어 있는 간선의 개수를 말합니다. 위 그래프에서 1, 2, 3은 각각 두 개의 간선이 연결되어 있으므로, 차수는 모두 2가 됩니다. 경로(Path) 예를 들어, 정점A에서 정점 B로 가는 경로는 1. A -> C -> D -> E -> B 2. A -> B 3. A -> C -> B 4. A -> C -> E -> B 이렇게 거쳐가는 경우가 있습니다. 이것이 바로 경로가 됩니다. 사이클(Cycle) 시작 정점과 도착 정점이 같으면 사이클이라 합니다. 예를 들어, 정점A에서 다시 정점A로 .. 2022. 8. 9.
[기초] 정렬(sort) 알고리즘 정렬 정렬은 어떤 자료를 순서대로 배열하는 것을 의미합니다. 많은 알고리즘 문제에서 정렬을 사용하여 문제를 해결합니다. 정렬은 직접 구현하기 보다는 STL에 있는 sort를 사용하는 것이 좋습니다. (STL sort는 intro sort를 사용한다고 합니다. 매우 빠름) 참고 링크 https://www.acmicpc.net/board/view/16770 글 읽기 - stl의 sort 로는 시간초과가뜨는데 제가 틀린건가요? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net Introsort - Wikipedia Hybrid sorting algorithm Introsort or introspective sort is a hybrid sorting algorithm that provides .. 2022. 8. 8.
[기초] 알고리즘 수학2 4. 진법 변환 (Base Conversion) 4-1. 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될때 까지 나머지를 계속 구하면 됩니다. 예를 들어 11을 3진법으로 바꾸는 방법은 11/3 = 3 나머지는2 3/3 = 1 나머지는0 1/3 = 0 나머지는1 그래서 위로 보면 따라서 11은 3진법으로 102 입니다. 백준 진법 변환문제 10진법 수 N을 B진법으로 바꿔 출력하는 문제입니다. https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc... 2022. 8. 2.
[기초] 알고리즘 수학1 알고리즘을 풀 때 필요한 수학 내용을 다루고자 합니다. 1. 나머지 연산 (Modular Arthmetic) 첫번째로 자주 사용하는 내용입니다. (A+B) % C = ( (A%C) + (B%C) ) % C A+B에서 나머지 연산으로 위와 같은 식이 성립합니다. 증명은 아래 링크 참고 모듈러 연산의 성질과 증명 모듈러 연산의 성질과 증명 위와 같이 모듈러 연산은 나머지를 구하는 연산자이며 다음의 분배법칙이 모두 성립한다. 왜 이런지 궁금해서 계속 찾아보다가 간신히 찾은게 칸 아카데미에서 증명 sexycoder.tistory.com 다이나믹 프로그래밍 문제 중에 경우의 수를 구하는 문제일 때 경우의 수가 너무 큰 경우 또는 정수 범위를 넘어가는 경우 이 연산을 이용하여 풀이가 가능합니다. - 컴퓨터의 정수는.. 2022. 8. 1.
C++ 백준 BOJ 10870 피보나치 수 5 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하는 문제입니다. 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; int fibo(int num) { int result = num; if (result == 0) { return 0; } else if (result == 1) { return 1; } else { return fibo(result - 1) + fibo(result - 2); } } int .. 2022. 7. 27.
[기초] 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 동적 계획법이라고도 합니다. 동적 계획법 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아래 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있습니다. 1. Overlapping Subproblem : 겹치는 부분 문제 2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem 겹치는 작은 부분 문제로 나눠서 푸는 것이 핵심입니다. 문제 작은 문제 - 작은 문제 (두 작은 문제가 겹쳐야 됨) 먼저 피보나치 수를 예시로 들어 알아보면, - 피보나치 수 - F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2.. 2022. 7. 27.

티스토리툴바