우리들의 T'SPACE

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

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으로 나눠지게 만든 ..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 제한 1 ≤ N ≤ 15 0 ≤ r, c < 2N 예제 입력 1 복사 2 3 1 예제 출력 1 복사 11 예제 입력 2 복사 3 7 7 예제 출력 ..

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 10 5 2 3 1 4 2 3 5 1 7 예제 출력 1 1 1 2 2 3 3 4 5 5 7 처음에는 당연히 vector에 수를 입력 받고 sort 함수로 정렬했다 근데 처음보는 Memory 초과... 제한된 메모리를 고려하고 있어서 어떻게 해야 할지 고민해보았습니다. 요즘 컴퓨터는 용량과 메모리가 크기 때문에 공간 복잡도를 크게 신경 쓰지 않아도 되지만, 가..

문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있..

문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K) 를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤K ≤N) 출력 (N K) 를 출력한다. 경우에 따라 우리가 빠르다고 생각하는 방식과 컴퓨터가 빠르다고 생각하는 기준은 다르다 우리는 흔히 고딩때 부터 확통을 하면 nCk를 계산 할 때 n!/k!(n-k)!을 활용해 이미 약분 된 공식을 습관화 해서 사용한다 그러나 컴퓨터는 이것 보다 파스칼의 삼각형을 이용한 방법을 선호한다 #include #include #include #include using namespace std; int pascal(int N, int k) { if (k == 0) { return 1; } if (k == 1) { ..