난쟁이 개발자

[level 2] 거리두기 확인하기 - 81302 문제 링크 성능 요약 메모리: 10.2 MB, 시간: 0.17 ms 구분 코딩테스트 연습 > 2021 카카오 채용연계형 인턴십 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 21일 22:21:28 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있..

8주차까지는 저자와 함께, 이후는 혼자 완독에 성공하였다. 아직 완전한 뒷부분은 남겨두었지만, 일단 기초 부분에 해당하는 부분은 완독을 진행하였다. 많은 생각이 드는 1독 행군이었다. 나태해졌던 나를 다시 다독이면서 남은 5주를 계속해서 달렸다. 중간에 이해가 잘 가지 않아 딜레이 되었던 부분도 많이 생겼었고, 책의 내용을 그대로 옮겨 적는 습관도 최대한 내것으로 만든 후 재정립하려고 애썼으나 뭐 어떻게 되었는지는 잘 모르겠다. 일단 잠시 이 블로그를 진행하면서 어떻게 진행하였는지 등등을 얘기해볼까 한다. 우선 나는 바쁘다는 핑계로 중간중간 운동을 가지 않았었는데, 이제는 어지간하면 하루 2시간, 주 6일 이상 계속해서 가고 있다. 주 7일을 가고 싶었는데, 체력이 도저히 되지 않았다. 몸에서 운동 좀 ..

[level 2] 두 원 사이의 정수 쌍 - 181187 문제 링크 성능 요약 메모리: 10.2 MB, 시간: 628.39 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 20일 22:09:23 문제 설명 x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요. ※ 각 원 위의 점도 포함하여 셉니다. 제한 사항 1 ≤ r1 < r2 ≤ 1,000,000 입출력 예 r1 r2 result 2 3 20..

문제 설명 혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다. 숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다. 준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다. 그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적..

탐욕 알고리즘, 그리디 알고리즘 등으로 불리우는 탐욕법, 그리디... 그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택을 번복하지 않습니다. 이런 특성으로 '그리디 알고리즘은 지역 최적해를 추구한다' 라고 말하기도 합니다. 부분적으로는 최적해를 구한다고 할 순 있어도 전체적으로 최선의 해를 구했는가에 대해서는 확실한 상황은 아니다. 그리디 알고리즘으로 거스름돈 내어주기 손님에게 8원을 거슬러 줘야 하는데 동전 종류가 5, 4, 1원만 있는 상황이라면, 동전 개수가 가장 적게 만드는 알고리즘을 적용하였을 때의 답은 무엇일까? 값이 가장 큰 동전부터 주는 방법이 있다. 그리디 알고리즘은 현재 상황에서 최선의 선택을 하니 값이 가장 큰 동전부터 준다고 생각한다는 것이..

[Platinum IV] 불 끄기 - 14939 문제 링크 성능 요약 메모리: 114680 KB, 시간: 240 ms 분류 비트마스킹, 브루트포스 알고리즘, 그리디 알고리즘 제출 일자 2024년 4월 19일 17:07:51 문제 설명 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라 입력 10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다. 출력 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라...

[level 3] 미로 탈출 명령어 - 150365 문제 링크 성능 요약 메모리: 10.3 MB, 시간: 0.00 ms 구분 코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 17일 21:59:46 문제 설명 n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다. 단, 미로를 탈출하는 조건이 세 가지 있습니다. 격자의 바깥으로는 나갈 수 없습니다. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 ..

[level 3] 고고학 최고의 발견 - 131702 문제 링크 성능 요약 메모리: 10.2 MB, 시간: 6365.44 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 18일 22:21:05 문제 설명 고고학자인 혜선은 오래전부터 성궤의 행방을 추적해왔습니다. 그동안 그의 연구는 주류 학자들로부터 인정받지 못했었지만, 혜선이는 포기하지 않고 조사를 계속했고 마침내 성궤의 행방을 알아내었습니다. 그러나 오래전 누군가로부터 봉인된 성궤는 특별한 잠금장치에 의해 보호되고 있었습니다. 잠금장치는 일종의 퍼즐과 연결되어 퍼즐을 해결하면 열리는 것으로 보입니다. 퍼즐은 시계들이 행렬을 이루는 구조물인데 하나의 시계에 시곗바늘은 하나씩..

동적 계획법을 간단히 정의하면 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법이라고 할 수 있다. 하지만 부분 문제를 활용하여 전체 문제를 해결했다고 해서 반드시 동적 계획법이 효율적인 것은 아니다. 동적계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야 한다. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다. 점화식 세우기와 동적 계획법 동적 계획법으로 문제를 해결하는 절차는 다음과 같다. 문제를 해결하는 해가 이미 있다고 가정 종료 조건을 설정 과정 1, 2를 활용하여 점화식을 세움 점화식 구현 : 재귀 활용 점화식을 어..

[level 3] 숫자 타자 대회 - 136797 문제 링크 성능 요약 메모리: 285 MB, 시간: 2222.80 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 17일 23:31:06 문제 설명 위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다. 대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 ..