본문 바로가기

Python191

[프로그래머스] 기지국 설치 (Python) https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr N의 범위를 보면 N: 200,000,000 이하의 자연수라 되어있기 때문에 N을 기준으로 풀면 시간 초과가 난다. 따라서 stations을 바탕으로 알고리즘을 생각했다. 해당 기지국의 커버 범위에 따라 추가해야 하는 기지국 값을 answer에 추가해준다. 나의 풀이 def solution(n, stations, w): start = 1 an.. 2021. 11. 23.
[프로그래머스] 블록 이동하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 힘든 구현 문제다. 이게 맞나 싶으면서 그냥 구현했다. bfs로 풀었다. 나의 풀이 from collections import deque,defaultdict def solution(board): length = len(board) visited = defaultdict(int) visited[(0,0,0,1)] = 1 q = deque([(0,0,0,1,0)]) while q: x, y, .. 2021. 11. 18.
[프로그래머스] 매칭 점수 (Python) https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr 고통스러웠다 정규식을 나름 조금씩 해봤다고 생각했는데 전혀 모르는 개념이 많았다. 특히 findall 이랑 search + group 차이를 이번에 깨달았고 \w, \W, \s, \S, + , * [ ] 등 다양한 메타 문자를 배우게 된 계기가 됐다.. 테스트 케이스가 많이 없으면 확실히 어렵다 나의 풀이 import re from collections impor.. 2021. 11. 18.
[프로그래머스] 외벽 점검 (Python) https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr set과 product를 이용해서 풀려고 했는데 시간초과가 나서 다른 풀이를 이용했다 def solution(n,weak,dist): count = 0 repair_list = [()] dist.sort(reverse = True) for distance in dist: repairs = [] count +=1 for i,st in enumerate(weak):.. 2021. 11. 18.
[프로그래머스] 모두 0으로 만들기 (Python) https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr DFS 문제다. queue로 BFS 풀려했는데 잘 풀리지 않았다 DFS 방식이 좀 친숙해지는 계기가 된 것 같다. import sys sys.setrecursionlimit(300000) answer =0 def solution(a,edges): global answer if sum(a) !=0: return -1 graph = [[] for .. 2021. 11. 17.
#7 Python 코딩테스트 최단 경로 알고리즘 https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7 이 포스팅은 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다. 다익스트라 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 - 음의 간선이 없을 때 정상적으로 동작. - 그리디 알고리즘에 속함. 다익스트라 알고리즘 간단한 구현 방법 import sys input = sys.stdin.readline INF = int(ie9) # 무한을 의미하는 값으로 10억을 설정 n, m = map(int, input().split()) start = int(input()) # 각 노드에 연결되어 있는 노드에 대.. 2021. 11. 17.
[프로그래머스] 징검다리 건너기 (Python) https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 이진탐색으로 구현해야 풀리는 문제다 def step_stone(stones,num,k): cnt = 0 for stone in stones: if stone - num = k: return False return True def solution(stones, k): start = 1 end = 200000000 while (start 2021. 11. 16.
[프로그래머스] 길 찾기 게임 (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.

티스토리툴바