'적자' 생존

하노이의 탑 하노이의 탑이라는 단어는 뭔가 익숙했는데 문제 내용은 굉장히 생소한 내용이었습니다. 재귀 문제를 설명하는 데 있어서 많이 다룬다고 하는데 비전공자여서 그런가 이런 문제가 낯설기만 합니다.. 그래서 가끔 이런 유명한 문제에 대해서는 포스팅을 하면서 깊게 파야겠습니다. 문제 설명 '하노이의 탑'은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로 다음과 같이 그림으로 표현할 수 있습니다. 이 문제의 목표는 기둥 A에 쌓여 있는 원판을 기둥 C에 옮겨서 다시 쌓는 것이 목표입니다. 하지만 원판을 옮길 시에는 다음과 같은 두 가지 조건을 만족하면서 옮겨져야 합니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 이 조건에서 '최소의 이동횟수로..

코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 처음에 어떻게 풀어가야할지 너무 막막했다. 무엇을 기준으로 정렬을 수행해야 할지 몰랐기 때문이다. 우선 각 숫자의 앞자리 숫자부터 비교해나가야 하는 것은 알 수 있는데 테스트 케이스로 주어진 34, 30, 3의 경우에는 무슨 기준으로 정렬해야 할지 고민하다가 결국 타인의 도움을 빌리기로 했다. [프로그래머스] 가장 큰 수 문제 가장 큰 수 (https://programmers.co.kr/learn/..

코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 처음은 그냥 내장 함수 sorted()를 활용해서 풀어봤다. 하지만 정렬 알고리즘을 직접 구현해보는 것도 좋을 것 같아서 선택 정렬과 삽입 정렬을 구현해보기로 했다. 1. 내장함수 sorted 활용 1 2 3 4 5 6 7 8 def solution(array, commands): answer = [] for command in commands: temp_array = array[command[0]-1:command[1]] temp_array = sorted(temp_array) answer.append(temp_array[co..

https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 노란색 사각형의 경우의 수를 모두 고려하고 그 노란 사각형을 갈색 격자로 한 층씩 덮어가는 식으로 구현하였다. 남은 갈색 격자의 수가 정확히 0이라면 answer로 반영한다. 1234567891011121314151617181920212223242526272829303132333435def solution(brown, yellow): answer = [] f..

코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 주어진 카드로 만들수 있는 경우의 수를 고려하기 위해 순열을 활용하였다. 순열을 직접 구현할 수도 있지만 이번에는 편하게 itertools를 활용해봤다. 만든 숫자에서 소수를 골라내기 위해서도 단순하게 2부터 (만든 숫자 - 1)까지를 나눠서 나머지 0이 안 되게 모든 반복문을 모두 순회하면 answer를 1 추가 시켜줬다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 코드는 총 3파트로 활용할 데이터를 추려내는 파트, 점수 계산 파트, 고득점자 추려내는 파트가 있다. 점수 계산하는 파트에서 찍는 번호 순서가 담은 리스트를 계속 반복해서 참조해야 하기 때문에 answers의 idx인 a에서 순서 리스트의 길이를 나눈 후 나머지를 인덱스로 지정하였다. 고득점자를 추려내는 파트에서는 현재 최고 점수보다 더 큰 점수가 나오면 answer를 초기화시키고 고득점자를 추가하고 최고 점수와 같은 점수가 나오면 고득점자 한 명을 추가시키는 ..

코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 재귀함수를 사용하여 DFS를 적용하였다. 철자가 하나만 다른 단어인지 확인하는 함수 canChange를 정의하였다. 현재 answer보다 함수 스택인 k가 크다면 바로 반환한다. 현재 dfs 함수에서의 cur_word와 target이 같다면 answer에 k를 할당한다. words를 반복하여 이미 바꾼 단어이거나 canChange가 True를 반환한다면 새로운 dfs함수를 호출한다. 1 2 3 4 5 6 7 8 9 10..

코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr BFS를 구현하기 위해 자료구조 Queue를 활용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import deque def solution(n, computers): len_c = len(computers) visited = [0 for _ in range(len_c)] answer = 0 for i in range(len_c): if not visited[i]..