코드 낙서장

문제 주소 : www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 문제 확인 DP 문제입니다. n과 n-1의 관계를 생각해보면 쉽게 풀 수 있습니다. n개의 막대에서 n 혹은 1 막대를 제거하면 n-1이 됩니다. n막대를 제거하면 1~n-1개의 막대를 나열하는 경우가 되며, 1 막대를 제거하면 2~n 막대를 나열하는 경우이며 모든 막대의 길이를 1 줄이게 되면 1~n-1 막대를 나열하는 경우와 같은 경우의 수를 가집니다. 이 특성을 이용해 n과 n-1..

문제 주소 : www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제 확인 간단한 시뮬레이션 문제입니다. 주어진대로 드래곤 커브 정보를 배열에 입력해둔 후 마지막에 정사각형 개수를 세면 됩니다. 풀이 드래곤 커브의 방향을 기록해야 다음 레벨의 드래곤 커브를 만들 수 있으므로 스택을 이용해서 기록합니다. 주의해야 할 점은 이전 단계 끝 지점에서 90도 방향으로 돌려야 하므로 스택에 저장된 정보를 top -> 0 순으로 읽어야 하며 모양..

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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/1831 코딩테스트 연습 - 4단 고음 4단 고음 I'm in my dream~↗ ~↗ ~↗ IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1]. [1] 견두헌, 배명 programmers.co.kr 문제 확인 간단하게 시뮬레이션처럼 풀 수 있지만 시간 초과가 납니다. 또한 단순 dfs로 풀어도 시간 초과가 나게 됩니다. 따라서 가지치기, 혹은 추가 조건을 통해서 통과할 수 있습니다. * 이후에 2개의 + 가 나와야 하므로 이를 이용하여 조건을 만들 수 있습니다. 하향식 dfs와 가지치기를 통해 풀 수 있습니다. 풀이 ..