므네모시아

2018 KAKAO BLIND RECRUITMENT 프렌즈 4블록 Level 2 문제 다음과 같은 블록이 있을 때, 같은 모양의 블록이 2x2 형태로 붙어 있다면 블록이 지워지며 점수를 얻을 수 있음 이 때, 2x2 배치가 여러개 있는 경우 한번에 지워진다. 한 번 지워지고 나면 남은 블록은 위에서 아래로 떨어지게 됨 빈 공간을 채운 후에 다시 2x2 형태의 블록이 모이면 다시 지워지고 떨어지는 것을 반복 지워지는 블록의 총 개수를 구하기 높이 m, 폭 n의 board n, m 은 2 이상 30 이하 board 는 길이 n인 문자열 m개의 배열로 주어짐. 블록을 나타내는 문자는 대문자 A~Z가 사용됨 Idea 보드판을 하나씩 체크하면서 4블록이 만들어지는지 확인하여 4블록이 만들어지면 체크해두기 한 열씩..

위클리 챌린지 전력망을 둘로 나누기 Level 2 문제 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있음 전선들 중 하나를 끊어 전력망 네트워크를 2개로 나누려 함 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추려고 함 두 전력망이 갖는 송전탑 개수의 차이(절대값) 반환하기 n은 2 이상 100 이하 wires는 길이가 n-1 인 2차원 배열 wires 원소는 [v1, v2] 2개의 자연수이며 각 수는 송전탑 번호를 의미 1

위클리 챌린지 교점에 별 만들기 Level 2 문제 Ax + By + C = 0 으로 표현할 수 있는 n 개의 직선이 주어짐 이 직선의 교점 중 정수 좌표에 별을 그리려고 함 line 길이(직선의 개수)는 2 이상 1,000 이하 line은 [A, B, C] 배열 A, B, C는 -100,000 이상 100,000 이하 정수 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음 A = 0 이면서 B = 0 인 경우는 주어지지 않음 정답은 1000*1000 크기 내로 표현됨 별이 한 개 이상 그려지는 입력만 주어짐 참고. Ax + By + E = 0 Cx + Dy + F = 0 두 직선의 교점이 발생하는 경우, 교점은 다음과 같음(아래 이미지 참고) 또한 AD - BC = 0 인 경우 두 직선은 평행 또는 ..

위클리 챌린지 피로도 Level 2 문제 던전을 시작하기 위해 필요한 “최소 필요 피로도” 던전을 마쳤을 때 소모되는 “소모 피로도” 가 있음 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데 이 던전을 최대한 많이 탐험하려함 현재 피로도 k와 던전 별 최소 피로도, 소모피로도 값이 주어질 때 탐험할 수 있는 최대 던전 수 구하기 k 는 1이상 5,000이하 던전의 개수는 1이상 8이하 dungeons 는 [“최소 필요 피로도”, “소모 피로도”] 배열임 최소 필요 피로도는 항상 소모 피로도 보다 크거나 같음 최소 필요 피로도와 소모 피로도는 1이상 1,000이하 서로 다른 던전의 피로도 값이 같을 수 있음 Idea 던전을 돌고 남은 값이 가장 큰 곳을 시도하는 것도 맞지 않으며, 최소 필요 피로도..

연습문제 카펫 Level 2 문제 테두리 한 줄은 갈색 중앙은 노란색 카펫 갈색 격자 수, 노란색 격자 수가 주어질 때 가로, 세로 크기를 반환 갈색 수 : 8 이상 5000 이하 노란색 수 : 1 이상 2,000,000 이하 가로 길이 >= 세로 길이 Idea 갈색은 테두리 1줄이므로 갈색 격자 수 나누기 2를 하면 가로 + 세로 -2 값이 됨 즉 갈색 격자 수 / 2 + 2 → 가로 + 세로 풀이 1 또한 중간에 노란색 줄이 1개라도 들어가야 하므로 갈색 테두리 길이는 세로와 가로 모두 최소 3의 값을 갖게 됨 이때 세로가 더 작거나 같으므로 세로를 3부터 시작해서 가로, 세로 조합을 구할 수 있음 또한 그에 따른 노란색의 가로, 세로길이는 (갈색 가로-2, 갈색 세로-2)이므로 노란색의 가로x세로의..

연습문제 H-Index Level 2 문제 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하 논문별 인용 횟수는 0회 이상 10,000회 이하 예. [3, 0, 6, 1, 5] → 3 이 과학자가 발표한 논문의 수는 5편이고, 그 중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3 Idea 논문을 인용 횟수에 따라 정렬하기 (그 이유는 아래 풀이 참고. 사실 이 문제는 정렬하지 않아도 풀 수는 있음!) 논문의 개수를 기준으로 확인하는데 (인용 가능한 횟수보다 논문의 개수가 더 ..

2021 KAKAO BLIND RECRUITMENT 합승 택시 요금 Level 2 문제 두 사람이 시작지점 S 로 부터 각자의 목적지 A, B에 도착할 때까지 택시 비용을 최소로 하려고 함 각 간선의 표시는 해당 도로를 사용하는데 드는 비용이며, 두 사람이 특정 위치까지 합승하여 비용을 절감할 수 있음 지점은 1에서 n개. n은 3이상 200이하 지점 s, a, b 는 1이상 n이하 자연수이며, 서로 다른 값 fares 는 [c, d, f] 로 이루어진 배열이며, c와 d 사이 요금이 f 라는 뜻 동일한 구간에 대한 요금 정보는 1번만 주어짐 f 는 1이상 100,000이하 Idea 시작 지점에서 모든 지점까지 최단 거리 구하기 모든 지점에서 A 까지, 모든 지점에서 B까지의 최단 거리 구하기 즉, S ..

연습문제 가장 먼 노드 Level 3 문제 n개의 노드가 있는 그래프 1번 노드에서 가장 멀리 떨어진 노드의 개수 구하기 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때, 간선의 개수가 가장 많은 노드들을 의미 n은 2이상 20,000이하 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있음 간선 정보는 [a, b] 배열로 제공되는데, 이는 a번 노드와 b번 노드 사이에 간선이 있다는 의미 Idea Dijkstra 연결된 간선의 개수에 따라 최단 경로가 결정되므로 모든 가중치는 1로 가정하여 각 노드의 비용을 구하면 됨 Code Swift 다익스트라 알고리즘으로 구현 ► 다익스트라 알고리즘 with Swift 다익스트라 알고리즘 with Swift 알고리즘 문제를 풀다가 최단 경로에 관한 ..

Summer/Winter Coding(~2018) 배달 Level 2 문제 N 개의 마을로 이루어짐 각 마을은 양방향 통행 가능한 도로로 연결되어 있고 각 도로 별로 걸리는 시간이 다름 1번 마을에서 배달 하려고 하는데 K 시간 이하로 배달이 가능한 마을만 주문을 받음 N은 1이상 50이하 road 길이(도로 정보 개수)는 1이상 2,000이하 road 는 길이가 3인 배열 (a, b, c) a, b (1이상 N이하, a != b) : 마을 번호, c (1이상 10,000이하 자연수) : 걸리는 시간 a, b를 연결하는 도로는 여러 개가 있을 수 있음 K 는 음식 배달이 가능한 시간. 1이상 500,000이하 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 반환 Idea 주어진 ..

2021 KAKAO BLIND RECRUITMENT 순위 검색 Level 2 문제 각 항목에 대해 하나 씩 선택해야 함 개발 언어 항목 cpp, java, python 지원 직군 항목 backend, frontend 지원 경력구분 항목 junior, senior 선호 소울 푸드 chicken, pizza 지원자 정보 info → 배열 크기는 1 이상 50,000 이하 → “개발언어 직군 경력 소울푸드 점수” 형식 → 이 때 점수는 1 이상 100,000 이하 → 스페이스 하나로 구분 [“java backend junior pizza 150”, ”python frontend senior chicken 210”] 요구 사항 query → 배열 크기는 1 이상 100,000 이하 → “개발언어 and 직군 a..