본문 바로가기

프로그래밍

 (100)
[C++] 백준 4949번: 균형잡힌 세상 이 문제는 이전에 풀었던 9012번: 괄호의 응용 문제다. 그 때와 다른 점은 대괄호가 추가 되었다는 점. 그래서 그에 대한 int 값 하나만 더 추가하면 되는거 아닌가?라고 생각했던 건 큰 오산이었다. ([)]이렇게 괄호 안에 불완전한 괄호가 있으면 안 된다. 위와 같은 방법으로는 판독할 수 없다. 하지만 생각할 수 있는 무적의 방법이 있다. 한 쌍을 이루는 괄호가 인접해 있는 경우를 계속 지우다 보면 균형잡힌 문장에서는 결국 모두 없어지지만 균형잡히지 않은 문장에서는 괄호가 남는 것을 알 수 있다. 이를 적용하면 된다. 말은 쉽지만 막상 이를 구현하려니 쉽지 않다. 걸핏하면 메모리 접근 오류가 발생하니 말이다. 단계별로 생각해보자. 1. 입력 이 문제에서 입력은 여러 줄에 걸쳐서 될 수도 있다. 하지..
[C++] 백준 2108번: 통계학 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 이번 문제는 네 가지의 출력을 해야한다. 그래서 각 출력을 작은 목표로 차근차근 풀어 나가면 다가가기 쉬울 것이다. 1. 산술평균 평균은 각 수를 입력받을 때, 입력받은 수를 합한 뒤 N으로 나눠 출력하면 된다. 이 때, 소숫점 아래 첫 번째 자리에서 반올림을 해야하므로 round 함수를 이용하고 int로 캐스팅하여 출력했다. 각 예제에 대한 출력도 옳게 나온다. #include #include using namespace std; int main() { int N; scan..
[C++] 백준 11866번: 요세푸스 문제 0 이 문제는 생각보다 어렵지 않다. 나는 vector를 이용해 1부터 N까지 push_back 하고, count라는 변수를 이용했다. count가 K가 되면 그 때 iterator가 가리키고 있던 요소를 출력하고 해당 요소를 erase한다. 그리고 count는 1이 된다. count가 다시 K가 될 때 까지 iterator는 다음 요소를 가리키고, 마지막 요소인 경우 처음을 가리킨다. #include #include using namespace std; int main() { int N, K; scanf("%d %d", &N, &K); vector P; for (int i = 0; i < N; i++) { P.push_back(i + 1); } int count = 1; printf("\n"); retur..
[C++] 백준 1966번: 프린터 큐 이 문제를 푸는데 조금 오랜 시간이 걸렸다. 왜냐하면 문제의 설명이 다소 이해하기 어려웠기 떄문이다. 처음에 풀었던 방식은 큐 배열을 이용해서 중요도에 따라 다른 큐에 순차적으로 집어넣는 방식으로 했지만, {1, 1, 9, 1, 1, 1}의 경우 0번 인덱스가 3번 인덱스보다 늦게 나와야 하므로 위의 방법은 틀리다. 그래서 리스트를 이용하여 맨 앞 인덱스의 중요도 보다 높은 인덱스가 있는지 스캔하며 있으면 push_back, pop_front를 이용해 문제에 주어진 작동방식대로 구현했다. goto 문을 유용하게 이용한 것 같다. #include #include using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int N, M;..
[C++] 백준 11650번: 좌표 정렬하기 이 문제를 처음 시도할 떄는 크기가 N인 두 개의 배열(X, Y)을 선언하고, X의 값 기준으로 정렬할 때 Y도 같이 바꾸는 방식으로 코드를 짰다. 그러나 예상했던 것처럼 시간초과가 떴다. #include using namespace std; int main() { int N, K; scanf("%d", &N); int* coords_x = new int[N]; int* coords_y = new int[N]; for (int i = 0; i < N; i++) { scanf("%d %d", coords_x + i, coords_y + i); } bool isSorted = false; while (!isSorted) { isSorted = true; for (int i = 1; i < N; i++) { ..
[C++] 비주얼스튜디오(VS)에서 발생하는 scanf 오류 해결하기 VS에서 scanf를 사용하려고 하면 아래와 같은 경고, 오류 메세지가 나온다. ⚠ C6031 반환 값이 무시되었습니다. 'scanf'. 🚫 C4996 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. 방법은 여러가지가 있다. 첫 번째로 위 오류 메세지에서 권고한 옵션을 적용하는 것이다. 코드 맨 위에 아래 코드를 한 줄 추가하면 C4996 오류 메세지가 없어지며 컴파일이 된다. #define _CRT_SECURE_NO_WARNINGS 하지만, C6031 경고 메세..
[C++] 백준 2775번: 부녀회장이 될테야 이 문제는 종이에 직접 적어가며 풀면 금방 푼다. 주어진 조건대로 수를 채워나가면 아래와 같은 표를 얻을 수 있다. 피보나치수열과 비슷한 느낌으로 수를 더해나간다. 맨 아래 0층은 1부터 쭉 수를 더해나가고, 각 층의 1호는 1로만 채워나간다. 연산은 1층의 2호부터 오른쪽으로 쭉 나아가며 한 층씩 올라가는데, 문제에서 주어진 것처럼 아래층의 해당 호수까지 숫자를 다 더해나가는 방법도 있지만, 바로 왼쪽과 아래칸의 합으로도 같은 결과를 얻을 수 있다. 바로 왼쪽 칸이 아래칸을 제외한 합이기 때문이다. 이를 활용하여, K와 N이 입력되면 (K + 1) * N의 크기를 갖는 배열을 선언하고 위의 규칙대로 끝까지 채워나간 뒤 마지막 칸의 값을 출력하면 된다. 이때 K + 1인 이유는 0층부터 시작하기 때문이다..
[C++] 백준 2869번: 달팽이는 올라가고 싶다 처음에는 이 문제를 시뮬레이션 해가며 답을 구하려고 했다. 아래처럼. #include using namespace std; int main() { long long A, B, V; scanf("%lld %lld %lld", &A, &B, &V); long long day = 1; long long H = 0; while (true) { H += A; if (H >= V) break; H -= B; day++; } printf("%lld\n", day); return 0; } 그러나 입력이 최대 10억까지 주어지고, 시간제한이 0.15초이므로 위의 코드는 시간초과가 발생한다. 그래서 식을 생각해야 하는데, 처음 생각해낸게 다음과 같다. (N - 1) (A - B) + A ≥ V 위에서 N은 나무 막대를 모..

티스토리툴바