본문 바로가기

알고리즘

 (113)
[탐욕법] 프로그래머스 L1 '체육복' (Python) https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 체육복을 잃어버린 학생이 여벌의 체육복이 있을 수 있다는 조건을 생각해야 함 1번의 학생이 있다면 lost와 reserve에 있는 학생 번호를 지움 체육수업을 들을 수 있는 학생을 구해야 하므로, 체육복을 잃어버린 학생 수를 제외하고 결괏값을 도출 (set 또는 for문을 사용할 수 있다) 주어진 배열이 정렬되어있지 않을 수 있으므로 정렬 여벌의 체육복을 가진 학..
[탐욕법] 난이도1, 2019 국가 교육기관 코딩 테스트 '큰 수의 법칙' (Python) '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 방법이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간..
[알고리즘] 탐욕법 / 그리디(Greedy) 탐욕법이란? 전체가 아닌 현재 상태에서 최선의 선택을 하는 알고리즘 전체 탐색보다 빠르지만 반드시 정답을 도출하지 않는다 탐욕법의 조건 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는다 각 부분에서의 최적 해결이 최종 해결방법이다 주의사항 탐욕법이 적용 가능한 문제인지 아닌지를 판별할 수 있어야 한다. 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이내믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민해보..
[정렬] 프로그래머스 L1 '실패율' (Python) https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr python 배열의 count() 함수를 이용하여 계산해야겠다고 생각 실패율을 기준으로 내림차순 정렬하되, 출력은 스테이지 번호를 출력하라 했으므로 dict() 사용 스테이지에 도달한 플레이어 수는 스테이지가 올라갈수록 그 전의 모든 플레이어 수가 없어지므로 total 변수 사용 ZeroDivisonError를 대비하여 try/except 구문 처리 #1차시도 ..
[정렬] 난이도1, 백준 18310번 '안테나' (Python) https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 집의 위치가 정렬되어 있지 않으므로 정렬 정렬 후 배열의 중앙값에 안테나를 설치했을 때 거리의 총합이 최소가 됨 집의 개수를 반으로 나누면 중앙값이 나옴. 단, 배열은 0부터 시작하므로 1을 빼줌 '''입력예시 4 5 1 7 9 ''' n = int(input()) house = list(map(int,input().split())) house.sort() print(house[(n-1)//2]) 필요 없이 주어지는 입..
[Dijkstra] 유명 알고리즘 대회 '전보' (Python) 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때..
[Dijkstra] 프로그래머스 L3 '가장 먼 노드' (Python) https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 하므로 다익스트라 알고리즘을 이용 간선은 양방향이므로 그래프에 노드를 서로 추가 가장 멀리 떨어진 노드를 구해야 하므로 max() 메서드 이용 import heapq def dijkstra(start,distance,graph): q=[] heapq.heappush(q,(0,start)) distance[start]=0 while q: dist,now = heapq.heappop..
[알고리즘] 정렬 - (선택/삽입/퀵/계수/버블/병합/라이브러리) 정렬 (sorting) 이란? - 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 - 정렬은 프로그램 작성시 빈번하게 필요로 함 - 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 > 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음 선택 정렬 다음과 같은 순서를 반복하며 정렬하는 알고리즘 1. 주어진 데이터 중, 최소값을 찾음 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 https://visualgo.net/en/sorting 시간 복잡도 : O(N^2)..
LIST

티스토리툴바