알고리즘 & PS69 [Python] 프로그래머스 Lv 3 - 빙고 아싸 빙고! 프로그래머스 Lv 3 빙고 풀이 알고리즘 처음에는, 일단 빙고판을 하나 또 깡으로 복사해서 0으로 모두 채우고, 리스트에 하나씩 있나 검사를 한다음 열이 모두 채워졌나, 행이 모두 채워졌나, 대각선은 되나 이렇게 각각을 검사했다. 어떻게던 풀겠지만 당연히 효율성에서 실패! 따라서 애초에 행과 열, 대각선을 입력 시점에서 모두 검사해야 한다. 이에 따라 행별로 숫자를 기록할때마다 1을 더할 리스트, 열도 1개 만들고, 대각선은 각 방향별로 변수를 미리 만들어둔다. board의 각 칸에 있는 값이 nums에 있는지 검사하면 된다. 근데, 이마저도 그냥 board in nums 를 하는 순간 효율성을 또 통과하지 못한다. 효율성을 위해 nums를 val값 없이, 키 값만 존재해도 dict를 만들어.. 2021. 4. 22. [Python] 프로그래머스 Lv 3 - 등굣길 프로그래머스 Lv 3 - 등굣길 풀이 출처 : https://programmers.co.kr/learn/courses/30/lessons/42898 알고리즘 우선 길찾기는 기본적으로 순열/조합으로 풀 수 있다. 그런데, 문제는 물 웅덩이가 존재한다는 것과 그것이 몇 개인지 모른다는 것이 가장 큰 문제이다. 따라서 순열/조합의 일반화는 절대 불가능하고, 직접 경우의 수를 컴퓨터가 세 줘야 할 것이다. 여기에서, DP로 풀어야 하는 문제임을 눈치챌 수 있다. 기본적으로 자신의 윗칸까지 온 경우의 수와, 좌측까지 온 경우의 수를 더하면 그 자리까지 가는 경우의 수가 될 것이다. 변수는 물웅덩이인데, 물 웅덩이로는 못 오니까 그 칸은 0으로 센다. 또한, 물웅덩이의 추가 변수가 있다. 가장 윗 줄과 가장 왼쪽 .. 2021. 4. 22. [Python] 프로그래머스 Lv 3 - 야근 지수 프로그래머스 Lv 3 - 야근지수 풀이 출처 : https://programmers.co.kr/learn/courses/30/lessons/12927 알고리즘 제곱의 특성 상, 큰 값을 더 크게 만드므로, 남은 N시간 동안, 가장 작업량이 많은 거를 1개씩 줄여 나가면 될 것이다. 즉, 계속 최댓값을 찾아줘야 하는 문제이다. 이에 적합한 자료구조는 최대와 최소를 간편하게 찾아주는 heap 자료구조이다. 다행히, Python에는 heapq 형태로 자료구조가 이미 구현되어 있다. 허나, 문제는 heapq는 Min Heap을 기반으로 하고 있다. 이를 Max로 바꾸려면 어떻게 해야 하나.? 자료구조를 Max로 바꿀 생각을 하지 말고, 주어진 배열이 모두 양수이므로, -1을 곱해서 모두 음수로 만들면 Min H.. 2021. 4. 22. [Python] 프로그래머스 Lv 3 - N으로 표현 DP 문제인데, 단순히 메모이제이션을 하지 않고 조금 다른 방식으로 풀어야 하는 특이한 문제였다. 프로그래머스 강의 내용 바탕으로 주석 추가하여, 내용을 정리하였다. 문제 (아 뭐 이리 문제 매워) programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 알고리즘 정신이 아득해지는 까다로운 문제이다. 처음 접근할때는 9 * 32001 이중리스트를 만들어야 하나 고민했는데 이걸 계산하고 최솟값을 계산하는거 자체가 무리라는 생각이 들었다. 따라서, 그냥 앞의 값을 바탕으로 계산을 때리는 알고리즘만이 가능할 것이다. 1개만 쓰는 경우는 자명하고, 2개만 쓰는 경우는 숫자 2개를 붙이는 경우와 1개인 경우와 1개인 경.. 2021. 4. 21. [Python] 프로그래머스 Lv 1 - 완주하지 못한 선수 Hash를 활용한 풀이 또한 정리하고자 한다. programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 나의 풀이 정렬을 활용하여 풀었다. 단 1명만, 완주하지 못했으므로, 참가자와 완주자 배열을 사전순으로 정렬하면 처음으로 어긋났을 때, 그 시점의 참가자가 완주하지 못한 사람일 것이다. def solution(participant, completion): participant.sort() completion.s.. 2021. 4. 21. [Python] 프로그래머스 Lv 2 - 큰 수 만들기 이번에는 큰 수 만들기에 대한 문제이다. 큰(?) 함정도 있고, 그리디 치고는 길이 잘 보이지 않았다. 강의를 통해 배운 내용을 정리해 보았다. 알고리즘 알고리즘은 간단하다. 1. 맨 앞부터 한 자리씩 정답의 후보라고 생각하고 쓴다. 2. 만일 새로 쓸 수가 직전에 쓴 수보다 크다면 지워버린다. 그 앞도 비교하여 지워버린다. 새로 쓸 수보다 직전의 수가 더 크다면 새로 쓸 수를 써버린다. 3. 단, 지울 수의 개수는 정해져 있으므로, 지울 양이 채워졌으면 지우는 것을 중단해버리고 남은 수를 모두 다 쓴다. 하지만 여기서 큰 함정이 있는데, 이대로 할 경우 987654 처럼, 숫자가 지워지는 경우가 없는 경우가 있다. 이때는, 뒤에서부터 숫자를 지워버리면 되는데, 굳이 이러한 경우를 고민할 거 없이 최종적.. 2021. 4. 21. 이전 1 ··· 8 9 10 11 12 다음