본문 바로가기
[C++] 백준 18111번: 마인크래프트 문제 바로가기 이 문제 걸핏보면 어려워 보이지만 처음 구현했을 때는 술술 나올 정도로 어렵진 않았다. 알고리즘 분류가 브루트포스 알고리즘으로 돼 있길래, 맘 편하게 코드를 짰다. worst case도 입력해주며 코드를 고쳐나갔다. 누락됐던 블럭을 부수면 인벤토리에 블럭을 추가하는 것도 추가시키고, 블럭이 지금 모자르다고 바로 break를 걸었던 것도 최종 결과에 따라 반영했다. 인벤토리에 블럭을 증가/감소시킨 양 만큼 변화하도록 수정하는 등 다양한 수정을 거쳤다. 코드에 주석까지 하나하나 달아가며 검토했지만, 제출한 코드의 결과는 "틀렸습니다" 아래가 해당 코드다. #include #include int main() { int N, M, B; scanf("%d %d %d", &N, &M, &B); int..
[C] 백준 풀 때 Tip. 답안 검토 시 파일로 입력 넣기 백준 풀면서 답안을 검토할 때 하는 것 중 하나가 입력의 최대치를 넣어보는 것이다. 이를 통해 시간초과가 발생할지, 값이 이상해지지는 않는지 확인할 수 있다. 하지만, 입력이 100만개씩 되는 경우가 있는데 이를 복사&붙여넣기를 하거나 일일이 입력할 수도 없는 노릇이다. 이 때 파일을 통해 입력하면 편하다. 1. 입력파일 생성하기 우선, 입력에 쓰일 파일을 만들 코드를 짜야한다. 18111번: 마인크래프트를 예시로 하면, 입력 코드를 아래처럼 구성할 수 있다. #include int main() { printf("500 500 6500000\n"); for (int i = 1; i [원하는 경로]\Input.txt 왼쪽 경로는 해당 소스파일을 컴파일 한 뒤의 생성된 파일이다. 가운데에는 '>'를 공백을 ..
[C++] 백준 2805번: 나무 자르기 문제 바로가기 이 문제는 1654번: 랜선 자르기와 비슷하다. 그 때에도 탈출조건 때문에 애를 먹었다. 하지만 그 때 되짚어 봤던 것처럼, HIGH(또는 RIGHT)에는 MID - 1을, LOW(또는 LEFT)에는 MID + 1을 대입하고 while문의 조건을 HIGH ≥ LOW로 하면 무한루프에 빠지지 않는다. 또는 HIGH, LOW = MID로 하되, HIGH > LOW + 1을 while문 조건으로 해도 상관없다. 둘은 사실상 같은거다. 이 문제를 풀면서 이를 잊고 있다가 무한루프로 인한 시간초과가 두 번이나 발생했다. 공식처럼 익혀 놓아야겠다. #include int main() { int N, M, MID; scanf( "%d %d", &N, &M); int LOW = 0; int HIGH = ..
[C++] 백준 15829번: Hashing 1. Small (50점) 서브태스크 Small(50 점)에 대한 해답은 어렵지 않다. 각 문자에 대해서 int 형식으로 변환하여 31를 인덱스만큼 거듭제곱한 것을 곱하고 합한 값을 1234567891로 나눈 나머지를 출력하면 된다. 1 ≤ L ≤ 5일 때는 int로도 충분히 풀 수 있을 정도로 숫자가 크지 않다. #include using namespace std; int pow(int num, int p) { int result = 1; for (int i = 0; i < p; i++) { result *= num; } return result; } int main() { int L; scanf("%d", &L); char* str = new char[L + 1]; scanf("%s", str); i..
[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은 나무 막대를 모..

티스토리툴바