우리들의 T'SPACE

삽입 정렬은 간단하면서도 직관적인 정렬 알고리즘입니다. 이 알고리즘은 배열의 모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 각 요소를 적절한 위치에 삽입하는 방식으로 동작합니다. 이 과정을 통해 배열이 점차적으로 정렬됩니다. 삽입 정렬의 작동 과정은 다음과 같습니다: 배열의 두 번째 요소부터 시작하여, 해당 요소가 이전에 정렬된 배열 부분에 삽입될 올바른 위치를 찾습니다. 이 요소를 그 위치에 삽입하고, 필요한 경우 나머지 요소들을 오른쪽으로 이동시켜 자리를 마련합니다. 배열의 모든 요소에 대해 이 과정을 반복합니다. 삽입정렬의 장점: 간단하고 이해하기 쉽습니다: 코드 구현이 간단하여 초보자도 쉽게 이해하고 구현할 수 있습니다. 안정적인 정렬 방법입니다: 같은 값의 요소가 입력에 주어진 순서를..

버블 정렬(Bubble Sort) - 단순하지만 효율적이지 않은 정렬 알고리즘 버블 정렬이란? 버블 정렬은 가장 기본적이고 직관적인 정렬 알고리즘 중 하나입니다. 배열의 인접한 두 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환하는 방식으로 동작합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. 버블 정렬의 작동 원리 배열의 첫 번째 원소와 두 번째 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환합니다. 이 과정을 배열의 마지막 원소까지 반복합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. 마지막 원소부터 차례대로 정렬이 완료되어, 가장 큰 원소가 배열의 끝으로 이동합니다. 버블 정렬의 장단점 장점: 구현이 매우 단순하여 이해하기 쉽습니다. ..

Binary Search는 정렬된 배열 내에서 대상 요소를 효율적으로 검색할 수 있는 강력한 알고리즘입니다. 이 알고리즘은 검색 공간을 반복적으로 절반씩 나누는 방식으로 작동하므로, 큰 규모의 정렬된 데이터셋에서도 매우 빠르게 동작합니다. 전제 조건: 정렬된 배열 Binary Search를 사용하기 위해서는 배열이 사전에 정렬되어 있어야 합니다. 배열이 정렬되어 있지 않다면 Binary Search가 올바르게 작동하지 않으며, 잘못된 결과를 얻을 수 있습니다. 이러한 요구 사항이 필요한 이유는 Binary Search가 배열의 정렬 순서에 의존하기 때문입니다. 이를 통해 알고리즘은 현재 검색 공간의 중간 요소와 대상 요소를 비교하여 다음에 검색할 절반을 결정할 수 있습니다. 그래서 Sorting이 중요함..

* 문제 이해와 해결 과정 땅을 고르게 만들어야 함. 땅을 고르게 만드는 방법에는 2가지가 존재하며 각각 소요시간이 다름. 땅의 높이는 0~256이 될 수 있음. 나에게 주어지는 것은 땅의 가로, 세로 길이와 각 땅의 높이, 인벤토리에 보관 중인 블럭들임. 첫 시도는 실패했는데, 2가지 작업을 동시에 해줄 수 있다는 점과 높이가 0~256일 때의 모든 경우를 고려하여 탐색해야 한다는 점을 간과했다. 결국 문제에서 원하는 것은 최소 시간과 높이다. 높이가 0일 때 시간이 가장 적게 들 수도 있고, 높이가 256일 때 시간이 가장 적게 들 수도 있다. 1)블럭을 파내어 인벤토리에 넣는 작업과 2)인벤토리에 있는 블럭을 꺼내어 쌓는 작업을 적절하게 사용해야한다는 뜻이다. 그래서 높이가 0일때 부터 256일때 ..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net * 해결 아이디어 N명의 사람의 15%를 구한 후, 1~30점 난이도 의견 배열의 앞과 뒤에서 1씩 빼준다. 그려면 30% 절사평균이 구현되며, 배열에 들어있는 값들을 평균내어 문제에 알맞게 출력하면 된다. #include #include #include #include #include #include #include #include #include #include #..

위와같은 두 행렬들이 있다하자 그러면 행렬 A와B의 곲 C는 다음과 같이 표현된다 그러면 아래와같이 이해될 수 있다 이 행렬의 곱 알고리즘의 시간 복잡도는 O(n^3)의 복잡도를 가진다 그래서 매우 큰 행렬들의 곱을 계산할 때는 매우 버거워진다 그의 결과로 분할정복의 한 방법인 Strassen 알고리즘이 나왔다 각 행렬들을 이렇게 4분할을 해보자 그러면 이렇게 계산해도 결과가 나온다 하지만 이건 또 결국 계산을 하다보면 O(n^3)의 복잡도를 가진다 그럼 Strassen 알고리즘은 어떻게 분할하냐? 위의 행렬들을 정의 해준다 그럼 아래와 같은 곱이 성립 한다 행렬의 곱셈을 한번 줄이고! 덧셈을 늘렸다! 그래서 O(n^3)->O(n^2) 로 수렴하게 된다 왜냐 행렬의 곱셈은 for문 골치거리이기 때문에 그..

C++ 입출력 최적화: sync_with_stdio와 cin.tie 이해하기 코딩테스트에서 표준 입출력을 사용할 때 주로 scanf/printf 또는 cin/cout을 사용합니다. C++에서는 string과 같은 편의 기능을 제공하는 cin/cout을 주로 사용하게 됩니다. 그러나 주의해야 할 점은 cin/cout을 사용할 때 시간초과를 막기 위해 특별한 조치가 필요하다는 점입니다. 1. ios::sync_with_stdio(0)과 cin.tie(0) C++에서는 입출력 버퍼를 동기화하는 작업이 기본적으로 수행됩니다. 그러나 이 작업은 입출력의 양이 많을 때 시간을 소비할 수 있습니다. 따라서, 입출력 작업이 많은 경우에는 이 동기화 작업을 해제하는 것이 좋습니다. 동기화 작업 해제를 위해 아래의 두 명..

문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 예제 입력 1 복사 55-50+40 예제 출력 1 복사 -35 예제 입력 2 복사 10+20+30+4..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 1 예제 입력 2 복사 10 예제 출력 2 복사 3 힌트 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. 진짜 다양한 방법으로 생각해봤는데 우선 3으로 나누는게 무조건 이득이라 생각해 3으로 나눠지게 만든 ..

문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개..