코드 낙서장

문제 주소 : www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 확인 전 문제 최솟값 문제와 풀이 방식이 같은 문제입니다. [백준] 10868번 : 최솟값 문제 주소 : www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와.. latter2..

문제 주소 : www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 문제 확인 문제에서 쿼리의 개수가 최대 10만 개 이므로 단순히 계산으로 풀면 시간 초과가 나게 됩니다. 따라서 쿼리에 따른 처리법인 mo's 알고리즘 혹은 세그먼트 트리를 통해 풀 수 있습니다. 처음엔 mo's 알고리즘으로 쿼리를 전처리 후 정렬된 query 순으로 풀어나가는 방법으로 시도하였습니다. 기록해둔 쿼리의 범위가 현재 쿼리의 범위보다 넓은 경우엔 최..

문제 주소 : www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 확인 특별한 알고리즘이 필요한 문제는 아닙니다. 곱셈의 특성을 이용하여 풀면 쉽게 풀 수 있습니다. 문제에서 고려해야 할 점은 3가지입니다. 곱셈은 큰 수 끼리 곱할수록 더욱 커집니다. 두 음수의 곱은 양수입니다. A X 1 = A 입니다. => A + 1 이 A X 1 보다 크므로 이 수는 묶지 않습니다. 풀이 1, 2번 특성을 이용하기 위해서는 수열이 정렬되어 있어야 합니다. 간단하게 ..

문제 주소 : www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 문제 확인 수식의 길이가 짧기 때문에 간단하게 dfs로 풀 수 있습니다. 계산한 값이 기록되어 있어야 하므로 스텍과 함께 탐색합니다. 풀이 괄호 연산자는 우선순위를 부여하는 연산이므로 스텍을 이용하여 우선순위에 따라 계산을 진행할 수 있습니다. dfs 완전 탐색 시 2가지의 탐색 경로가 있습니다. 현재 수식을 계산합니다. = 괄호 없이 진행 or 현재 수식에 괄호를 둠 현재 수식을 계..

문제 주소 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 확인 모든 루프를 제거하고 조건식으로 풀 수 있는 문제이지만 이는 너무 시간이 많이 드는 작업이라 간단하게 dfs와 가지치기를 통해 풀었습니다. 조건식 풀이로 푼다면 시간과 메모리 모두 단축할 수 있습니다. 테트로미노는 최대 4개까지의 도형이므로 탐색이 깊지 않으므로 dfs로 풀어도 무방합니다. 주의해야 할 점은 다른 4가지의 테트로미노는 dfs로 풀 수 있지만 ㅜ 모양의 테트로미노는 dfs..

문제 주소 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 확인 bfs와 시뮬레이션 문제입니다. 배열 크기가 20x20으로 작기 때문에 가지치기 등을 이용하지 않고 문제를 풀 수 있습니다. 주의할 점은 먹이를 선정하는 기준이 아기 상어로부터의 거리, 거리가 같다면 위, 왼쪽 순으로 우선순위가 높습니다. 먹이를 먹으며 이동한 거리가 최종 결과가 됩니다. 풀이 큐를 통해서 bfs를 구현하고 visited 배열을 통해 여러 번 탐색하는 것을 방지합..

문제 주소 : www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 문제 확인 간단한 헤싱 문제 베열 인덱스 연산 대신 char 값을 그대로 인덱스로 사용해서 연산 횟수를 줄입니다. 풀이 fread를 통해 문자열을 한 번에 받아서 연산합니다. getchar을 통해 문자를 하나하나 입력받으면 보통 8ms~12ms가 나오게 됩니다. 문자를 입력받으면 그 문자의 아스키 값을 그대로 배열 인덱스로 사용하여 횟수를 체크합니다. 문자열 입력이 끝나면 최대 빈도수의 문자를 찾으며 같은 횟수의 문자가 나오면 d..

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545 2020 경북대학교 Goricon 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Python 2 PyPy2 C99 (Clang) C++98 (Clang) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++20 (Clang) C90 C2x C90 (Clang) C2x (Clang) www.acmicpc.net 문제 주소 : www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 ..

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545 2020 경북대학교 Goricon 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Python 2 PyPy2 C99 (Clang) C++98 (Clang) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++20 (Clang) C90 C2x C90 (Clang) C2x (Clang) www.acmicpc.net 문제 주소 : www.acmicpc.net/problem/20120 20120번: 호반우와 리듬게임 호반우가 모든 노트를 처리하면 3×1..

문제 주소 : www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 확인 특별한 알고리즘을 필요로 하는 문제는 아닙니다. 각 시험자의 응시자 수가 먼저 입력으로 주어지므로 배열에 저장해둔 후 감독관 정보를 받아 해결합니다. 각 시험장의 학생의 수가 총감독관이 감시 가능한 학생의 수를 넘는다면 계산이 필요하고 넘지 않는다면 1명을 추가합니다. 풀이 시험장에 있는 학생의 수가 총감독관이 감시할 수 있는 학..