Problem Solving/BOJ-Platinum (4) 썸네일형 리스트형 (Python) 백준 3679 - 단순 다각형 https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net 아이디어 볼록 껍질(컨벡스 헐) 알고리즘(https://monogatary.tistory.com/57)을 응용해서 풀 수 있다. 먼저 볼록 껍질 알고리즘을 통해 껍질의 절반을 구한다. 껍질에 포함되지 않은 점들을 순서대로 연결한다. 코드 # ccw 알고리즘 def ccw(a,b,c): return ((b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0.. (Python) 백준 11046 - 팰린드롬?? https://www.acmicpc.net/problem/11046 11046번: 팰린드롬?? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 아이디어 - 문자열 내의 팰린드롬을 찾는데 효율적인 매내처 알고리즘(https://monogatary.tistory.com/28) 을 활용해야 한다. - 입력받은 숫자가 1자리수가 아닐 수도 있기 때문에 입력받은 문자열을 그대로 활용하면 안 되고 split을 사용해야 한다. - s번째 부터 e번째 까지의 부분문자열의 팰린드롬 여부를 체크하려면, 두 문자의 중간위치의 최대 팰린드롬 반지름 길이를 가져와야 한다. 글자 사이에 0을 끼워넣.. (Python) 백준 11375 - 열혈강호 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 아이디어 - 이분 그래프의 한 그룹에서 다른 그룹으로 간선을 만들 때, 각 정점에 최대 1개의 간선만 존재해야 한다면 최대 몇 개의 간선을 만들 수 있는지 묻는 문제이다 - 이와 같은 유형의 문제는 이분 매칭이라는 알고리즘을 통해 해결할 수 있다 - 이분매칭에 대해서는 따로 정리할 예정 코드 import sys input=sys.stdin.readline # 이분 매칭 함수 def dfs(.. (Python) 백준 11003 - 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 아이디어 - 입력값이 크기 때문에 배열 전체를 O(n) 정도로 탐색할 수 있어야 함 - 큐를 이용하여 배열의 원소를 1번씩만 탐색하는 방법을 사용 - 순차적으로 배열을 탐색하여 큐에 새 값을 추가하기 전에 다음의 연산을 먼저 시행 - 큐의 마지막 값이 새 값보다 클 시 마지막 값을 삭제 - 큐의 첫 값이 윈도우 범위를 벗어날 시 첫 값을 삭제 - 큐에 새 값을 추가.. 이전 1 다음