목록알고리즘 문제풀이/프로그래머스 (12)

매일 매일 성장하는 섭섭군

[Seop's의 코드풀이] 프로그래머스 보석쇼핑 - Python

programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제요약 배열에 있는 문자열의 종류를 모두 포함하는 최소 구간을 찾으면 되는 문제입니다. 간단하게 모든 경우의 수를 생각하면서 문제를 풀게되면 시간초과가 나게됩니다. 문제풀이 IDEA 시간 초과 없이 문제를 해결하기 위해 다음과 같은 고민을 진행하였습니다. 배열에 있는 문자열을 한번만 순환하여 찾는 방법이 없을까? 특정 구간 안에 있는 문자열의 종류의 수를 한번에 찾을 수 없을까? 먼저 한번만 순환하여 찾는 방법으로 지렁이 ..
알고리즘 문제풀이/프로그래머스 2020. 10. 14. 23:19
[Seop's의 코드풀이] 프로그래머스 경주로 건설 - Python

programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제요약 2차원 배열에서 최단거리를 구하는 문제에서 방향을 바꾸었을때 추가적인 비용이 발생하는 문제이..
알고리즘 문제풀이/프로그래머스 2020. 10. 13. 16:15
[Seop's의 코드풀이] 프로그래머스 호텔방 배정

programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 문제요약 문제를 읽어보면 쉽게 이해할 수준의 문제이다. 시간복잡도를 고려하지만 않는다면 방이 차있을 경우 1씩 더해가면서 확인하는 작업을 하면 정확성 테스트는 통과 할 수 있다. 하지만 1씩 더하는 방법을 사용할 경우 효율성 테스트에서 시간초과가 발생한다. 즉 방이 차있을경우 일일이 확인하지 않고 빠르게 배정된 방번호보다 크면서 비어있는 방을 찾는것이 관건이다. 문제풀이 IDEA 이번 문제의 주요 IDEA는 방이 비어 있는 방을 가리키는 것이다. 주요 알고리즘은 다음과 같다. 방 딕셔너리를 생성하고 다음과 같은 Key, Value 값을 가지도록 한다. ..
알고리즘 문제풀이/프로그래머스 2020. 10. 12. 17:52
[Seop's의 코드풀이] 프로그래머스 자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제요약 이번에 풀어본 문제는 2020 카카오 블래인드 채용 코딩테스트에서 출제되었던 문제입니다. 이차원 배열인 Key 와 Lcok이 주어집니다. 각 배열은 0 과 1로 구성되어 있습니다. Key를 회전시키거나 이동하여 Lock에 맞다면 True를 Reutrn 하고 맞지 않는다면 False를 리턴합니다. Key는 Lock을 벗어나도 됩니다. 문제풀이 IDEA 본 문제를 풀때 눈여겨 봐야할 것이 N,M의 크기입니다. 둘다 20..
알고리즘 문제풀이/프로그래머스 2020. 8. 30. 20:56
[Seop's의 코드풀이] 프로그래머스 가사 검색 - Python

programmers.co.kr/learn/courses/30/lessons/60060# 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 개요 이번에 풀어볼 문제는 2020 Kakao 블라인드 채용에 출제되었던 가사 검색이란 문제입니다. queries에 있는 '?'가 섞인 문자열이 있는데 각 해당하는 문자열이 words에 있는 것과 몇개나 매칭이 되는지 알아봐야 합니다. 단순하게 모든 문자열을 비교한다면 풀릴 것 같은 문제입니다. 하지만 그렇게 한다면 시간은 굉장히 오래걸리게 됩니다. 문제 풀이 IDEA 문자열들이 있는 집합에서 특정 문자열을 효율적으로 검색하기 위해서 Trie 라는 자료구조를 사용 할 것 입니다. Trie 에 대한 설명은 다음 링크에 있습니다. 설명보기 queries..
알고리즘 문제풀이/프로그래머스 2020. 8. 28. 01:31
[Seop's의 코드풀이] 프로그래머스 줄 서는 방법 - Python

programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 문제 요약 서로다른 자연수 n 개를 나열하는 방법의 수 중 k 번째 수는 무엇인지 확인하는 문제이다. 모든 경우를 나열한 후 사전순으로 정렬 할 수 있지만 시간이 너무 오래 걸리는 문제가 발생한다. 그러므로 우리는 바로 K 번째 수를 구할 수 있어야 한다. 문제풀이 아이디어 서로다른 n개의 자연수로 이루어진 수열의 맨 앞자리가 수가 같은 경우는 한정되어 있다. ..
알고리즘 문제풀이/프로그래머스 2020. 8. 19. 20:24
[Seop's의 코드풀이] 프로그래머스 최고의 집합 - Python

programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr 문제요약 이번에 풀어볼 '최고의 집합'이란 문제는 s 라는 자연수를 n개의 자연수를 더해서 만드는 문제이다. 그 중에서 각각의 자연수의 곱이 가장 큰 경우를 찾는것이다. 그냥 단순하게 생각하더라도 모든 경우를 고려한다면 시간이 너무 오래 걸린다는 것을 알 수 있다. 그래서 n개의 자연수 중 합이 s면서 곱이 가장 크게될 값을 한번에 찾아야 한다. 문제풀..
알고리즘 문제풀이/프로그래머스 2020. 8. 19. 13:06
[Seop's의 코드풀이] 프로그래머스 실패율 (2019 KAKAO BLIND RECRUITMENT) - Python

이번에 풀어볼 문제는 프로그래머스에 있는 실패율이라는 문제입니다. 2019년 카카오 블라인드 채용에 나왔던 문제인데요 문제는 다음과 같습니다. www.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 요약하면 다음과 같습니다. N 개의 스테이지가 존재하고 stages란 배열에 참가자들이 현재 도전중인 스테이지가 주어진다. 현재 도달한 스테이지는 아직 클리어하지 못한 것이다. 각 스테이지마다 실패율 : (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수)/ (..
알고리즘 문제풀이/프로그래머스 2020. 5. 12. 12:10
Prev 1 2 Next