'프로그래밍/알고리즘 With Python' 카테고리의 글 목록

[프로그래머스] 메뉴 리뉴얼 with Python

programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr Python으로 프로그래머스 '메뉴 리뉴얼' 문제를 풀어봤습니다. 크게 3가지 IDEA가 필요한 문제였습니다. 1. 메뉴 주문 조합(Combination) 구하기 2. 메뉴 주문 조합별 Count 구하기 3. 조합 구하기 전에 정렬하기 ["XWY", "WXA"] → ["WXY", "AWX"] 정렬하지 않으면 "XW" 와 "WX"를 다른 메뉴 조합으로 봅니다. 저는 Python ..

프로그래밍/알고리즘 With Python 2021. 4. 10. 16:50

[프로그래머스] 멀쩡한 사각형 with Python

프로그래머스 멀쩡한 사각형 풀이 공유드립니다. 2가지 풀이 방법으로 도전해봤습니다. 1. 대각선이 움직일 때마다 사용할 수 있는 상자수를 구해서 더해준다. 2. 반복되는 패턴에서 빠지는 상자수를 구해서 더해준다. 1, 2번으로 문제에 도전한 결론부터 말씀드리면 1번은 시간 초과 및 계산 오차(6번 케이스)로 실패했고, 2번은 성공했습니다. 1번 : 대각선이 이동할 때 마다 사용할 수 있는 상자 수 구하기, 시간 복잡도 : O(n) 1. 대각선이 아래에서 위로 움직인다고 할때 X에 대응되는 Y값 (높이/너비 * 너비)을 구합니다. 2. 대각선 아래쪽에 사용할 수 있는 모든 상자들의 개수를 더합니다. Y값 내림 후 Y보다 작은 모든 자연수만큼 이 사용 가능한 상자 개수입니다. 3. 대각선 아래쪽만 구했으므로..

프로그래밍/알고리즘 With Python 2021. 4. 4. 23:36

[백준] 12865번 평범한배낭 풀이 (중복미허용 냅색)

www.acmicpc.net/problem/12865 # 요약 동적 계획법(Dynamic Programming) 대표 유형 문제입니다. Dynamic 테이블을 만들어 물품별로 업데이트를 진행해서 풀 수 있습니다. N : 상품수, K : 최대 무게 일 때 복잡도는 O(N*K) 동적 계획법을 쓰지 않고 모든 경우의 수로 문제를 풀려고 하면 O(N^2) # 문제풀이 Dynamic 테이블 업데이트 과정을 엑셀로 정리해봤습니다. 이번 문제에서 핵심은 2가지입니다. 1. 동적 계획법 활용 (다이나믹 테이블 사용) 2. 중복 미허용이므로 각 상품별 Dynamic 테이블 업데이트 시 오른쪽에서 왼쪽으로 업데이트 (←) 중복을 허용한다면 각 상품별 왼쪽에서 오른쪽으로 Dynamic 테이블 업데이트 (→) # 코드 '''..

프로그래밍/알고리즘 With Python 2021. 1. 3. 19:16

[알고리즘풀이] 프로그래머스 문자열 압축 (Kakao)

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제 설명 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 ..

프로그래밍/알고리즘 With Python 2020. 8. 9. 20:40

[백준] 14502번: 연구소 풀이 with Python

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net # 요약 백준 연구소 문제 풀이입니다. 삼성SW역량 테스트 기출문제로 문제 해결을 위해서 2가지 역량이 필요한 문제입니다. 1. 조합의 구..

프로그래밍/알고리즘 With Python 2019. 11. 4. 17:53

[알고리즘 풀이] 프로그래머스 쇠막대기, Level 2(스택/큐)

https://programmers.co.kr/learn/courses/30/lessons/42585?language=python3 알고리즘 연습 - 쇠막대기 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다. - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. - 레이저는 어떤 쇠..

프로그래밍/알고리즘 With Python 2019. 5. 5. 02:55

[알고리즘 풀이] 프로그래머스 기능개발, Level 2(스택/큐)

https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 알고리즘 연습 - 기능개발 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr for 문에 list를 지정하고 해당 list에서 pop()이 일어나면 반복문이 어떤식으로 흘러가는지 알게되었음. 아래는 풀이한 코드 다른사람들 코드는 훨씬 간결.. 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 27 28 29 30 31 32 33 34 def solution(progresses, speeds): answer = [] pro = progresses sp = speeds # 1..

프로그래밍/알고리즘 With Python 2019. 5. 2. 20:20

[알고리즘 풀이] 프로그래머스 위장, Level2(해시)

https://programmers.co.kr/learn/courses/30/lessons/42578 알고리즘 연습 - 위장 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 배열로 동적변수를 만든다 라는 방식으로 접근했었는데, 배열로 동적변수를 만들고 만든 동적변수에 append를 하는 건 쉬는게 아닌거 같음. 나중에 생각해보기. 아래는 문제풀이 내용 1 2 3 4 5 6 7 8 9 10 11 12 13 from collections import defaultdict def solution(clothes): num_clothes = defaultdict(int) for name, kind in clothes : num_clothes[kind] +=1 answer = 1 f..

프로그래밍/알고리즘 With Python 2019. 4. 21. 17:24

[알고리즘 풀이] 프로그래머스 : 다리를 지나는 트럭, Level2(스택/큐)

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3 알고리즘 연습 - 다리를 지나는 트럭 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 1. 가장 앞에 있는 트럭을 뽑는다. 2. 다리에 있는 트럭을 확인한다. 3. 다리에 트럭이 없거나, 뽑은 트럭과 다리에 있는 트럭의 합이 weight 이하이면 다리를 트럭에 넣는다. 4. 1초마다 반복한다. + 트럭이 들어간지 다리의 길이만큼 지나면 빼낸다. 10분 정도 위의 내용을 생각해보고 코드로 구현해서 풀었다. 디버깅 과정은 생각보다 짧았고, 문제푸는데는 총 30분 정도 소요. 아래는 풀이한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13..

프로그래밍/알고리즘 With Python 2019. 4. 18. 19:55

[알고리즘 풀이] 프로그래머스 : 2016년, 연습문제

https://programmers.co.kr/learn/courses/30/lessons/12901?language=python3 알고리즘 연습 - 2016년 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 월별 Days를 딕셔너리로 만들어서 문제해결. 날짜를 1~366(2016년이 윤년이라 366)까지의 숫자로 만들고 나머지를 구해서 해당날짜가 무슨요일인지 구한다. 아래는 테스트 통과한 코드 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 27 28 29 30 31 Month_per_Days = {} Month = [i for i in range(1,13)] Days = [0,31,29,31,3..

프로그래밍/알고리즘 With Python 2019. 4. 16. 00:25

[알고리즘문제 풀이] 프로그래머스 : 서울에서 김서방 찾기, 연습문제

https://programmers.co.kr/learn/courses/30/lessons/12919?language=python3 알고리즘 연습 - 서울에서 김서방 찾기 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 하루에 최소 1문제씩 풀자는 의지. 오늘 역량테스트는 죽쒔음. 테스트케이스를 array가 아니고 input()으로 직접 받다니 거기서 부터 꼬여서 1시간 30분 잡아먹었다. 잘준비하자. 1 2 3 4 5 6 7 8 9 10 11 def solution(seoul): answer = 0 for i, j in enumerate(seoul) : if j == "Kim" : answer = i break return "김서방은 "+str(i)+"에 있다"

프로그래밍/알고리즘 With Python 2019. 4. 14. 23:38

[알고리즘 풀이] 프로그래머스 : 타겟넘버, Level2(깊이/너비 우선 탐색)

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 알고리즘 연습 - 타겟 넘버 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(numbers, target): cnt = 0 def operator(numbers, target, idx=0) : if idx

프로그래밍/알고리즘 With Python 2019. 4. 12. 20:12

[알고리즘 풀이] 프로그래머스 : 가장 큰 수, Level2(정렬)

https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 알고리즘 연습 - 가장 큰 수 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 처음에 전체 수의 조합을 찾고, 그중에서 가장 큰 값을 찾는다로 접근했는데 역시나 "시간초과" # 전체 수 조합 찾고, 그중에서 가장 큰 값을 찾기 (시간초과로 실패) 1 2 3 4 5 6 7 8 9 10 11 12 13 import itertools def solution(numbers): s_num = [str(i) for i in numbers] p_num = itertools.permutations(s_num) p_num = ["".join(i) for i ..

프로그래밍/알고리즘 With Python 2019. 4. 12. 19:47

[알고리즘 풀이] 프로그래머스 : 소수 찾기, Level2(완전탐색)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 알고리즘 연습 - 소수 찾기 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 아래 2가지 과정으로 문제를 단순화 해서 풀었음 1. 전체 순열리스트 구하기 2. 소수 판별 위 2개만 보면 아주 간단해 보이는데, 저 2개 구현하는게 생각보다 간단하지 않아서 문제푸는데 오래걸렸음. - 전체 순열리스트 구하기는 itertools의 permutations를 사용해서 구함 - 소수판별은 에라토스테네스의 체 방식으로 * 판별하려는 수(이하 판별수)를 2부터 판별수의 제곱근으로 나누어 나머지가 0인 경우가 나오면 소수가 아님 permutations..

프로그래밍/알고리즘 With Python 2019. 4. 12. 16:42

[알고리즘 풀이] 프로그래머스 : 체육복, Level2(탐욕법)

https://programmers.co.kr/learn/courses/30/lessons/42862?language=python 알고리즘 연습 - 체육복 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 비교적 쉽게 성공 문제가 길어서 어려울 줄 알았는데, 순차적으로 접근하니 생각보다 쉽게 해결되었다. 코드 + 간단한 설명 덧붙이겠다. 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 27 28 29 30 31 32 33 34 35 36 37 def solution(n, lost, reserve): answer = 0 s_arr = [1 for i in range(n)] # 초기 값..

프로그래밍/알고리즘 With Python 2019. 4. 12. 14:49

[알고리즘 풀이] 프로그래머스 : K번째수, Level1(정렬)

Python 자체 정렬함수를 쓰니까 너무 쉬운듯. https://programmers.co.kr/learn/courses/30/lessons/42748?language=python3 알고리즘 연습 - K번째수 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 1 2 3 4 5 6 7 8 9 10 11 def solution(array, commands): answer = [] for i in range(len(commands)) : cal_value = array cal_value = cal_value[commands[i][0]-1:commands[i][1]] cal_value.sort() answer.append(cal_value[commands[i][2]-1]) retu..

프로그래밍/알고리즘 With Python 2019. 4. 12. 01:43

[알고리즘 풀이] 프로그래머스 : 더 맵게, Level2(Heap)

아래는 문제링크 https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3# 알고리즘 연습 - 더 맵게 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 정확성에서는 통과했으나 효율성에서 실패. 실패 1 (sort가 많아서 실패) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1번 sort()가 많아서 실패 def solution(scoville, K): answer = 0 while len(scoville) >=1 : if min(scoville) >= K : return answer else : if len(scoville) == 1 : return -1 scoville..

프로그래밍/알고리즘 With Python 2019. 4. 12. 01:04

[알고리즘 풀이] 프로그래머스 : 전화번호 목록, Level2(해시)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3# 알고리즘 연습 - 전화번호 목록 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 내 풀이 간신히 통과했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def solution(phone_book): answer = True for i in phone_book : len_num = len(i) com_list = [] #비교할 값 for j in phone_book : # i보다 긴 것들만 com_list에 append if i != j : # 같은 값일 때는 제외 함 if len_num = ..

프로그래밍/알고리즘 With Python 2019. 4. 11. 23:18

[알고리즘 풀이] 프로그래머스 : 탑, Level2(스택/큐)

프로그래머스(https://programmers.co.kr/) 프로그래밍 강의 | 프로그래머스 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr 프로그래머스 코딩테스트 중 Level 2 탑 문제 푼 내용입니다. Python 3 으로 풀어봤습니다. python 리스트의 기본 method인 pop, insert를 사용해서 리스트를 스택(stack)으로 사용해 문제를 풀었습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(heights): s_result = [] # 마지막 출력용 while len(heights) > 0 : h_temp = heights.pop() # print(heights) s1 = [i for i in he..

프로그래밍/알고리즘 With Python 2019. 4. 9. 02:24

행궁동 데이터 엔지니어

프로그래밍/알고리즘 With Python → (19)건