난쟁이 개발자

[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) 안정적인 성능으로 정..

완전 탐색 : 깊이 우선 탐색, 너비 우선 탐색과 같이 데이터를 전부 확인하는 탐색 방법을 의미한다. 우리는 이 글에서 공부해 볼 탐색 방법은 백트래킹으로 지난 깊이 우선 탐색, 너비 우선 탐색을 공부하던 중 탐색 진행이 더이상 불가능해 졌을 때 되돌아 오는 것을 착안해서 가능성이 없는 곳에서는 되돌아 가고, 가능성이 있는 곳을 탐색하는 알고리즘이다. 유망 함수 백트래킹 알고리즘의 핵심은 해가 될 가능성을 판단하는 것. 그리고 그 가능성은 유망 함수라는 것을 정의하여 판단한다. 유효한 해의 집합을 정의 위 단계에서 정의한 집합을 그래프로 표현 유망 함수 정의 백트래킹 알고리즘을 활용해서 해를 찾음 유망 함수가 백트래킹 알고리즘에서 어떻게 동작하는지 예제를 통해 알아보자 합이 6이 넘는 조합 알아보기 {1..

이 글은 코딩 테스트 합격자 되기 - 파이썬 1독 스터디를 진행하고 느낀 점과 배운점, 그리고 보완해야할 점을 적는 글이다. 그래서 알고리즘을 검색하시다가 들어오신 분들은 뒤로 가기 하시길 바란다. 얼마 전 코딩 테스트 합격자 되기 - 파이썬 1독 스터디를 완주하였다. 블로그 글을 다시 봤을 땐 상당히 아쉬운 점이 많았다. 무엇보다 처음 글을 작성했을때는 어떤 것들을 작성해야할 줄 몰라 그냥 대충 적은 느낌이 강했다. 그리고 중반 이후 글은 그냥 복사 붙여넣기 한 것 같은 느낌이 들어 뭔가 내가 공부했다는 느낌을 받지 못하였다. 내가 이 책에 있는 정보 등을 포함하여 완전히 습득하지 못하였기 때문이라고 생각한다. 해야한다는 생각만 들어서 그냥 용량만 채운? 그런 느낌이 상당히 강했다. 이러한 기분이 많이..

그래프 최단 경로 구하기 최단 경로는 그래프 종류에 따라 그 진의가 다르게 해석될 수 있는 주제. 최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘과 벨만-포드 알고리즘을 알아보자. 다익스트라 알고리즘 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘이면서 탐욕법(Greedy Algorithm)으로 분류되는 알고리즘이기도 하다. 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련. 최소 비용을 저장할 공간은 매우 큰 값으로 초기화. (float('inf')) 직전 노드를 저장할 공간도 INF로 초기화함. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 한다. 해당 노드를 통해 방문할 수 있는 노드 중 현재까지 구한 최소 비용이 가장..