분류 전체보기 (53) 썸네일형 리스트형 백준 28357 사탕 나눠주기 파이썬 https://www.acmicpc.net/problem/28357 28357번: 사탕 나눠주기 소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 $X$를 정한 뒤 최종 점수가 $X$점을 넘는 학생들에게 점수가 높은 www.acmicpc.net 간단한 이분탐색 문제였습니다. 최솟값과 최댓값 설정만 잘해주면 쉽게 풀릴것 같습니다. def ch(x):#나눠줘야하는 사탕 개수 체크 함 re = 0 for i in s: if i>x: re+=(i-x) return re n,m = map(int,input().split()) s = list(map(int,input().split())) a,b = 0,max(s)#점수의 최대값이 기준점의 .. 백준 16567 바이너리 왕국 파이썬 반례 O https://www.acmicpc.net/problem/16567 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net flip 횟수를 0이 나올때마다 구하면 시간초과가 나올 수 밖에 없는 문제이다. 0 > 1 로 바꿔줄때 flip 횟수를 구해야 시간초과를 피할 수 있다! 밑에는 반례입니다. 코드 설명은 아래에 하겠습니다. 입력 5 9 0 1 0 0 0 0 1 1 0 1 3 0 1 5 0 1 2 0 답 1 1 1 2 2 오답 0 0 0 1 1 핵심 포인트 정리입니다. 1. 양 옆이 .. 백준 28215 대피소 파이썬 https://www.acmicpc.net/problem/28215 28215번: 대피소 $2$차원 평면의 KOI 마을에 $N$개의 집이 있다. 각 $i$번째 집의 위치는 $(X_i , Y_i)$이다. $i$번째 집과 $j$번째 집 사이의 거리는 $|X_i - X_j | + |Y_i - Y_j |$이다. 즉, 두 집 사이의 거리는 $X$의 차이와 $Y$의 www.acmicpc.net 문제에서 최대 K개의 대피소를 설치할 수 있고 거리가 최소가 될 때 최대값을 구하라고 했으니 백트레킹을 사용하면 모든 경우의 수를 탐색할 수 있어 문제를 풀 수 있을 것이라 생각했다. 그래서 처음에는 문제를 풀기위해 아래와 같이 코딩했었다. import sys def ch(w):#대피소의 개수에 따라 최솟값을 구하는 알고리즘.. 파이썬 정렬 + 예제 문제 추천 알고리즘 문제에서 정렬은 매우 쉬운 알고리즘에 속한다. 물론 정렬을 구현하는 것은 어렵겠지만 우리는 List.sort를 통해 정렬을 해주기 때문에 문제 없다. 아래 사진은 나름 정렬을 요약정리 해본것이다. 기초적인 정렬을 알아봤으니 알고리즘 문제에서 어떻게 쓰이는지 알아보자! 이것을 이해했다면 아래 문제를 풀어보는 것을 추천한다. https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 부족한 글 봐주셔서 감사합니다. :) 파이썬 stack and deque(덱) + 예제 코드 덱은 무엇일까? 덱을 이해하려면 기존의 stack을 이해하고 있어야한다. stack은 후입선출구조를 가지고 있다. 아래 사진을 보면 단번에 이해가 갈것이다. 이제 덱을 알아보자 덱은 기존 stack에서 먼저 들어간 자료를 빼내려면 시간복잡도 O(N)을 소요해 원소를 빼내는 단점을 보완할 수 있는 자료구조이다. 따라서 리스트의 앞부분을 조작하고 싶을때 많이 사용된다. 추후 BFS문제에 필수로 사용되니 꼭 알고 넘어가자.!! stack =[0,2,1,5] 일때 stack.pop(0)을 해주면 stack의 가장 앞부분인 0이 삭제되긴 하지만 시간복잡도 O(N)을 가짐. 놀랍게도 덱을 사용하면 첫번째 원소를 빼는 작업을 O(1)만에 수행할 수 있다. 우선 덱을 사용하려면 모듈을 가져와야 한다. 사진을 통해 설명.. 백준 25917 Prime Arrangement 파이썬 증명 X https://www.acmicpc.net/problem/25917 문제에서 소수만 주어진 이유는 서로 다른 소수 * 소수는 값이 안 겹치기 때문이다. 여기서 알 수 있는것은 문제의 답은 나올 수 있는 모든 조합의 경우의 수인것이다. (P는 고려할 필요가 없음. 조합을 만들고 알맞게 순서를 배치만 하면 되므로) 처음에는 (nCc * n-cCc * n-c-cCc ... *n-c-c...-cC0) * {(c!)**r}을 해주는 방법으로 생각 했다. 하지만 예제의 답이 나오지 않았고 여러 조합으로 해본결과 (nCr * n-rCr * n-r-rCr ... *n-r-r...-rC0) * {(r!)**c-1} 이런 방정식으로 답을 유도했다. 이 답을 유도하기위해 아래와 같은 작업을 해줬다, 아직 수학적 기술이 부족.. 백준 25919 Lost Edge 파이썬 최적화버전 https://www.acmicpc.net/problem/25919 25919번: Lost Edge 새로운 RPG게임인 Lost Edge에는 레이드 시스템이 존재한다. 하지만, 레이드에 참가하기 위해선 일정 레벨 이상을 찍고 레이드 장소에 모여야 한다. 플레이어는 상하좌우 4방향으로 한 칸씩만 움직 www.acmicpc.net https://77dptjd.tistory.com/48 이전 포스팅을 하고나서 코드를 다시 보니 굳이 find함수를 안 만들어도 됐었다. 처음 레벨업 탐색중에 레이드 장소에 갈 수 있다면 레벨업이 끝나고도 다시 갈 수 있기에 처음 레벨업 탐색중에 레이드 장소에 도달했다는 것을 표기해주는 변수를 하나 추가하면 find함수 없이도 문제를 풀 수 있었다. from collections .. 백준 25919 Lost Edge 파이썬 https://www.acmicpc.net/problem/25919 25919번: Lost Edge 새로운 RPG게임인 Lost Edge에는 레이드 시스템이 존재한다. 하지만, 레이드에 참가하기 위해선 일정 레벨 이상을 찍고 레이드 장소에 모여야 한다. 플레이어는 상하좌우 4방향으로 한 칸씩만 움직 www.acmicpc.net 대회 문제중에 풀만한 문제를 찾아보던중 발견한 문제였다. 일반적인 BFS와 다른 점은 heapq과 같이 사용한다는 것이였다. 왔던길을 다시 갈 수 있으므로 갈 수 있는 길을 모두 heapq에 담아 자신의 레벨보다 작은 몬스터들을 먼저 죽여 레벨업을 하면서 갈 수 있는 길을 넓여가면 된다. from collections import deque import heapq import sy.. 이전 1 2 3 4 ··· 7 다음
