코달

문제 설명한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.사다리꼴의 윗변의 길이를 나타내는 정수 ..

문제 설명도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니..

문제https://www.acmicpc.net/problem/1060 풀이문제가 상당히 수학적이라 바로 이해하기 힘들다.풀이를 해보기 전에 이 글에서 사용할 용어 몇 가지를 약속하고 가자.숫자 집합 S = {s(0), s(1), ... , s(L-1)} 와 같은 형태이다.S 구간이란, S의 원소가 아닌 연속된 정수들의 구간이다.예를 들면 S = {s(0), s(1), s(2)} 일 때 S구간은 (1, s(0)), (s(0), s(1)), (s(1), s(2)), (s(2), 무한대) 가 있다.S구간의 오른쪽에 오는 원소가 s(n)이면 해당 S구간은 S(n)이라고도 한다.x가 포함된 좋은 구간의 갯수는 i다. 어떤 수가 더 좋은 수인지 판단하기 위해서는 어떤 수가 몇 개의 좋은 구간을 가지고 있는지 알아야..

문제https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위www.acmicpc.net 풀이처음엔 동전의 배열을 노드로 하는 그래프의 DFS 탐색으로 풀었다. 현재 노드는 현재 동전 배열이고, 인접한 노드들은 모든 행, 모든 열을 뒤집는 경우의 동전 배열이다.이런 식으로 풀어도 답은 나오지만, 메모리 초과 혹은 시간초과가 발생한다. 결국 다른 블로그 글을 보고 깨달았다.https://please-amend.tistory.com/175 백준 1285번 동전 뒤집기 - C++ 풀이1..

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 보드 자체가 탐색할 노드가 되어야 한다는 생각을 하기 어려웠다. 처음엔 보드에서 0을 움직이고 현재 보드가 정렬된 상태인지 검사하며 탐색할 생각을 했으나, 퍼즐을 가장 빠르게 푸는 방법을 생각해내지 못했다. 이 문제는 보드의 상태마다 0을 움직일 수 있는 경우의 수가 인접한 노드로 존재하는 그래프를 떠올리고, 모든 숫자가 제자리에 위치한 상태의 노드를 탐색해야하는 문제였다. 보드는 vector에 저장했다. 탐색에는 BFS알고리즘을 이용했다. 그 이유는 가장 빠르게..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 무엇보다 트리의 특성을 잘 이용하는 것이 중요한 문제입니다. 트리는 두 점 사이의 경로가 단 1개입니다. 따라서 가장 멀리 떨어진 두 점 (a, b)사이의 길이가 트리의 지름이 됩니다. 그렇다면 문제는 가장 멀리 떨어진 두 점 a와 b를 어떻게 찾을 것인가? 를 고민해야 합니다. 아래는 제가 맘대로 만든 트리입니다. 각 노드에는 번호가 적혀있고, 연결한 선분에는 길이가 ..

문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다. 예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다. 시추관은 위 그림처럼 설치한..

문제 설명 인사고과 문제 설명 완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다. 각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return ..

문제 설명 n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다. 단, 미로를 탈출하는 조건이 세 가지 있습니다. 격자의 바깥으로는 나갈 수 없습니다. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다. 이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다. l: 왼쪽으로 한 칸 이동 r: 오른쪽으로 한 칸 이동 u: 위쪽으로 한 칸 이동 d: 아래쪽으로 한 칸 이동 예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, ..

문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.) 초기에, 1, 2, 6, 7..