목록알고리즘 (23)
DevKim
programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 기존의 알파벳으로 사전을 생성시켜준다. 그 후에 문자열을 하나씩 돌면서 사전에 존재하는 문자열까지 체크를 해주고, 존재하는 문자열+1까지의 문자열을 사전에 새로 넣어준다. 마지막 문자열을 처리하는 과정에서 index에 오류가 있어서 생각보다 오래걸렸던 문제였음 [코드] def solution(msg): answer = [] dic=[0] for i in range..
programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr [ 알고리즘 ] 다익스트라 최단거리 알고리즘 [문제 접근] 1에서 출발하여 모든 노드까지의 최단경로를 구하기위해 다익스트라 최단경로 알고리즘을 사용하였음. 힙을 사용하여 매번 최소 경로를 가지고 있는 노드를 반환하는 것이 포인트이다. [코드] import sys import heapq def solution(N, road, K): inf = sys.m..
programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] #을 어떻게 처리하느냐가 이 문제의 핵심이다. 처음엔 #이 뒤에올때, 안 올때를 나눠서 풀까.. 생각했지만, 너무 번거로울 것 같아서 고민하다가 소문자로 변환해서 풀면 쉬울 것 같아서 모조리 소문자로 바꿨다. 문제를 처음에 제목 길이가 긴 순서를 우선순위로 놓고 풀어라 라고 잘못 읽어서 이상한 오류다.. 생각하고 있었다(하^^)..
programmers.co.kr/learn/courses/30/lessons/17677# 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 다중 집합에 대해 확장할 수 있다는 조건으로, 단순히 파이썬의 내장 함수 set을 사용하여 교집합과 합집합을 구할 수 있는 문제가 아니었다. 또한 영문자외의 다른 문자뒤나, 앞에 오는 문자들은 함수에 들어가지 않는다는 점을 고려해야했다. 입력 : AA_bb_aa_AA,BBB 출력 : 13107 이 반례가 오류를 고치는..
programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 1. combonations 를 이용해 조합을 구해주었고 2. Counter을 이용해 나온 횟수를 구해주었다. 처음엔 collections 에 있는 defaultdict을 이용해서 문자열들의 조합을 하나씩 세주고, 그 후 정렬을 한 후에 최대값과 같은 애들을 하나씩 구해줬는데 그렇게하니 실행 케이스에서 2개 정도 시간 초과가 나서 아예 처음부..
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr [ 알고리즘 ] 그리디 [문제 접근] 1. 앞에서 부터 큰 수가 와야한다는 점 2. 삭제되는 값이 k개 이어야한다는 점 3. "9999"와 같이 같은 수로 이루어진 문자열이 존재하는 경우를 고려 4. k개가 아직 다 삭제되지 않았는데 문자열을 모두 순회했을 경우를 고려 이렇게 4가지를 염두해두고 풀이한 문제이다 que를 이용하여 문자열을 하나씩 담아주고, 해당 문자열이 이미 que에 들어가있는 숫자보다 크다면, 즉 이미 que에 담긴 숫자가 해당 숫자보다 작다면 pop으로 삭제를 해준다. 이때 k < 0 이면 더 이상 pop을 진행하면 안되기 때문에 k..
programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr [ 알고리즘 ] 그리디 [문제 접근] 이 문제를 풀때, 고려해야할 변수는 두가지이다 1. 해당 알파벳을 찾을 때 다음 알파벳을 찾는게 더 빠른 방법인지, 뒤로 가면서 찾는 방법이 더 빠른지 (ex. A->Z ) 2. 커서를 움직일 떄 왼쪽으로 움직일 것인지, 오른쪽으로 움직일 것인지 문제의 핵심은 2번이라고 생각한다. 카운팅한 알파벳은 'A'로 바꿔주고 '..
[첫번째 문제 접근] - 정수가 0~9가 아닌 10까지 주어진 점과, 옵션이 있을 수도 있고 없을 수도 있다는 조건을 보고, 꼼꼼하게 모든 상황을 고려하여 구현해야겠다고 생각했고, 문자열을 슬라이싱하는 과정 중에 이것 저것 조건을 모두 찾아서 구현했다. 정답이지만 반복되는 부분과 긴 코드를 줄이기 위해 다른 사람들의 풀이를 검토해봄 [두번째 문제 접근] - 다른 분의 코드를 보니 dictionary와 정규표현식 re를 통해 15줄 안에 구현한 코드를 발견하였다 - 정규 표현식을 이용하여 다트 한번에 주어지는 점수,보너스,옵션을 나누고 조건에 따라 dic에 있는 보너스와 옵션을 제곱하고 곱해줌 [알고리즘] - 구현 [첫번째 코드] def solution(dartResult): answer = 0 resul..