본문 바로가기

All Post269

[프로그래머스] 길 찾기 게임 (Python) 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 sys sys.setrecursionlimit(10**5) class Tree: def __init__(self, nodeinfo): self.idx, *self.root.. 2021. 11. 15.
[프로그래머스] 기둥과 보 설치 (Python) https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 조건이 너무 많아져서 이건 아닌 것 같아서 다른 분 아이디어를 참고해서 코드를 작성.. 2021. 11. 15.
[프로그래머스] 풍선 터트리기 (Python) https://programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 이런저런 케이스를 생각하다 보면 해당 위치에서 왼쪽 오른쪽으로 가장 작은 값이 하나라도 본인일 경우 마지막까지 남는 풍선이 될 수 있다. 따라서 왼쪽에서, 오른쪽에서 동시에 서치 하면서 가장 작은 순간이 있다면 answer에 추가해주면 된다. 나의 풀이 def solution(a): answer = [False for _ in range(len(a))] INF = 1000000001 left_min, right_min = INF, INF for i in range(le.. 2021. 11. 14.
[프로그래머스] 최고의 집합 (Python) https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 나의 풀이 def solution(n, s): answer = [] while s >0: if s//n == 0: return [-1] answer.append(s//n) s -= s//n n -=1 return answer 2021. 11. 13.
[프로그래머스] 줄 서는 방법 (Python) https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 완전 탐색은 시간 초과가 뜨고 나열해서 적다 보면 규칙이 있다 이를 활용하면 풀 수 있음 나의 풀이 import math def solution(n, k): answer = [] number = [i for i in range(1, n+1)] while (n != 0): temp = math.factorial(n) // n index, k = k/.. 2021. 11. 13.
[프로그래머스] 야근 지수(Python) https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr heapq를 활용해서 매번 정렬하지 않고 풀면 통과한다. 나의 풀이 import heapq def solution(n, works): q = [] for work in works: heapq.heappush(q,-work) for _ in range(n): if q: t = heapq.heappop(q) if t !=-1: heapq.heappus.. 2021. 11. 13.
[프로그래머스] 멀리 뛰기(Python) https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 나열해서 쓰다 보면 피보나치임을 알 수 있다. 나의 풀이 def solution(n): fibo = [0]*(n+1) fibo[0] = 1 fibo[1] = 1 for i in range(2,n+1): fibo[i] = fibo[i-1] + fibo[i-2] return fibo[n]%1234567 2021. 11. 13.
[프로그래머스] 거스름돈 (Python) https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 완전 탐색으로 할 때 너무 오랜 시간이 걸려서 dp인 것은 알았으나 알고리즘을 생각을 못했다. def solution(n, money): dp = [1] + [0]*n for coin in money: for i in range(1,n+1): if coin 2021. 11. 13.
[프로그래머스] 가장 긴 팰린드롬 (Python) https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr for range와 list indexing을 정확하게 이해하게 된 문제다. 나의 풀이 def palindrome(s): if len(s)%2 ==0: return True if s[:len(s)//2] == s[len(s)-1:len(s)//2-1:-1] else False else: return True .. 2021. 11. 12.
[프로그래머스] 아이템 줍기 (Python) https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 어려웠던 문제다. bfs로 풀었다. 1. 시작 지점에서부터 U, D, R, L 방향으로 하나씩 이동 2. 이동 후 조건에 맞는지 확인 - 좌표 범위를 넘어갔으면 continue - 방문 한 적이 있다면 continue - 주어진 직사각형들을 하나씩 순회하며 직사각형 좌표를 받는다.. 2021. 11. 11.
[프로그래머스] 경주로 건설 (Python) https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 어려웠다... bfs + dp로 풀어냈는데 계속 틀려서 확인해보니 board = [ [.. 2021. 11. 10.
[프로그래머스] 합승 택시 요금 (Python) https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 매 지점까지 같이 합승했다고 치고 그 지점에서 각자 목적지로 이동했을 경우에서 요금.. 2021. 11. 10.
[프로그래머스] 금과 은 운반하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/86053 코딩테스트 연습 - 금과 은 운반하기 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 programmers.co.kr 이진 탐색으로 풀면 된다. 나의 풀이 def solution(a, b, g, s, w, t): start = 0 end = int(1e9*1e5*2*2) answer = end while start= a and all_silver >= b and all_total >= a+b : # 시간 더 줄이기 answer = min(answer,mid.. 2021. 11. 10.
[프로그래머스] 불량 사용자 (Python) https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 쉬울 줄 알았는데 생각보다 오래 걸렸다.. 처음 풀이는 ban 사용자 가지고 조합을 짜서 user_id를 만족하면 answer를 추가해주는 방식으로 코드를 짰다. 처음 풀이 import re from collections import Counter from itertools import product def solution(user_id, banned_id): .. 2021. 11. 9.
[프로그래머스] 보석 쇼핑 (Python) https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 투 포인터 문제다. 처음에 set을 이용해서 각각의 경우마다 set(gems[start : end +1]) == set(gems) 이렇게 풀었었는데, 효율성 테스트에서 시간 초과가 났다. 시간초과가 날 때 입력 값의 범위를 고려해서 알고리즘을 변경하거나 set or dict를 활용할 생각을 해야겠다. 나의 풀이 def solution(gems): start, end, answer = 0, 0, [0, len(g.. 2021. 11. 9.

티스토리툴바