난쟁이 개발자

[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 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 ..

[level 3] 퍼즐 조각 채우기 - 84021 문제 링크 성능 요약 메모리: 10.3 MB, 시간: 0.53 ms 구분 코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS） 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 16일 23:11:26 문제 설명 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다. 조각은 한 번에 하나씩 채워 넣습니다. 조각을 회전시킬 수 있습니다. 조각을 뒤집을 수는 없습니다. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으..

[level 3] 억억단을 외우자 - 138475 문제 링크 성능 요약 메모리: 91.6 MB, 시간: 7822.86 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 15일 23:22:04 문제 설명 영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다. 억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다. 수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기..

[level 2] 2개 이하로 다른 비트 - 77885 문제 링크 성능 요약 메모리: 25.3 MB, 시간: 27.54 ms 구분 코딩테스트 연습 > 월간 코드 챌린지 시즌2 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 14일 16:41:23 문제 설명 양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다. x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 예를 들어, f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다. 수 비트 다른 비트의 개수 2 000...0010 3 000...0011 1 f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 ..

[level 2] 혼자서 하는 틱택토 - 160585 문제 링크 성능 요약 메모리: 10.2 MB, 시간: 0.02 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 제출 일자 2024년 04월 13일 21:52:59 문제 설명 틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다. 할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니..

뭔가 시뮬레이션은 어떻다기 보다는 많은 문제를 접하면서 내 생각대로 문제를 풀 수 있을까가 많이 중요해보임. 그렇기 때문에 기초가 더 중요한 챕터라고 생각함. 문제 65 - 이진 변환 반복하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 def solution(s): # [1] 0을 제거한 횟수, 2로 변환한 횟수 cnt_rm = cnt_2 = 0 # [2] s가 '1'이 아닌 동안 계속 반복 while s != "1" : # [3] 이진 변환 횟수 1 증가 cnt_2 += 1 # [4] s에서 '0'의 개수를 세어 cnt_rm 에 누적 cnt_..

문제 56 - 문자열 내 마음대로 정렬하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석하고 풀기 파이썬의 정렬 함수인 sorted() 함수를 사용해서 풀이 더보기 def solution(strings, n) : return sorted(strings, key=lambda x:(x[n], x)) 첫 번째 매개변수 strings는 정렬 대상, 두 번째 매개변수 key는 정렬 방법을 람다 함수로 전달한 것이다. lambda x:(x[n], x)는 x[n]을 기준으로 오름차순 정렬하겠다는 의미 N은 strings의 길이이다. sorted() 함수의 ..

정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말함. 정렬이 필요한 이유 데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있다. 그 예시로 이진 탐색 트리가 있다. 만약 오름 차순으로 정렬이 되어있는 데이터가 있다면, 큰 수를 찾을 때는 오른쪽부터 찾는 것이 훨씬 쉽고 빠르게 찾을 것이다. 정렬은 알고리즘의 효율을 크게 높여줍니다. 이번에 알아볼 정렬은 다음과 같다. 정렬 방법 최악의 경우 최선의 경우 특이점 삽입 정렬 O(N ^ 2) O(N) 데이터가 거의 정렬되어 있을 때는 최고의 성능을 발휘함. 병합 정렬 O(N log N) O(N log N) 안정적인 성능으로 정렬할 수 있다. 병합 과정에서 추가적인 메모리가 요구된다. 힙 정렬 O(N log N) O(N log N) 안정적인 성능으로 정..