코드 낙서장

활용 문제 : www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 백준 문제와 테스트 케이스를 이용해서 속도 비교를 해 보았습니다. pair의 경우 객체 메서드 생성에 의해 조금 느린 것을 볼 수 있지만 거의 차이가 보이지 않아 간단한 벤치마킹 코드를 작성해서 비교해 보았습니다. 백준 테스트 케이스를 얻을 수 없어서 std::sort 함수를 통해 성능을 비교하도록 하겠습니다. sort 함수에서 2차원 배열을 사용하기 위해서는..

문제 주소 : 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/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 백준 사이트에서 설명을 잘해 두었습니다. 배열에서 부분합, 부분 최대/최소 등 범위 참조 연산이 자주 일어날 때 자주 사용하는 자료구조입니다. 미리 배열에 대하여 세그먼트 트리를 생성해 둔 후 미리 계산해둔 값을 참고하여 O(n)의 시간을 O(log n) 만큼으로 줄여줍니다. 일반적으로 세그먼트 트리에서 노드들은 다음과 같은..

문제 주소 : 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/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제 확인 시뮬레이션 문제입니다. dfs방식으로 주어진 방식대로 풀어주면 간단하게 풀 수 있습니다. 주의해야 할 점은 dfs 단계마다 맵 정보를 기록 해 두어야 정확한 답을 구할 수 있습니다. 풀이 방향 전환에 필요한 dx, dy 배열을 선언하고 정해진 물고기의 번호 순서대로 움직여야 하므로 해쉬 기법을 사용합니다. dfs 단계마다 맵 정보를 기록하기 위해 임시 배열을 선언하고 ..

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

Wiki : en.wikipedia.org/wiki/Binomial_heap Binomial heap - Wikipedia In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priori en.wikipedia.org Visualization : www.cs.usfca.edu/~galles/visualization/..

문제 주소 : 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..