티스토리

Data Engineering

검색하기

블로그 홈

Data Engineering

jun-code-in.tistory.com/m

jun_code 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

Python 알고리즘 끄적끄적 시간초과 발생 요인반복적인 SUM문제 참고 : 스택/큐 - 다리를 지나는 트럭 (프로그래머스)sum은 시간복잡도가 O(N)인데 반복문 for이나 while을 사용하면 시간복잡도가 O(n^2)이 될 수 있음아래 예시는 sum으로 인해 시간초과가 발생한 경우로 sum을 반복적으로 하는 것이 아닌 계산된 값을 이용while len(truck_list) !=0: b = bridge.popleft() S -= b if S + truck_list[0] > weight: # sum 함수에서 시간 초과 발생 time +=1 bridge.append(0) else: t = truck_list.popleft() bridge.append(t) .. 공감수 0 댓글수 0 2025. 1. 20.
★★★ 스택/큐 - 다리를 지나는 트럭 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr from collections import dequedef solution(bridge_length, weight, truck_weights): l = len(truck_weights) bridge = deque([0] * bridge_length) truck_list = deque(truck_weights) S, time = 0, 0 while len(truck_list) !=0: b = bri.. 공감수 0 댓글수 0 2025. 1. 20.
스택/큐 - 프로세스 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr from collections import dequedef solution(priorities, location): prior_list = deque() answer = [] l = len(priorities) prior = deque(sorted(priorities, reverse = True)) for i in range(l): prior_list.append((priorities[i], i)) .. 공감수 0 댓글수 0 2025. 1. 18.
스택/큐 - 올바른 괄호 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr from collections import dequedef solution(s): if s[0] == ')': return False else: par_list = deque() for i in s: if i == '(': par_list.append(i) else: if len(par_list) == .. 공감수 0 댓글수 0 2025. 1. 18.
스택/큐 - 기능개발 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(progresses, speeds): answer = [] time = [] l = len(progresses) for i in range(l): p, s = progresses[i], speeds[i] if (100 - p) % s == 0: time.append((100 - p) // s ) else: time.app.. 공감수 0 댓글수 0 2025. 1. 16.
스택/큐 - 같은 숫자는 싫어 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/12906 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(arr): answer = [] c = -1 for i in arr: if len(answer) ==0 : answer.append(i) c = i else: if c == i: pass else: answer.append(i) .. 공감수 0 댓글수 0 2025. 1. 16.
★★★ 해시 - 베스트앨범 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(genres, plays): x = len(genres) dict_music = {} dict_list = {} answer = [] for i in range(x): gen = genres[i] if gen not in dict_music.keys(): dict_music[gen] = plays[i] dict_list[gen] .. 공감수 0 댓글수 0 2025. 1. 15.
해시 - 의상 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(clothes): dict_cloth = {} answer = 1 for cloth, types in clothes: if types not in dict_cloth.keys(): dict_cloth[types] = [cloth] else: dict_cloth[types].append(cloth) for i.. 공감수 0 댓글수 0 2025. 1. 15.
★★ 해시 - 전화번호 목록 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr from collections import Counterdef solution(phone_book): # hash를 dict로 만드는 방법 1 hash_phone = {} for phone in phone_book: hash_phone[phone] = 0 # hash를 dict로 만드는 방법 2 # hash_phone = Counter(phone_book) for phone in.. 공감수 0 댓글수 0 2025. 1. 15.
해시 - 완주하지 못한 선수 (프로그래머스) https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr from collections import Counterdef solution(participant, completion): a = Counter(participant) - Counter(completion) # Counter({'vinko': 1}) print(a.keys()) # dict_keys(['vinko']) return list(a.keys())[0] collections의 Counter 클래스를 이용한다Counte.. 공감수 0 댓글수 0 2025. 1. 14.
해시 - 폰켓몬 https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(nums): return min(len(nums)//2, len(set(nums))) set : list에서 sum은 중복값 제거 가능 공감수 0 댓글수 0 2025. 1. 13.
백준 19637번 : IF문 좀 대신 써줘 링크 : https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net import sys input = sys.stdin.readline from bisect import bisect_left N, M = map(int, input().split()) name = [] attack = [] for i in range(N): n, a = input().split() name.append(n) attack.append.. 공감수 0 댓글수 0 2022. 2. 12.
백준 11663번 : 선분 위의 점 링크 : https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right N, M = map(int, input().split()) point = list(map(int, input().split())) point.sort() line = [list(map(int, input().spli.. 공감수 0 댓글수 0 2022. 2. 12.
백준 2805번 : 나무 자르기 링크 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net import sys input = sys.stdin.readline N, M = map(int, input().split()) height = list(map(int, input().split())) s, e = 1, max(height) while e-s >=0: mid = (s+e)//2 tree = 0 for i in height: tree +.. 공감수 0 댓글수 0 2022. 2. 12.
백준 2512번 : 예산 링크 : https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) bud = list(map(int, input().split())) M = int(input()) s, e = 0, max(bud) while e-s >= 0: mid = (s+e)//2 res = 0 for i in range(N): if bud[i] >= mid: res += mid.. 공감수 0 댓글수 0 2022. 2. 12.
백준 2022번 : 사다리 링크 : https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net import sys input = sys.stdin.readline import math def get_height(x, y, w): h1 = math.sqrt(x**2-w**2) h2 = math.sqrt(y**2-w**2) h = h1*h2/(h1+h2) return h x, y, c = map(float, input().split()) w_s = 0 w_e = min(x, y) dif = 1 res_w = 0 wh.. 공감수 0 댓글수 0 2022. 2. 12.
백준 1654번 : 랜선 자르기 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net import sys input = sys.stdin.readline K, N = map(int, input().split()) lan = [int(input()) for _ in range(K)] res = 0 s, e = 1, max(lan) while e-s >= 0: num = 0 mid = (s+e)//2 for i in range(K): num += .. 공감수 0 댓글수 0 2022. 2. 12.
백준 20291번 : 파일 정리 링크 : https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net import sys input = sys.stdin.readline # 시간 줄이기 N = int(input()) dict = {} for i in range(N): x, y = input().strip().split(".") # strip으로 공백 제거 if y in dict: dict[y] += 1 else: dict[y] = 1 for key in sorted(dict.keys()): pr.. 공감수 0 댓글수 0 2022. 1. 25.
백준 19948번 : 음유시인 영재 링크 : https://www.acmicpc.net/problem/19948 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net import sys input = sys.stdin.readline poem = input().strip().split() space = int(input()) alpha = list(map(int, input().split())) result = True if len(poem)-1 > space: result = False else: s = len(poem) for i in range(s.. 공감수 0 댓글수 0 2022. 1. 25.
백준 17413번 : 단어 뒤집기 2 링크 : https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net import sys input = sys.stdin.readline S = input().rstrip() inner = False word = '' result = '' for i in S: if inner == False: # 외부 if i == '': 는 나올수 없는 경우 else: word = i + word else: # 내부 if i.. 공감수 0 댓글수 0 2022. 1. 25.
백준 1972번 : 놀라운 문자열 링크 : https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문 www.acmicpc.net import sys input = sys.stdin.readline def sup(M): m = len(M) result = True if m >1: itv = [i for i in range(m-1)] for i in itv: s = set() for j in range(m-1-i): _x = M[j]+M[j+1+i] s.add(_x) if len(s) != m-1-i: result =.. 공감수 0 댓글수 0 2022. 1. 25.
백준 1764번 : 듣보잡 링크 : https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net import sys input = sys.stdin.readline N, M = map(int, input().split()) s1= set() s2= set() for _ in range(N): s1.add(input().strip()) for _ in range(M): s2.add(input().strip()) s = sorted(list(s1.intersection(s2))) n .. 공감수 0 댓글수 0 2022. 1. 25.
백준 11725번 : 트리의 부모 찾기 링크 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net from collections import deque import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) # 반복 제한 풀기(default : 1000) N = int(input()) graph = [[] for _ in range(N+1)] parent = [-1] * (N+1) for _i in range(N-1): x, y = map(int, input().split()) gra.. 공감수 0 댓글수 0 2022. 1. 16.
백준 11724번 : 연결 요소의 개수 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys input = sys.stdin.readline # 안하면 시간초과 발생 sys.setrecursionlimit(10**6) # 런타임 에러 방지 - 재귀 N, M = map(int,input().split()) graph = [[] for _ in range(N+1)] for i in range(M): _.. 공감수 0 댓글수 0 2022. 1. 16.
백준 2606번 : 바이러스 링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net from collections import deque import sys input = sys.stdin.readline N = int(input()) n = int(input()) graph = [[] for _ in range(N+1)] # 편의상 0 추가 for _i in range(n): _x, _y = map(int, input().split()) graph[_x].append(_y).. 공감수 0 댓글수 0 2022. 1. 16.
백준 1260번 : DFS와 BFS 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque import sys input = sys.stdin.readline N, M, V = map(int, input().split()) graph = [[] for _i in range(N+1)] # 편의를 위해 1개 더 추가 for i in range(M): x, y= map(int,input().s.. 공감수 0 댓글수 0 2022. 1. 16.
백준 1012번 : 유기농 배추 링크 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline def dfs(x, y): _x = [0, 0, 1, -1] _y = [1, -1, 0, 0] for i in range(4): m_x = x+_x[i] m_y = y+_y[i] if (0 공감수 0 댓글수 0 2022. 1. 16.
백준 1912번 : 연속합 링크 : https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr_sum = [0] * n arr_sum[0] = arr[0] for i in range(1, n): if arr_sum[i-1] > 0 : arr_sum[i] = arr_sum[i-1]+arr[i] else: arr_sum[i].. 공감수 0 댓글수 0 2022. 1. 8.
백준 11053번 : 가장 긴 증가하는 부분 수열 링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) count = [1] * N for i in range(1, N): _list = [] for j in range(i): if A[i] > A[j]:.. 공감수 0 댓글수 0 2022. 1. 8.
백준 9095번 : 1, 2, 3 더하기 링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) x_list= [] for _i in range(N): _x = int(input()) x_list.append(_x) x = 10 count = [[0 for i in range(x+1)] for j in range(3)] count[0] = [0] + [1 for i in range(0, x+1)] count[1][1] = count[2][1] = 1 for i in range(1, 3.. 공감수 0 댓글수 0 2022. 1. 5.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.