Algorithm
3392 화성지도
위 이미지와 같이 항상 x축, y축과 평행한 변을 가진 직사각형 들의 면적을 출력하는 문제입니다. 예시로 든 이미지를 좌표평면상에 그려보면 위와 같은 그림이 되며, 각 직사각형의 면적에 해당하는 부분에 1을 더하면 오른쪽과 같이 나타납니다. 1 이상의 값이 들어간 모든 블럭의 값을 합하면 면적이 되는 것을 알 수 있습니다. 단순하게 직사각형을 모두 탐색한다면 최대 30000의 좌표를 가지기 때문에 30000 * 30000 = 9억 으로 시간이 너무 많이 들게됩니다. 여기서 해결해야하는 부분을 살펴봅시다. 직사각형 내부의 숫자를 어떻게 갱신할 것인가. 1이상의 값을 가지는 블럭의 수를 어떻게 세야하는가? 크게 두 가지의 문제를 해결해야함을 알 수 있습니다. 해결법 숫자를 갱신하는 조건은 범위내의 면적에 숫..
p384 ( Slurpys )
Slump 조건 1. D or E로 시작 2. 첫 글자 이후엔 F가 1개 이상은 반드시 옴. 3. F이후에 Slump또는 G가 와야함 Slimp 조건 1. A로 시작. 2. 총 두글자라면 반드시 AH여야함. 3. 길이가 2 이상이면 두 가지 경우가 있음. -> AB(Slimp)C -> A(Slump)C Slurpy 조건 Slimp에 이어서 Slump가 나오는 문자열 조건에따라 주어진 문자열이 Slurpy가 맞는지 확인하는 문제입니다. isSlump()와 isSlimp() 함수를 재귀적으로 작동하게 만들어서 풀었습니다. 먼저 처음으로 주어진 문자열에서 D 또는 E의 바로 이전에 C가 있는 경우를 찾아서 전체 문자열을 Slimp와 Slump로 나눴습니다. Slump의 경우 F가 등장한 경우 계속해서 진행하며..
p10010 ( Where's Waldorf )
문제 문자들이 적혀있는 표( 배열, 격자 ) 에서 왼쪽 위에서부터 오른쪽 밑으로 탐색하여 찾고자 하는 문자열을 8방향으로 탐색, 탐색에 성공하면 현재 위치를 출력하는 문제이다. 추가조건으로 문자의 대소문자를 구분하지 않는다. 위의 예제에 대하여 나타내면 다음과 같다. 입력되는 격자의 최대 크기가 50 x 50이고, 찾는 문자열의 길이는 최대 20이다. 격자의 각 위치마다 8방향을 탐색하고, 최대 길이가 20이므로 단순하게 50 x 50 x 8 x 20으로 계산을 해보더라도 40만이다. 그냥 좌측 위를 ( 0, 0 )으로 두고 오른쪽 아래로 나아가며 8방향 탐색을 하면 된다고 판단했다. 소스코드. 더보기 #include #include using namespace std; #pragma warning(di..
p10150 ( Doublets )
문제 동일한 길이의 두 문자열의 차이가 한 글자만 있는 경우 Doublet이라 한다. 단어사전에 해당하는 문자열이 한줄에 하나씩 나열되며, 두 문자열이 공백을 기준으로 나뉘어져 입력이 들어오게되면 출력을 해야함을 의미한다. 출력은 입력으로 들어온 두 문자열 중에서 앞의 것을 시작 단어, 뒤의 것을 끝 단어로 둔다. 시작단어부터 현재 단어와 Doublet관계에 있는 단어를 타고 다음 단어로 이동이 가능하다. 끝 단어에 도착하게 되면 지금껏 타고온 단어들을 순서대로 출력해야한다. (단, 제일 빠르게 끝 단어에 도착한 순서를 출력해야한다. ) 문자열의 최대길이는 16이며, 입력되는 단어의 최대개수는 25143개 이다. booster rooster boosted roaster coasted roasted coa..
p679 ( Dropping Balls )
FBT, 완전 이진 트리에 대하여 푸는 문제. FBT의 모든 노드는 초기값이 false로 세팅되어있고, 공은 루트노드부터 떨어진다. 공이 거쳐간 노드는 값이 반전( false라면 true로, true라면 false로 ) 되며, false였다면 왼쪽으로 공이 떨어지고 true면 오른쪽으로 떨어진다. 트리의 높이와 공을 떨어뜨린 횟수가 주어졌을 때, 마지막에 떨어진 공이 위치하는 노드의 값을 출력하는 문제. 공은 리프노드까지 떨어진다. 풀이 더보기 위와 같은 트리에서 공을 떨어트릴 수 있는 기회는 총 8번이다. ( 리프노드까지 공이 떨어지므로 ) 이를 숫자로 표현하여 다시 나타내보면 다음과 같다. 잘 보면 루트노드를 기준으로 왼쪽 서브트리는 모두 홀수의 순서값을 가지고, 오른쪽 서브트리는 짝수의 순서값을 가..
p10137 ( The Trip )
여행경비로 지출된 총 금액을 모든 인원이 최대한 균등하게 돈을 지출하도록 만드는 문제 돈을 많이 낸 사람들과 작게 낸 사람들 중 평균값과의 차이가 더 큰 만큼 돈을 이동해야한다. 예를 들어 13.01 13 3.01 3 이렇게 돈을 냈다고 가정했을 때, 총 지출한 돈의 양은 32.02 달러이다. 이를 4로 나누게 되면 8..005달러가 되지만, 0.5센트는 없으므로 8달러와 8.01달러로 평균값을 둔다. 8달러와 8.01달러 중 작은 금액에 해당하는 8달러보다 작게낸 사람은 3.01달러와 3달러가 되고, 8.01달러보다 많이 낸 사람은 13.01달러와 13달러가 된다. 적게낸 사람들 각각 평균값과의 차이는 4.99달러, 5달러이고 많이낸 사람들 각각 평균값과의 차이는 5달러, 4.99달러이다. 적게낸 사람..
p100 ( 3n + 1)
두 수 i, j 를 입력받은 다음, 그 사이 값에 대하여 규칙에 따라 연산을 했을 때, 제일 연산을 많이 수행했을 때의 횟수를 출력하는 문제. 규칙 홀수이면 *3을 하고 1을 더한다. 짝수이면 /2를 한다 더보기 #include #include #pragma warning(disable:4996); using namespace std; int solve(int num) { int cnt = 1; while (num > 1) { cnt++; if (num % 2 == 0) { num /= 2; } else { num = num * 3 + 1; } } return cnt; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); in..
Dynamic Sets (계속 추가될 예정 )
Dynamic Set? Dynamic Set( 동적 집합 )이란 집합의 요소들이 계속해서 변화하는 집합입니다. Dynamic Set의 자료구조는 여러개가 존재합니다. BST : 이진 탐색 트리 AVL Tree : 균형잡힌 이진 탐색 트리 2-3 Tree Red-Black Tree Splay Tree ....? 동적 집합에서 몇몇의 쿼리와 수정 연산자를 지원하며, 모두 O(log n)의 시간복잡도를 가져야합니다. Search(S, k) : S 내에서 key가 k의 값을 가지는 원소 탐색 Minimum(S) : S 내에서 key값이 가장 작은 값을 가지는 원소 Maximum(S) : S 내에서 key값이 가장 큰 값을 가지는 원소 Successor(S, x) : S 내에서 x의 key 값을 가지는 원소의 다..
2042. 구간 합 구하기
과거에 통과했던 문젠데 재채점을 하면서 `틀렸습니다!`로 바뀌었다. 세그먼트 트리를 이용한 풀이였던 것으로 기억하는데.. 일단 최대 최소값이 각각 8바이트의 정수값을 가진다. 과거에도 그렇고 이번에도 그렇고 많이 고통받은 문제다. 재채점에서 틀렸습니다를 받은 이유를 살펴보니 c의 입력이 int값을 넘어선 값을 받을수도 있지만, 기존에는 int로 해놔서 그런걸로 밝혀졌다.. 더보기 더보기 import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { public static int N, M, K; public static BigInteger ans; public static BigInteger[] arr; publ..
14889. 스타트와 링크
N x N 격자에 각 i 번호의 선수와 j 번호의 선수가 같은 팀 일때의 점수를 표기하고, 두 팀의 점수차가 최소가 되게 팀을 구성했을 때의 최소값을 출력하는 문제이다. N의 수가 최대 20이라서 최악의 경우가 20명중에 10명뽑는 경우의 수가 된다. `20 C 10 = 184756` 이므로 브루트포스와 백트래킹을 쓰면 풀릴 것 같았다. 더보기 더보기 import java.io.*; import java.util.*; import java.util.List; public class Main { public static int ans, N; public static int[][] MAP; public static boolean[] chk; public static void InputData() { try(..