알고리즘(21)
-
[프로그래머스] 위클리 챌린지 3주차 퍼즐 조각 채우기 파이썬 풀이
※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 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 문제 접근 문제가 상당히 복잡합니다. 접근 방식을 그림과 함께 설명할 예정이니 차근차근 집중하여 보..
2021.09.02 -
[백준] 16206 롤케이크 파이썬 풀이
※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 문제 접근 1. 자를 롤케이크의 크기가 10보다 작은 경우 자를 이유가 없기 때문에 넘겨준다. 2. 크기가 작은 롤케이크 먼저 자른다. 만약 롤케이크의 크기가 10 20 20 30 50 이 있고, 자르는 횟수 제한이 4인 경우 IF : 크기가 작은 롤케익롤케이크 먼저 자를 경우 10 사이즈의 롤케이크는 8개가 생김 IF : 크기가 큰 롤케익..
2021.08.25 -
[프로그래머스] 섬 연결하기 파이썬 풀이
※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ 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를 오름차순으로 정렬하고 해당 간선을 방문했는지 안 했는지 확인해가며 풀어가는 문제이다. 문제 풀이 (with Python) def solution(n, costs): costs=sorted(costs, ke..
2021.08.07 -
[백준] 19638 센티와 마법의 뽕망치 파이썬 풀이
※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/19638 19638번: 센티와 마법의 뿅망치 마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수 www.acmicpc.net 고려사항 1. 키가 1인 경우 더 이상 줄어들 수 없기 때문에 뽕망치의 영향을 받지 않는다 2. 거인의 최대키가 센티의 키보다 작으면 더 이상 뽕망치를 쓸 이유가 없으므로 멈춰줘야 한다. 3. 힙을 통해 풀 경우, 해당 문제를 풀기 위한 힙은 최대 힙이 되어야 하지만, 파이썬은 최소 힙만 제공해준다. 그래서 -1을 곱해 최대 힙으로 접근할 ..
2021.06.22 -
[프로그래머스] 2개 이하로 다른 비트 파이썬 풀이
※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 문제 접근 ◇ 짝수와 홀수의 경우로 나누어서 생각해볼 수 있다. ◇ 짝수인 경우 마지막 bit를 0에서 1로 바꾸면 X보다 크면서 1~2개 비트가 다른 수 중 가장 최솟값이 된다. ◇ 홀수인 경우 크게 2가지 경우로 나뉜다. ➡ 1. 2진수로 전환시 모든 비트가 1인 경우 (EX. 7, 15) ➡ 2. 모든 비트가 1이 아닌 경우 (0이 섞여있는 경우로 9 같은 숫자를 예로 들 수 있다.) ◇ 모든 비트가 1인 경우에는 앞에 있는 01을 10으로 바꿔줍니다. ◇ 모든 비트가 1이 아닌 경..
2021.06.03 -
[백준] 1655 가운데를 말해요 파이썬 풀이
※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 설명 ◇ 해당 문제를 풀기 위해서는 두 개의 heap이 필요하다. ◇ 두 heap의 이름을 각각 leftheap, rightheap이라고 칭한다고 가정하면, ➡ leftheap은 중간값보다 작은 수가 들어가고 rightheap에는 중간값보다 큰 수가 들어간다. ◇ 그림에서는 중간값을 따로 빼두었지만, 중간값도 결국에는 heap 안에..
2021.05.27