Computer/알고리즘&백준

[백준][C++] 요세푸스 문제 0

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 큐를 이용하는 문제 비슷한 문제 계속 풀다보니 감이 잡혀서 쉽게 풀었다. 먼저 큐에 1부터 n까지의 숫자를 저장해둔 후, k-1번째 숫자까지 뒤로 push한 뒤 pop한다. 그런 뒤에 가장 앞에 오는 숫자가 k번째 숫자이므로 우리가 원하는 수열의 숫자가 된다. 따라서 따로 벡터나 배열에 옮겨담은 후 pop한다. 이 과정을 큐가 빌 때까지 반복 #include #include int main() { std::queue que; std::vector vec; int n, k; std:..

[백준][C++] 1874 스택 수열

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 역시 스택을 사용하는 문제인데 처음에 딱 문제를 봤을 땐 어떻게 코드를 짜야할지 모르겠어서 좀 당황했다 풀고나서 다시 보면 쉽지만... 처음 풀 땐 내가 이 정도로 빡대가리였나 좀 고민할뻔 함 #include #include #include int main() { std::stack stack; std::vector..

[백준][C++] 4949 균형잡힌 세상

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 스택을 활용하는 문제 #include #include #include int main() { std::string str; std::stack stack; while (1) { std::getline(std::cin, str, '.'); //.을 만날 때까지 받아오기 std::cin.get(); //개행문자 지우기 str.append(1, '.'); if (str[0] == ..

[백준][알고리즘][C++] 2750 수 정렬하기, 버블 정렬, 삽입 정렬

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1) 버블 정렬 알고리즘(Bubble sorting) 버블 정렬은 인접한 두 원소를 비교하여 자리를 교환해가는 알고리즘이다. 시간 복잡도는 O(n^2) (이중 for루프) #include #include using std::vector; int main() { int n; std::cin >> n; vector arr(n); for (int i = 0; i > ar..

[백준][C++] 2738 행렬 덧셈

https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 2차원 배열을 이용하는 문제이다. n과 m의 범위가 100 이하이므로 굳이 동적할당을 할 필요는 없지만 연습을 위해 동적할당을 써 보았다. 2차원 배열은 배열의 배열로 이해할 수 있다는 점을 이용하여 구현할 수 있다. 즉 포인터 배열을 만들고, 각각의 원소들이 또 다른 배열을 가리키도록 하여 구현할 수 있다. (물론 실제 2차원 배열의 메모리는 연속된 주소 값을 갖기 때문에 이렇게 ..

[백준] [C++] 11729 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀를 이용하는 문제다. 단계별 풀기를 하고 있는데, 아직 이 문제를 풀 순서는 아니지만 재귀 배운 김에 풀어봤다. 이 문제의 핵심 포인트는 다음과 같다. n개의 원반을 A에서 C로 옮기기 위해서는 n-1개의 원반을 A에서 B로 옮기고, 가장 밑의 원반을 A에서 C로 옮긴 후, 다시 n-1개의 원반을 B에서 C로 옮겨야 한다. 따라서 재귀로 귀결되는 것이다. 사실 이 문제는 너무 유명..

[알고리즘] 시간복잡도와 공간복잡도, 빅-오(Big-Oh) 표기법

안녕하세요, katte입니다. 이번 글에서는 알고리즘을 평가하는 기준인 시간복잡도와 공간복잡도, 그리고 시간복잡도를 나타내기 위한 방법인 빅-오 표기법에 대해 알아보도록 하겠습니다. 알고리즘을 평가하는 기준으로는 시간복잡도와 공간복잡도 두 가지가 있습니다. 시간복잡도: 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느린가? 연산 횟수와 관련 공간복잡도: 어떤 알고리즘이 어떠한 상황에서 더 메모리를 적게 사용하고 많이 사용하는가? 일반적으로는 공간복잡도보다 시간복잡도를 더 우선시합니다. 시간복잡도의 경우에는 데이터 양에 따른 연산 횟수와 관련이 있습니다. 즉, 데이터의 양이 n일 때, 연산횟수 T(n)이 어떤 형태를 띄는가에 관심을 둡니다. 이때 중요한 것은, 데이터 양 n이 증가함에 따라 T(n)이 어느..

[백준] [C++] 9020 골드바흐의 추측

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 두 가지 방법으로 풀었다. 첫 번째 방법은 숫자 n을 받아서 2로 나눈 후 단순하게 소수 판별을 하고, 소수가 아니라면 증감을 시키는 방법을 사용하였다. //개별 수에 대해서 소수 판별을 하는 방법 #include bool prime(int n) //소수 판별 함수 { for (int i = 2; i * i > loop; while (loop--) { int n; std::ci..