파이썬

    [프로그래머스] 3 x n 타일링 / 파이썬
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 3 x n 타일링 / 파이썬

    programmers.co.kr/learn/courses/30/lessons/12902# 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 처음에는 너무 쉽게 생각했다. 처음 생각한 점화식은 dp[i] = dp[i-2] * 3 + dp[i-4] * 2 였다. 하지만 오답이 난 순간 무언가를 빼먹었나 라는 생각을 하게되었고, 나름 쉽게 규칙을 찾을 수 있었다. 우선 n이 홀수인 경우를 생각해보자 3 x 홀수 => 홀수 이다. 즉 홀수인 경우는 홀수가 나오므로, 길이가 2인 타일들로는 채우는 것이 불가능함이 자명하다. 짝수인 경우를 생각해보자. 짝수를 n이라고 가정해보자. 우선 2개로 만들 수 있는건 그려보면 3개가 나온다. 그러니 n-2개로 만들 수 있는 수 * 3으로 만들 수 있다. ..

    [프로그래머스] 지형 이동 / 파이썬 / MST(최소신장트리)
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 지형 이동 / 파이썬 / MST(최소신장트리)

    programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 예전에 백준에서 풀어본 문제랑 비슷해서, 크게 어렵지는 않았습니다. 어렵지는 않은데, 구현이 조금 귀찮은 문제라고 볼 수 있겠네요. 우선 문제 예시에 있는 그림에서 쉽게 힌트를 찾았는데, 바로 이동할 수 없는 영역간의 구분입니다. 저는 이를 대륙(land)이라고 표현했습니다. 그리고 각각의 대륙마다, 번호..

    [프로그래머스] 하노이의 탑 / 파이썬
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 하노이의 탑 / 파이썬

    https://programmers.co.kr/learn/courses/30/lessons/12946# 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 재귀함수를 처음 배웠을 때, 백준에서도, 종만북에서도 보았던 하노이의 탑 문제입니다. 하지만 1~2년만에 다시 보니, 또 어떻게 푸는지 감이 안오더라구요.. 고민하고.. 고민하고.. 고민하다가 풀었습니다 ㅠㅜ 개인적으로는 어려운 문제라고 생각합니다.. 재귀함수를 의미론적으로 접근해야했습니다. from으로부터 to까지 (n)개의 원판을 넘..

    [프로그래머스] 길 찾기 게임 / 파이썬 / 자료구조(트리)
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 길 찾기 게임 / 파이썬 / 자료구조(트리)

    https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 자료구조를 적절히 사용하는지를 묻는 문제였던 것 같다. 이진트리를 한 번 구현해 본 경험이 있으면 쉽게 풀 수 있는 문제였다. 우선 높이별로 한 번 정렬을 한 다음에, 이진트리에 계속 추가하는 형식으로 문제를 풀었다. 딱히 설명이 필요없을 듯 하다.. import heapq as h import sys sys.setrecursionlimit(100000) a..

    [프로그래머스] 스타 수열 / 파이썬
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 스타 수열 / 파이썬

    https://programmers.co.kr/learn/courses/30/lessons/70130# 코딩테스트 연습 - 스타 수열 programmers.co.kr 최근에 일을 시작해서(사실은 귀찮아서.. 일수도..) 알고리즘 문제를 풀지 못했습니다. 오늘은 설연휴라 푹 쉬고 밤에 자기 전에, 이대로 자면 안될 것 같다..는 생각에 한 문제 풀었습니다. 내일은 꼭 두 개 풀어야지.. 풀이 방법은 모든 경우의 수를 생각합니다. 당연히 최빈값부터 계산하면 좋습니다! 그리고, 도달할 수 없는 케이스는 배제하면 시간 내에 풀 수 있습니다. :) from collections import Counter def solution(a): answer = 0 # 최빈값 common = Counter(a).most_co..

    [프로그래머스] 셔틀 버스 / 파이썬 / (시뮬레이션)
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 셔틀 버스 / 파이썬 / (시뮬레이션)

    https://programmers.co.kr/learn/courses/30/lessons/17678?language=python3 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 풀이 은근히 까다로웠던 문제이다. 푼 방법으로는 우선, 시간을 모두 분 단위로 변환한 후 모든 크루원을 한 명씩 버스에 태웠다. 한 명씩 버스에 태우다보면, 마지막 버스에, 마지막 사람이 언제 탔는지를 알 수 있는데 그 값의 -1을 한 시간을 문자열로 반환하면 된다. 만약 마지막 버..

    [프로그래머스] 숫자 게임 / 파이썬 / (정렬, 이진 탐색)
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 숫자 게임 / 파이썬 / (정렬, 이진 탐색)

    https://programmers.co.kr/learn/courses/30/lessons/12987# 풀이 예전에 풀어봤던 문제다. 핵심은 비교값보다 큰 값이 있다면, 큰 값 중 가장 작은 값을 내고 비교값보다 큰 값이 없다면 가장 작은 값을 내는 것이다. 정렬과 이진 탐색을 이용해서 풀었다. 한 번은 직접 구현했고, 한 번은 라이브러리 사용을 했다. 직접 구현 def solution(A, B): answer = 0 B.sort() def b_search(val): start = 0 end = len(B)-1 while start val: end = mid else: start = mid + 1 return end for a..

    [프로그래머스] 배달 / 파이썬 / (다익스트라 알고리즘)
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 배달 / 파이썬 / (다익스트라 알고리즘)

    https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이 전형적인 다익스트라 문제이다. 딱히 풀이과정에 대해 설명할 게 없다. import heapq as h def solution(N, road, K): answer = 0 INF = 987654321 dist = [ INF for _ in range(N+1) ] dist[1] = 0 edges = [ [] for _ in range(N..

    [프로그래머스] 기지국 설치 / 파이썬
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 기지국 설치 / 파이썬

    https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 은근히 까다로웠다. 전형적인 문제들은 쉬운데, 이런 문제는 전형적인 문제가 아니니.. 핵심은, 기지국 전파에 포함되지 않는 범위를 알아내는 것이다. 범위를 알아냈다면 쉽게 풀 수 있다. def solution(n, stations, w): answer = 0 d = [] # 처음범위 d.append((1, stations[0] - w -..

    [프로그래머스] 보석 쇼핑 / 파이썬 / 투 포인터
    Problem Solving 🔥/프로그래머스

    [프로그래머스] 보석 쇼핑 / 파이썬 / 투 포인터

    https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 문제를 읽고, 연속된 숫자 => 투 포인터 문제느낌이 나서 접근했더니 쉽게 풀 수 있었습니다. PS를 C++에서 파이썬으로 갈아탄지 얼마 안됐는데, 파이썬의 위대함을 다시 한 번 느낄 수 있었습니다. 파이썬 집합, 딕셔너리 너무 편하다... def solution(gems): answer = [] s = set() for gem in gems: s.add(gem) st, ed..

티스토리툴바