코딩기록

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제는 전형적인 최단 경로 문제이며 플로이드 워셜 알고리즘을 이용하면 수월하게 풀 수 있었다. 플로이드 워셜 알고리즘을 알아야 풀 수 있어서 이 알고리즘을 모른다면 아래의 링크를 참고하면 좋을 것 같다. https://it-garden.tistory.com/247 플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현 플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 최소 카메라를 설치해야하므로 그리디 방식으로 나간 시점 기준으로 확인한다. 두 풀이 모두 진출시점 기준으로 작성된 코드이다. 첫번째 풀이 - 카메라에 걸리는지 확인하는 check 리스트를 두고 모든 구간을 검사하는 방법 def solution(routes): answer = 0 length = len(routes) check = [0] * length # 카메라에 걸리는지 확인하는 리스트 routes.sort(key = lambda x: x[1]) # 진출 시점 기준..

https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr costs 리스트를 비용 기준으로 정렬해야하는 것까진 생각했는데 그 뒤로는 어떻게 접근해야할지 모르겠어서 구글링을 했다.. 구글링을 했더니 이 문제는 Kruskal 알고리즘으로 풀면 된다는 사실을 알게 되었다. Kruskal 알고리즘이 뭔지 몰라서 공부를 한 후 코드를 짰더니 수월하게 해결할 수 있었다. 이 알고리즘을 알아야 풀 수 있는 문제였다 Kruskal 알고리즘 - 탐욕적인 방법을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 처음 생각한 문제 풀이는 people 리스트를 오름차순으로 정렬한 다음 최소값 두 개를 가져와 limit보다 크면 최소값 하나만 리스트에서 빼고 limit보다 작거나 같으면 최소값 두 개를 리스트에서 빼는 로직으로 코드를 짰다. 그런데.... 일부는 맞았지만 일부는 실패가 떴다..ㅠㅠ 질문하기를 보니 내가 생각한 로직이 틀린거 였다....

https://programmers.co.kr/learn/courses/30/lessons/42891# 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr import heapq def solution(food_times, k): if sum(food_times)

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr def solution(number, k): num = [] for n in number: while num and n > num[-1] and k > 0: k -= 1 num.pop() num.append(n) if k != 0: num = num[:-k] return ''.join(num) 입력받은 number에서 큰 수만을 뽑아야 하므로 큰 수를 담을 num 리스트를 생성한다. for문을 통해 number배열을 돌면서 num에 큰 수만을 담는다. while문을 통해 num에 담긴 숫자보다 현재 숫자가 크면 현재 숫자보다 큰 숫자만 담..

https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱을 움직일 때 움직인 마지막 위치에서 최소거리를 구해야하는 줄 알고 생각하다가 방법이 생각나지 않아서 다른 사람 풀이를 보려고 검색했는데 완전히 잘못 이해하고 있었다...ㅋㅋㅋㅋ 다음 위치로 넘어가면 조이스틱이 A에서 시작하는 것이었다... 이 사실을 알고 다시 생각해보았더니 방법이 생각났다 이 문제는 상하로 움직이는 로직과 좌우로 움..

https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr def solution(n, lost, reserve): student = [0] * (n+2) answer = 0 # 여분 체육복 있는 사람은 값 1로 만들기 for r in reserve: student[r] += 1 # 체육복을 안가지고 온 사람은 값 -1로 만들기 for l in lost: student[l] -= 1 # 체육복을 입을 수 있는 사람의 최댓..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr import heapq def solution(operations): heap = [] for operation in operations: o = operation.split(' ') # 명령어 값 분리하여 저장 # 명령어에 따라 처리하는 부분 if o[0] == 'I': heapq.heappush(heap, int(o[1])) #명령어가 'I 숫자'인 경우 else: if len(heap) > 0: # 명령어가 'D 1'인 경우 if o[1] == '1': heap.pop(heap.index(heapq.nlargest(1, heap)[0..

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 처음엔 이렇게 코드를 짰었습니다.. 애초에 소요시간으로 정렬한 후 현재 시점을 알 수 있는 now를 사용하여 작업 요청부터 종료까지 걸리는 시간을 계산하였습니다. 그런데....마지막 테스트케이스 빼고 다 실패^^가 떴습니다... 생각해보니 jobs = [[0,3], [2,1]]인 경우 이것을 정렬하면 [[2,1],[0,3]] 이 되는데 이 순서대로 실행이 ..