본문 바로가기

전체 글269

[프로그래머스] 섬 연결하기(Python) https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 두세 시간 걸려서 풀었던 문제다. 알고리즘을 어떻게 짜야할지 오래 고민했다 내가 짠 알고리즘을 아래 기준으로 설명하겠다. cost = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] n = 4로 주어졌을 때 일단 각 섬의 정보를 모아놓는 리스트 안에 python set을 통해 각 set에 현재 연결된 섬의 정보를 담는다. island = [set() for _ in range(n)] 다음으로 섬 연결 비용 기준으로 정렬한다. cost.. 2021. 10. 28.
[프로그래머스] 구명보트 (Python) https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 사람의 무게를 정렬하고 가장 무거운 사람과 가장 가벼운 사람의 무게를 더해서 limit를 넘지 않으면 answer를 추가시키는 방식으로 코드를 작성했다. def solution(people, limit): people.sort(reverse=True) right = len(people)-1 answer = 0 for i in range.. 2021. 10. 27.
[프로그래머스] 큰 수 만들기(Python) https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이것저것 여러 풀이 방식으로 풀었다. 나머지 테스트는 모두 통과했지만 10번에서 시간 초과가 났다 def solution(number, k): result = len(number)-k index = 0 answer = '' while k>0 and len(answer)!=result: max_index = number[index:index+k+1].find(max(number[index:index+k+1])) answer+=number[index:index+k+1][max_index] k-=max_index index += max_inde.. 2021. 10. 27.
[프로그래머스] 조이스틱(Python) https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 이 문제에서 구현해야 하는 로직은 두 가지다 1. 현재 커서의 알파벳에 따라 이동해야 하는 최소 커서 횟수 계산 2. 현 위치에서 커서를 왼쪽 오른쪽 중 어디로 이동해야 최소 커서 이동인지 계산 알파벳의 총개수는 25개이므로, 위의 12개 까지는 조이스틱을 아래로 아래 12개 까지는 조이스틱을 위로(거꾸로) 이동하면 된다. 'A'의 아스키 코.. 2021. 10. 26.
#6 Python 코딩테스트 다이나믹 프로그래밍(DP) https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 이 포스팅은 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다. 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음 구현은 Top - Down , Bottom - Up 동적 계획법이라고도 부름 문제가 다음의 조건을 만족할 때 사용 할 수 있음. 1. 최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2.. 2021. 10. 23.
[프로그래머스] 괄호 변환(Python) https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 주어진 조건대로 구현하면 되는 문제다. 살짝 까다롭긴 했지만 풀만 했던 것 같다. 나의 코드 def check_correct(p): stack = [] for i in p: if i =='(': stack.append(i) elif len(stack) ==0: return False else: stack.pop() return True def split_brack.. 2021. 10. 23.
[프로그래머스] 짝지어 제거하기(Python) https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 스택 자료구조를 사용해서 O(N)으로 풀 수 있다. 나의 코드 def solution(s): stack = [] for i in s: if len(stack) == 0: stack.append(i) elif stack[-1] == i: stack.pop() else: stack.append(i) return 0 if stack else 1 2021. 10. 23.
[프로그래머스] 오픈채팅방(Python) https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 나의 코드 def solution(record): user = dict() answer= [] for i in record: info = i.split() if info[0] =='Enter' or info[0]=='Change': user[info[1]]=info[2] for i in record: info = i.split() if info[0] =='Ent.. 2021. 10. 22.
[프로그래머스] 부족한 금액 계산하기(Python) https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 1주차_부족한 금액 계산하기 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 등차수열의 합을 공식으로 쓰면 됨 def solution(price, money, count): return max(0,price*(count+1)*count//2-money) 2021. 10. 21.
[프로그래머스] 나머지가 1이 되는 수 찾기(Python) https://programmers.co.kr/learn/courses/30/lessons/87389 코딩테스트 연습 - 나머지가 1이 되는 수 찾기 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 입 programmers.co.kr def solution(n): for i in range(1,n): if n%i==1: return i 주어진 조건대로 그대로 구현하면 되는 문제다. 2021. 10. 21.
[프로그래머스] 여행 경로(Python) https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 처음 문제를 풀 때는 알파벳 정렬만 따져서 풀어서 일부 문제가 안 풀렸다. 내가 틀리는 유형의 테스트 케이스는 하단과 같다. tickets = [["ICN", "AOO"], ["AOO", "BOO"], ["AOO", "COO"], ["COO", "AOO"], ["BOO", "ZOO"]] answer.. 2021. 10. 21.
[프로그래머스] 단어 변환(Python) https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 나의 풀이 from collections import deque def check_one_word(word,begin): counting = 0 for w,b in zip(word,begin): if w != b: counting +=1 return True if counting ==1 else False def sol.. 2021. 10. 21.
[프로그래머스] 네트워크(Python) https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 참고 https://hkim-data.tistory.com/31?category=1016184 #2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 https://www.yout.. 2021. 10. 21.
[프로그래머스] 타겟 넘버 (Python) https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 참고 https://hkim-data.tistory.com/31?category=1016184 #2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0d.. 2021. 10. 21.
#5 Python 코딩테스트 이진 탐색 https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이 포스팅은 위의 영상을 보고 제가 필요하다고 생각되는 부분을 정리한 포스팅입니다. 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. 절반씩 데이터를 쪼개서 탐색하기 때문에 O(logN)의 시간 복잡도를 가지게 됨 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search_recursive(array, target.. 2021. 10. 20.

티스토리툴바