본문 바로가기

알고리즘10

[백분] 1107: 리모컨 파이썬 풀이 - 부르트포스 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 다행히 리모컨은 부시지 않았습니다. 처음에는 그리디로 접근을 하다가 반례 해결이 도저히 안돼서, 부르트포스 방식을 생각하게 됐습니다. 풀이는 다음과 같습니다. 1. 채널 버튼을 누르지 않고 이동하는 경우를 구한다. 2. 누를 수있는 채널 버튼들로 중복조합을 구한다. 3. 중복 조합을 통해서 이동하는 경우가 버튼을 최소로 누르는 방법이면 업데이트한다. 풀이는 좋았으나, 실수를 연속해.. 2021. 8. 16.
[백준] 1011: Fly me to the Alpha Centauri 파이썬 풀이 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제설명 어떤 이동거리에 대해 움직이는 최소 횟수를 구하는 문제입니다. 이동 방법은 1칸 점프 부터 시작해서, n 번째에 x칸 점프 했다면 n+1 번째는 x-1 or x or x+1 칸 점프할 수 있습니다. 끝 지점은 반드시 1칸 점프로 도착해야합니다. 풀이과정 1. 이동거리가 n일 때, 최소 이동횟수를 구해봤습니다. 2. 위를 구해보니, 특정 이동 횟수에 대해 갈 수 있는 최대 거리의 규칙이 보였습니다. 3. 이동횟.. 2021. 7. 28.
[백준] 17367: 공교육도박 파이썬 풀이 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 풀이 게임의 진행 주사위를 굴릴 기회가 있으면, 현재 상태에 대해 기댓값(현 상태에서 한 번더 주사위를 굴렸을 때의 기댓값)을 판단한다. 판단한 기댓값이 현재 상금(현재 게임을 멈췄을 때 얻을 수 있는 상금)보다 높다면 go 아니라면 멈추고 현재 상금을 받음 이러한 메커니즘 때문에, 주사위를 굴릴 기회가 많을 수록 기댓값이 높아짐 풀이 d[x][i][j][k] : 굴릴 기회가 x 번 남았을 때, 주사위 눈이 i, j, k가 나왔을 때 얻을 수 있는 상금(혹은 상금의 .. 2021. 7. 15.
주요 알고리즘 설명 및 문제 모음 냅색(knapsack) 알고리즘 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 gsmesie692.tistory.com 12865: 평벙한 배낭 2021. 7. 7.
[알고리즘] 최단경로 - 다익스트라 알고리즘 (Dijkstra's algorithm) 동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다. 풀이 언어는 파이썬을 사용했습니다. 목차 최단 경로 문제 다익스트라 알고리즘 우선순위 큐를 사용한 다익스트라 알고리즘 최단 경로 문제 최단 경로 문제 중 한 시작점으로 부터 다른 노드 까지 가는데 비용이 얼마나 걸리는 지를 구할 때 사용하는 알고리즘이 다익스트라 알고리즘 입니다. 기본적으로 최단 경로 문제는 방향이 있고 가중치가 있는 그래프가 주어집니다. 따라서 위의 그래프는 다음과 같이 입력을 받습니다. 6 11 1 1 2 2 1 3 5 1 4 1 2 3 3 2 4 2 3 2 3 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2 코드에선 다음과 같은 2차원 배열로 구현 됩니다. [[], [(2, 2), (3, 5), (4, 1)], .. 2021. 3. 10.
[알고리즘] 파이썬에서 순열 조합 구하기 - itertools, permutations, combinations 파이썬에선 itertools 모듈의 permutations 함수를 이용해 쉽게 순열을 구할 수 있습니다. 다음의 코드로 리스트의 순열을 구할 수 있습니다. import itertools numbers = '123' p = list(map(''.join, itertools.permutations(numbers))) # p -> ['123', '132', '213', '231', '312', '321'] pools = ['a', 'b', 'c'] p = list(map(''.join, itertools.permutations(numbers))) # p -> ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] p = list(itertools.permutations([1,2,3]) #.. 2021. 2. 27.
[알고리즘] 에라토스테네스의 체 에라토스테네스의 체는 소수(prime number)를 구할 때 가장 기본적으로 사용되는 알고리즘 입니다. 소수를 구하는 것은 기본적으로 완전탐색을 사용하는데, 이미 검사한 수는 스킵하여 효율성을 높였습니다. + 소수는 0과 1을 제외한 2부터 시작됩니다. 코드에서 prime[0], prime[1]이 True여도 이는 소수가 아니므로 사용할 때 주의해야 합니다. 파이썬 코드 N = 10000 # N-1번까지의 소수 구하기 prime = [True]*(N+1) for i in range(2, int(N**0.5)): # 2 부터 N-1의 제곱근 까지 검사 if prime[i]: for j in range(i+i, N+1, i): prime[j] = False 매우 간단하지만 막상 사용하려고 하면 쉽게 떠오르.. 2021. 2. 26.
[백준] 6236: 용돈 관리 파이썬 리뷰 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. 전형적인 이분 탐색 문제입니다만... 고려하지 못한 부분과 실수한 부분이 많아 이를 되짚어 보려합니다. 문제 풀이는 적절한 금액(조건을 만족하면서 최소가 되는)을 이분탐색으로 찾는 것입니다. 처음에 제가 잘못 생각한 것은 하루 소비 금액 > 뽑을 수 있는 금액(설정 금액) 이어도 하루에 여러번 돈을 뽑으면 된다는 것이었습니다. 문제에서 돈을 뽑을 때는 가지고 있는 돈을 모두 반환하고 뽑기 때문에 잘못된 생각입니다. 이 때문에 설정 .. 2021. 2. 23.

티스토리툴바