[프로그래머스] 등산코스 정하기 - Python
2023. 6. 30. 01:10
Algorithm/프로그래머스
🤔 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😀 풀이 해당 문제는 최단 경로 문제의 변형으로 최단 경로문제가 익숙하시다면 다익스트라 알고리즘을 떠올리기까지는 비교적 쉬울 것 같습니다. 다만 저처럼 아무생각 안하고 다익스트라를 적용하게되면 시간초과를 맞게됩니다..ㅠ 처음 생각했던 풀이는 모든 출입구에 대하여 (출입구 -> 산봉우리 -> 출입구)의 최단경로를 구하는 방식을 사용했는데 이렇게 되면 N번의 다익스트라를 수행해야해서 시간초과가 나게되죠. 문제를 다시 천천히 읽어보니 2가지 포인트를 찾을 수 있었습니다. 첫 번째는 (출입구 -> 산봉우리)..
[프로그래머스] 길 찾기 게임 - Python
2023. 3. 1. 05:12
Algorithm/프로그래머스
🤔 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😀 풀이 위 문제는 BST를 구현해본 경험이 있다면 쉽게 풀이할 수 있는 문제입니다. 전체적인 풀이 방향이 BST의 insert, 전위 순회, 후위 순회를 구현하는 문제이기 때문에 이에 대한 내용을 중점적으로 설명해보도록 하겠습니다. 먼저 문제에서 y축의 크기가 클수록 BST 상단에 위치해야하므로 아래 코드와 같이 문제에서 주어진 nodeinfo를 정렬해줍니다. 이때 노드의 y값을 기준으로 정렬합니다. y값을 기준으로 정렬하게 되면 순서대로 노드들을 확인했을 때 부모 노드부터 트리에 삽입할 수 있게 ..
[프로그래머스] 조이스틱 - Python
2022. 4. 4. 04:20
Algorithm/프로그래머스
🤔 문제 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 😀 풀이 해당 문제는 프로그래머스의 그리디 유형으로 올라온 문제인데.. 테스트 케이스 추가 전에는 정답 처리가 되었다가 다시 채점해보니 틀렸다고 나와 재풀이한 문제입니다. 그리디로 풀었던 방법은 현재 위치를 기준으로 'A'가 아닌 곳 중 가장 짧은 곳으로 가서 변경하고 이를 반복하는 작업을 했습니다. 그런데 이런식으로 풀면 반례가 생깁니다...! 대표적으로 "BBBBAAAABA" 가 있습니다. 그리디 방식을 사용할 경우 아래와 같이 ..
[프로그래머스] 양과 늑대 - Python
2022. 3. 4. 22:45
Algorithm/프로그래머스
🤔 문제 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 😀 풀이 해당 문제는 DFS를 사용하여 풀이했습니다. 우선 문제 풀이를 위해 아래 두 가지 기능이 필요하다고 생각하여 함수 두 개를 작성했습니다. 현재 노드에서 어떤 노드를 가볼 수 있는지 체크하는 함수(getCanGoEdges) 가볼 수 있는 노드에 가보며 양과 늑대의 개수를 갱신하는 함수(DFS) # ..
[프로그래머스] 경주로 건설 - Python
2022. 2. 21. 04:17
Algorithm/프로그래머스
🤔 문제 https://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 😀 풀이 본 문제는 DFS와 메모제이션 기법을 사용해서 풀이했습니다. DFS를..
[프로그래머스] [1차] 셔틀버스 - Python
2022. 2. 13. 19:32
Algorithm/프로그래머스
🤔 문제 https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 😀 풀이 본 문제의 핵심은 콘이 마지막 버스에 가장 늦게 탑승해야 한다는 것입니다. 출근자들을 순서대로 버스에 태워 보낸다고 생각하고 마지막 버스에 자리가 남는다면 마지막 버스 출발시간에 도착하면 되고 마지막 버스가 다 차있다면 마지막 버스에 ..
[프로그래머스] k진수에서 소수 개수 구하기 - Python
2022. 2. 10. 18:15
Algorithm/프로그래머스
🤔 문제 https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 😀 풀이 본 문제는 문제 조건에 맞는 단순 구현 문제였습니다. 풀이 과정은 아래의 세 단계로 나눌 수 있습니다. 1. 양의 정수 n이 들어왔을 때 이를 소수로 변환하는 과정 2. 문제 조건에 맞게 소수 판단의 대상이 될 숫자들을 확인하는 과정 3. 2번 과정에서 찾은 숫자들이 소수인지 확인하는 과정 위..
[프로그래머스] 주차 요금 계산 - Python
2022. 2. 6. 02:24
Algorithm/프로그래머스
🤔 문제 https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 😀 풀이 주차 요금 계산 문제는 입차하는 차량과 출차하는 차량을 관리하는 dictionary, 각 차량의 주차 시간을 관리하는 dictionary 즉, 두 개의 dictiona..
[프로그래머스] [3차] n진수 게임 - Python
2022. 2. 4. 00:51
Algorithm/프로그래머스
🤔 문제 https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 😀 풀이 본 문제는 10진수로 주어진 숫자를 n진수로 변환하면 쉽게 풀 수 있는 구현 문제입니다. n진수 변환의 경우 풀이 코드에 convert라는 함수로 정의해놓았습니다. 또한 진수 변환의 경우 참고할만한 코드가 많으므로 설명은 생략하겠습니다. 게임에 참여하는 인원(m)과 튜브가 미리 구할 숫자의 개수(t)를 고려해보았을 때 최대 t ..
[프로그래머스] [3차] 파일명 정렬 - Python
2022. 2. 1. 20:50
Algorithm/프로그래머스
🤔 문제 https://programmers.co.kr/learn/courses/30/lessons/17686 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 😀 풀이 본 문제는 주어진 파일명 배열을 몇 가지 조건에 따라 정렬하면 되는 문제입니다. 따라서 배열을 정렬하는 기준인 key 값에 적절한 함수를 넣어주면 풀이할 수 있음을 쉽게 떠올릴 수 있습니다. 문제에서 주어진 정렬 조건은 크게 두 가지가 있습니다. 1. HEAD 부분 HEAD 부분의 경우 파일명의 맨 앞부분부터 숫자가 나오기 직전까지입..