오구리의 DevLog

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

▶야근 지수 - 연습문제 (level 3) ▶문제 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. ▶제한사항 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니다. ▶입출력 예 입출력 예 #1 n=4 일 때, 남은 일의 작업량..

▶행렬과 연산 - 2022 카카오 테크 인턴십 (level 4) ▶문제 2022.08.28 - [Programmers Code/Level 4] - [Programmers] level4 - 행렬과 연산 (Python) : 2022 카카오 테크 인턴십 (75점 / 100점) [Programmers] level4 - 행렬과 연산 (Python) : 2022 카카오 테크 인턴십 (75점 / 100점) ▶행렬과 연산 - 2022 카카오 테크 인턴십 (level 4) ▶문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다. ShiftRow dhalsdl12.tistory.com 지난번에 이 문제를 풀었는데, 효율성 테스트에서 3개의 te..

▶기둥과 보 설치 (Python) : 2020 KAKAO BLIND RECRUITMENT (level 3) ▶문제 빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션할 수 있는 프로그램을 만들고 있습니다. 프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다..

▶징검다리 건너기 - 2019 카카오 테크 인턴십 (level 3) ▶문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그다음 디딤돌로 한 번에 여러 칸을 건너뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가..

▶코딩 테스트 공부 - 2022 카카오 테크 인턴십 (level 3) ▶문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다. A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다. B라는 문제가 알고력 10, 코딩력 20을 요구한..

▶행렬과 연산 - 2022 카카오 테크 인턴십 (level 4) ▶문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다. ShiftRow 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.) ShiftRow의 예 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다. 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다. Rotate 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 ..

▶단어 퍼즐 - 팁스타운 (level 4) ▶문제 단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 "ba", "na", "n", "a" 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개 만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 ..

▶베스트 앨범 - 해시 (level 3) ▶문제 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. ▶제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는..

▶등굣길 - 동적계획법 (level 3) ▶문제 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. ▶제한사항 ..

▶파괴되지 않은 건물 - 2022 KAKAO BLIND RECRUITMENT (level 3) ▶풀이 처음에 아주 간단한 문제라 생각하고 풀었다. 정확성 테스트는 다 맞게 나오는데 효율성에서 시간 초과가 떴다... 카카오에서 이렇게 쉬운 문제를 낼리가 없지ㅋ 효율성 테스트 실패 코드...ㅜ def solution(board, skill): answer = 0 building = board for s in skill: if s[0] == 1: for i in range(s[1], s[3]+1): for j in range(s[2], s[4]+1): building[i][j] -= s[5] elif s[0] == 2: for i in range(s[1], s[3]+1): for j in range(s[2],..

▶올바른 괄호의 갯수 - 연습문제 (level 4) ▶문제 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요. ▶제한사항 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수 ▶출력 n result 2 2 3 5 ▶입출력 예 설명 입출력 예 #1 2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다. 입출력 예 #2 3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만..

▶도둑질 - 동적계획법 (level 4) ▶문제 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. ▶제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. ▶출력 money return [1,2,3,1] 4 ▶풀이 dp를 이용해서 푸는 문제이지만 조건이 두 개다. 그냥 일자로 나열된 집을 도둑질한다면 아무 조건..

▶네트워크 - DFS/BFS (level 3) ▶문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. ▶제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번..

▶정수 삼각형 - 동적계획법 (level 3) ▶문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. ▶제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. ▶출력 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5,..