알고리즘
-
숫자구슬 (boj 2613)알고리즘 2020. 6. 5. 01:46
숫자구슬 문제는 Parametric search 기법을 활용해서 풀 수 있어요. 용돈관리 문제랑 상당히 유사하고 코드도 거의 똑같습니다만.. 약간의 함정이 숨어있어요. M개의 그룹으로 나누고 각 그룹에 속한 원소의 수를 출력해줘야하는데 입력으로 8 5 1000 1 1 1 1 1 1 1 같이 극단적으로 큰 값을 주게 되면, 용돈관리 코드로는 1000 1 7 과 같이 그룹이 5개가 아니라 2개만 나오게 돼요 그래서 충분히 적은 수의 그룹을 만들 수 있더라도 M개에 미치지 못한다면 적절히 쪼개주는 작업이 필요하답니다. 쪼개는건 사실 쉬워요. 원소의 갯수가 2 이상인 그룹을 찾아서 1개씩 뽑아주면 됩니다. 뽑아주는 과정은 그룹의 갯수가 M이 될때까지 반복하는거구요. 코드 #include #include #inc..
-
용돈관리 (boj 6236)알고리즘 2020. 6. 5. 01:10
용돈관리 문제는 Parametric search 문제에요 Parametric search 는 Binary search 의 아이디어를 가져온 기법입니다. 지금 문제가 최소한의 K원을 찾는 문제니까 최대값은 N * 10000(일일 최대 사용금액), 최소값은 입력받은 일일금액 중 가장 큰 금액일거에요. 예를 들면 N이 100000, M이 1, 그리고 모든 일일금액이 10000원이라면 100000 * 10000 원을 한 번만 뽑아야하겠죠? 이는 100억이라서 int 의 범위를 넘어섭니다. 이를 먼저 주의해야하구요 최소값이 일일금액 중 가장 큰 금액이여야함은 자명하죠? 만약 K보다 큰 일일금액이 있다면 돈이 부족해서 은행에 돈을 넣었다가 다시 뽑아도 돈이 모자르니까요! Max = 100만 Min = 일일금액 중 ..
-
쿼드트리 (boj 1992)알고리즘 2020. 6. 5. 00:40
쿼드트리 문제는 Divide and conquer 를 활용하는 전형적인 문제입니다. 저의 경우에는 최초로 주어진 N을 size 로 두고, 반복문을 쭉 돌면서 다른 숫자가 있는지 찾아봅니다. 만약 다른 숫자가 발견되지 않고 모든 숫자가 같은 숫자라면 그 숫자로 압축이 가능합니다. (Best 케이스) 만약 다른 숫자가 발견된다면 이는 4등분해야하는 상황인 것이죠. 그렇다면 이들을 4등분한 지점을 left, top 으로 주고, size 를 절반으로 나눕니다. 그리고 위에서 했던 과정을 반복합니다. 코드 #include #include #include #include #include #define INF 987654321 int N; char map[70][70]; void DFS(int left, int to..
-
별 찍기 11 (boj 2448)알고리즘 2020. 6. 3. 22:04
별 찍기11 문제는 분할정복(Divide and conquer) 기법으로 문제를 해결할 수 있습니다. 삼각형 안에 작은 삼각형이 들어있는 꼴이기 때문입니다. 코드 #include #include #include #include #include #define INF 987654321 int N; char arr[5000][10000]; void drawTri(int y, int x) { sprintf(arr[y - 2] + x, " * "); sprintf(arr[y - 1] + x, " * * "); sprintf(arr[y] + x, "*****"); } void draw(int y, int x, int size) { if (size == 0) { drawTri(y, x); return; } int w..
-
트리의 높이와 너비 (boj 2250)알고리즘 2020. 6. 3. 17:52
트리의 높이와 너비 문제는 각 노드마다 자식 노드의 번호를 2개 주고, 이를 이진트리로 만든 뒤 DFS하는 문제에요 (Postorder search) 아래 코드를 보시면 children 배열에 자식노드를, parent 노드에 부모 노드를 저장하여 이진트리를 구성했어요. 그리고 빈 column 없이 트리를 구성해야한다는 점을 이용하면, 왼쪽 자식 서브 트리가 차지한 최대 column + 1 이 자기 자신의 노드 column index가 된다는 것을 알 수 있죠. 이후 오른쪽 자식노드의 maxIndex를 구하는 이유는 내 부모 노드의 위치를 결정해주어야 하기 때문이에요. DFS를 통해 재귀적으로 자식의 maxIndex 부터 알아가며 자기 자신의 위치를 결정하고, 그렇게 결정된 위치를 통해 레벨 별 최소 최대..
-
수학은 너무 쉬워 (boj 2904)알고리즘 2020. 6. 3. 16:32
수학은 너무 쉬워 문제는 소수를 구하고, 그 소수로 소인수분해를 하는 문제입니다. 최대 공약수라는게 모든 수가 갖고 있는 소수들의 곱으로 나타내지기 때문에 N개의 숫자를 각각 소인수분해하여 N개의 숫자를 통틀어서 어떤 소수를 몇개나 갖고있게 되는지 알게된다면 문제는 쉬워집니다. 예를 들어 8 24 9는 8 = 2^3 24 = 2^3 * 3 9 = 3^2 따라서 2가 6개, 3이 3개입니다. 숫자의 갯수가 3이므로 2를 2개씩 나눠가지고, 3을 한 개 씩 나눠가지면 최대공약수가 2^2 * 3 = 12가 됩니다. 그리고 움직이는 횟수는 9가 2를 두 개 받았고, 8이 3을 하나 받았으니 3개가 될거에요. #include #include #include #include #include int N; int ar..
-
MT 문제 (boj 10265)알고리즘 2020. 5. 16. 22:52오늘은 MT 문제에 대해 풀어볼게요 저는 문제를 딱 보는 순간 위상정렬(Topological sort) 문제라는게 보였어요 위 입력은 다 자기 자신을 지목한 상황이라 다른 사람에게 의존하지 않는 경우에요 세 번째 그림을 잘 보셔야해요 1은 2가 가야 가는 것이지만 2가 간다고 무조건 1이 가야하는건 아니에요. 따라서 세 번째 입력의 경우에도 답은 2명이 됩니다. 사실 여기까지는 단순한 위상정렬 문제로 보여요. 의존성이 없는 사람부터 버스에 태우면서 k명이 될때까지 최대한 태워보면 되니까요 하지만 예외가 있습니다. 이런 경우는 조금 다르죠 1, 2, 3 은 서로 의존적이라 다 같이 가거나 다 같이 안 갈 수 밖에 없어요. 따라서 답은 1명이 됩니다. 그냥 위상 정렬로 풀려고 해도 쉽지 않아요. 왜냐면 1,..
-
위상정렬알고리즘 2020. 5. 16. 16:30위상정렬은 작업간의 순서가 있어서 어떤 작업을 먼저 처리해야하는지 그 순서를 결정하는 문제에요 예를 들어 라면에 파를 넣어 끓여먹는 작업이라고 해볼게요 엄마한테 혼나지 않으려면 설거지까지 잘 해야해요..! 위상 정렬 문제 푸는 방법 1. 각 단계 별로 선행 과제의 갯수를 센다. 2. 선행과제가 없는 단계부터 처리하며 지워나간다. 3. 모든 단계를 처리한다. 1. 각 단계 별로 선행 과제의 갯수를 센다. 2. 선행과제가 없는 단계부터 처리하며 지워나간다. 2-1 2-2 2-3 3. 모두 처리한다. 어때요 쉽죠?