곰퓨타의 SW 이야기

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 정확성만을 고려한 아이디어는 다음과 같다. 정확성만을 고려하여,, 해결한 코드는 다음과 같다. def solution(stones, k): person = 0 while True : temp = 0 for i in range(len(stones)): if stones[i]==0 : temp += 1 if temp >= k: return person else : stones[i]-=1 temp = 0 person += 1 return answ..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 처음에는 다음과 같이 접근하였다. def solution(n, works): answer = 0 for _ in range(n): max_n =max(works) if max_n==0 : break i = works.index(max_n) works[i] -= 1 for work in works : answer ..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 이는 줄세우기가 떠올라서 팩토리얼을 이용해서 문제에 접근하였다. 이를 바탕으로 작성한 코드는 다음과 같다. def factorial(n) : k=1 for i in range(1,n+1): k *= i return k def solution(n): answer = 0 f..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr N-Queen 문제를 해결하기 전, 이 문제를 알고리즘 백트래킹 시간에 다루었던 기억이 나서, 백트래킹에 대해서 다시 짚어보았다. 백트래킹 알고리즘(Backtracking Algorithm) 가치지기 과정을 통해, 해를 찾아가면서 유망하지 않은 경우(non-promising)한 경우 그 경로를 더이상 탐색하지 않..

해결해야하는 문제는 다음과 같았다. 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 처음에 우선, 모든 경우의 수를 구해서 경주로를 건..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 이 문제는 해결하는데 굉장히 오랜 시간이 걸렸다. 무작위로 시간을 탐색하다가, 약 8개정도의 테스트케이스에서 시간 초과가 났다. 계속 고민하던 결과,,,, 문제를 해결하지 못하여 질문하기 및 검색을 해보았다. 검색 결과, 누적 시간이 긴 경우를 찾는 것이기..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 우선 이 문제를 해결하기 위해서는 이진트리 및 전위순회 후위순회를 알아야할 것 같았다. 기본 개념은 다음과 같다. 이진트리 각각의 노드가 최 대 두 개의 자식 노드를 가지는 트리 자료 구조이다. 이진 탐색 트리 이진 탐색의 효율성을 유지하면서 빈번한 자료의 입력과 삭제가 가능하도록 한ㄷ나. - 각 노드의 왼쪽 서브트리는 해당 노..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 인접행렬 형식으로 그래프를 저장한 후, '플로이..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다. answer = [] def dfs(ban_dict, ban_ids, idx, id_set): if len(ban_ids) == idx : if set(id_set) not in answer: answer.append(set(id_set)) return now = ban_..

해결해야하는 문제는 다음과 같았다. https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다. from collections import deque def solution(tickets): answer = deque() ticket_dict = {} for s,d in tickets : if s not in ticket_dict.k..