본문 바로가기

Algorithm

 (77)
[프로그래머스] 위클리 챌린지 12주차 - 피로도 (Python) 코딩 테스트 연습 - 피로도 [위클리 챌린지 12주차] 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 풀이 1. 들어갈 던전들의 순서들의 경우를 찾는다. 2. 탐험 순서들을 확인하며 최대 입장 던전 수를 찾는다. 제한사항을 확인해보면 던전의 개수는 최대 8개이니 Permutation을 사용하면 최대 4만 개 정도의 경우의 수가 생깁니다. 그렇게 많지 않은 경우이니 간단한 반복문을 통해 확인할 수 있습니다. from itertools import permutations def solution(k, d..
[프로그래머스] 위클리 챌린지 10주차 - 교점에 별 만들기 (Python) 코딩 테스트 연습 - 교점에 별 만들기 [위클리 챌린지 10주차] 코딩테스트 연습 - 10주차_교점에 별 만들기 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 참신한 유형의 별 찍기 문제였습니다ㅎㅎ (옛 추억 새록새록..) 풀이 1. 모든 정수 좌표들을 찾는다. 2...
[프로그래머스] 위클리 챌린지 9주차 - 전력망을 둘로 나누기 (Python) 코딩 테스트 연습 - 전력망을 둘로 나누기 [위클리 챌린지 9주차] 코딩테스트 연습 - 9주차_전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 풀이 제 풀이 방식은 간단합니다. 노드의 개수가 최대 100개이니까 노드 간의 선을 하나씩 잘라보고 확인해도 연산이 많지 않습니다. 1.wires를 차례대로 없다고 가정한 뒤 1번 노드부터 BFS 2. 나뉜 전력망(노드들)의 차이를 구한다. Code from collections import defaultdict, deque def solution(n, wires): answer = flo..
[프로그래머스] 코딩테스트 연습 - 빛의 경로 사이클 (Python) 코딩 테스트 연습 - 빛의 경로 사이클 [월간 코드 챌린지 시즌3] 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 챌린지에 참가해서 풀 때 분명 로직은 맞다고 생각되는데 채점을 하면 0점이 나와서 프로그래머스에 나오면 반드시 풀겠다고 다짐했던 문제입니다ㅋㅋ.. 참가 당시 참 화가 났던 문제... 풀이 풀이를 간단히 정리해보면 다음과 같습니다. 1. visit을 저장할 3차원 배열생성 2. cycle 완전 탐색 문제가 겁을 주기는 하지만 문제를 잘 이해하고 접근한다면 어려울 것이 ..
[프로그래머스] 코딩테스트 연습 - N으로 표현 (Python) 코딩 테스트 연습 - N으로 표현 [DP] 코딩테스트 연습 - N으로 표현 programmers.co.kr 처음 문제를 보았을 때 DP보다는 BFS가 먼저 떠올라서 BFS로 한참을 시도하다가 처리해야 하는 경우가 너무 많아져서 DFS로 변경했네요. 풀이 1. DFS를 이용한 완전 탐색 DFS를 사용하면 하나의 단계에서 4가지 갈래가 나오게 됩니다. 그리고 완전 탐색을 진행하므로 일정한 크기의 트리구조를 순회하는 것과 같아져서 일정한 속도로 탐색할 수 있게 됩니다. Code from collections import deque def dfs(base, target): queue = deque([[0, 0]]) mins = -1 while queue: curr, step = queue.pop() if cur..
[프로그래머스] 위클리 챌린지 5주차 - 모음사전 (Python) 코딩 테스트 연습 - 모음사전 [위클리 챌린지 5주차] 코딩테스트 연습 - 5주차_모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 확률 문제를 오랜만에 보니 생각보다 쉽지 않았던 문제였습니다. 풀이 각 자리별로 앞서는 단어들의 개수를 센다. 먼저 각 자리별로 가능한 단어들의 개수를 알아야 합니다. 예를 들어 'A'로 시작하는 단어들의 개수는 \( 5^1+5^2+5^3+5^4 \)로 781개가 되고 다른 모음들도 마찬가지입니다. 즉 모음에 상관없이 단어를 왼쪽 정렬한다고 생각한 뒤 단..
[프로그래머스] 코딩테스트 연습 - 베스트앨범 (Python) 코딩 테스트 연습 - 베스트앨범 [Hash] 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 Dictionary에 [장르의 전체 재생수, [(인덱스, 재생수)]]의 형태로 저장하고 다음 순서에 따라서 정렬하여 해결했습니다. 가장 많이 재생된 장르부터 장르내에서는 가장 많이 재생된 곡부터 재생수가 같다면 인덱스가 작은것 부터 문제를 풀면서 Hash보다는 정렬시에 lambda식을 사용하는 것이 더 중요하게 여겨졌던것 같습니다. Code def solution(genres, plays): answer, md..
[프로그래머스] 위클리 챌린지 3주차 - 퍼즐 조각 채우기 (Python) 코딩 테스트 연습 - 퍼즐 조각 채우기 [위클리 챌린지 3주차] 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 문제를 천천히 읽어보면 설명을 왜 그렇게 어렵게 적어놨나 싶네요..ㅎㅎ 물론 쉽지 않은 문제였고 프로그래머스에서 Python으로 알고리즘을 풀며 코드가 가장 길었던 문제였던 것 같..

티스토리툴바