개발미정

프로그래머스에 나와있는 2020년 카카오 인턴십 기출문제인 키패드 누르기이다. 왼손 엄지와 오른손 엄지만 사용하여서 번호판을 누르는데, 1, 4, 7 일 때는 왼손 엄지로 3, 6, 9 일 때는 오른손 엄지로, 2, 5, 8, 0 일 때는 왼손 엄지 or 오른손 엄지 중 거리가 가까운 손가락으로 눌러야 한다. 만약 거리가 같을 경우, 오른손 잡이 -> 오른손/ 왼손 잡이 -> 왼손으로 눌러야 한다. 거리를 구하는 과정에서 피타고라스를 사용해서 문제를 풀었는데, 정답률이 55%가 나왔다. 문제에 "엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다." 라고 적혀있기 때문에, 거리를 구할 때 피타고라스가 아니라, x의 이동 칸수 + y의 이동 칸수로 구해줘야..

풀이 다음과 같은 방법으로 풀었다. https://thisis-undefined.tistory.com/66 [프로그래머스] 베스트앨범 Python 프로그래머스에서 해시 -> 마지막 문제인 "베스트앨범"이다. 각 장르별로 인기있는 음악을 2개씩 골라서 베스트앨범을 만드는 문제이다. 다음과 같은 전략을 이용하여 풀었다. 1. 장르별로 총 play thisis-undefined.tistory.com 정답 코드 #include #include #include #include #include using namespace std; vector solution(vector genres, vector plays) { map m; priority_queue pq; vector max; vector answer; for ..

프로그래머스에서 해시 -> 마지막 문제인 "베스트앨범"이다. 각 장르별로 인기있는 음악을 2개씩 골라서 베스트앨범을 만드는 문제이다. 다음과 같은 전략을 이용하여 풀었다. 1. 장르별로 총 plays 합을 구해서 장르별 인기순 배열을 만든다. 2. 만든 배열을 탐색하면서 각 장르별로 play수가 많은 순 + play 수가 같은 경우 고유번호(idx)가 작은 순으로 정렬한다. 3. 정렬한 배열에서 2개씩 꺼내는데, 여기서 총 1개만 있을 경우도 있기 때문에 조건문을 따로 만들어주었다. (무조건 2개씩 꺼내면 런타임에러가 뜬다.) 배열 정렬하는 것은 lamda를 사용하였다. genres_cnt2.sort(key=lambda x : (-x[0], x[1])) 이 부분을 보면, "genres_cnt2 배열을 정..

프로그래머스에 DFS/BFS -> 3번째 문제인 "단어 변환" 이다. 주어진 단어들만을 돌면서 begin -> target으로 가는 경로 중 최단 경로의 길이를 구하는 문제이다. 주어진 단어들로만 변경이 가능하고, 한 글자만 다를 경우에만 change가 가능하다. def solution(begin, target, words): answer = 0 min_cnt = 0xffff if target not in words: return 0 def dfs(cur, cnt): nonlocal min_cnt # 최소 cnt보다 현재 cnt가 더 큰 경우, 더 볼 필요가 없어지므로 return if min_cnt < cnt: return # cnt가 words의 길이보다 클 경우 이미 모든 경로를 탐색하게 된 것이므..

프로그래머스의 코딩테스트 연습 -> DFS/BFS 문제 중 마지막 문제인 "여행경로" 이다. "ICN"으로 무조건 시작해서 모든 도시를 지나는 경로들 중 알파벳 순서로 되어있는 경로를 구하면 된다. 먼저, 모든 도시를 지나는 경로들 중 알파벳 순서로 먼저인 경로를 구하기 위해서 tickets 배열을 sort 해주었다. 그래야 for문을 돌 때 순서대로 돌 수 있기 때문이다. def solution(tickets): answer = [] s = ["ICN"] visited = [0] * len(tickets) def dfs(cur, visited, tickets, state): nonlocal answer if len(state) == len(tickets) + 1: answer = state return..

실버5단계의 문제이다. N개의 DNA가 주어지고, Hamming Distance가 가장 작게 나오는 DNA 서열을 구하는 문제이다. 이 문제는, 각각의 서열을 인덱스로 접근하여서 가장 많이 나온 알파벳을 추가하는 방식으로 문제를 해결했다. 처음에 문제를 끝까지 다 안읽어서 멀리까지 돌고 돌다가 왔다..ㅎㅎ "그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다." 만약 DNA 서열들의 1번 인덱스가 A 1개, T 1개, G 1개, C 1개 있다고 했을 때 A를 추가해주면 되는데, 위에 문장을 안읽고 각각 넣어보고 다른 서열들과 비교해서 Hamming Distance가 가장 작은 것을 찾는 방식으로 풀다가 포기했다..ㅎ 오늘의 교훈문제 끝까지 읽자..^~^ 해결코드 N, M = map..

입력받은 배열이 pho라고 하고, 최대값을 저장할 배열이 dp라고 하자. n이 1인 경우, 최대값은 pho[1]이다. n이 1보다 큰 경우, 다음과 같은 점화식을 따른다. dp[n] = max(dp[n-1], dp[n-2] + pho[n], dp[n-3] + pho[n-1] + pho[n]) 이게 어떻게 적용되는 건지 보자. 각각 n일때의 최대값이다. n=3보다 큰 경우 - n일때 값을 포함시키지 않은 값(dp[n-1]) - n-2일때 포함 안하고, n-1과 n일때만 포함시키는 값(dp[n-3]+pho[n-1]+pho[n]) - n-1번째 포함 안하고 n번째 포함하는 값(dp[n-2]+pho[n]) 중 최대값이 dp에 저장된다. N = int(input()) pho = [0] for n in range(..

브론즈이지만 정답비율이 33%로 낮은 문제이다. DP가 기초단계라면 이 문제 추천한다! Top-down / bottom-up 두 가지 방법으로 접근할 수 있다. 나는 브루트포스 / bottom-up 두 가지 방법으로 풀었고, Top-down 으로 푸는 방법은 런타임 에러가 뜨는 상태이다..! 1. 브루트포스 N = int(input()) five_max = 5000//5 three_max = 5000//3 min_count = three_max for i in range(three_max,-1,-1): total = 3*i if total == N and i < min_count: min_count = i else: for j in range(0,five_max+1): total = 5*j + 3*i i..