본문 바로가기

취준

[백준][Python][11722][DP]가장 긴 감소하는 부분 수열 문제 : https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 2020/02/19 - [취준/백준] - [백준][Python][11053][DP]가장 긴 증가하는 부분 수열 불러오는 중입니다... 이 문제에서 배열만 거꾸로 돌면된다. import sys n = int(sys.stdin.readline()) line = [int(i) for i in sy.. 더보기
[백준][Python][6087][BFS]레이저 통신 문제 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. www.acmicpc.net BFS 문제다. 이 문제는 큐에 좌표값만이 아닌, 현재의 방향과 꺾은 횟수를 같이 넣어줘야 한다. 그리고, 방향을 돌릴 때, .. 더보기
[백준][Python][1261][BFS] 알고스팟 문제 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net BFS 문제다. 전형적인 탐색 문제고, 벽의 갯수를 Queue에 넣지 않고, 따로 lt 라는 리스트에 저장하여 풀었다. 하도 예전에 한거라 블로그 닉값한 문제인지 내가 푼건지 모르겠다. import sys from collections import deque m,n = [int(i) for i in sys.stdin... 더보기
[백준][Python][1309][DP] 동물원 문제 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net DP 문제다. 예전에 풀어서 그런지 기억이 안났다. 이 문제는 n번째를 n-1, n-2 번째로 각각 나눠서 확인해야 한다. n-1 번째에 [0,X][X,0] 일때 n 번째에서는 각각 [X,0][0,X] 할 수 있는 경우의 수가 있다. 그리고 n-1 번째에 아무것도 놓지 않는 방법의 수, [0,0] 의 수가 있다. 이 때는 어디든 놓을수 있다. 따라서, dp[n] = dp[n-1]* 2 + dp[n-2]의 경우의 수가 있다. import sys n = int(sys.stdin.readline()) dp = [1,3] for.. 더보기
[백준][Python][14889][브루트포스] 스타트와 링크 문제 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 브루트 포스 문제다. 모든 팀 조합을 구하고, 그 조합들에서 차이가 가장 안나는 조합으로 최솟값을 구한다. 문제의 N이 작으므로 조합을 통해 다 구해보자. for c in combinations(orig,n//2) 은 0~n-1 까지의 모든 숫자를 반으로 나눈다. 그 다음 각각 나눠진 팀을 c, news 라 한다. 이는 Set 연산으로 구할 수 있다. 그 후 각각의 c에 대해 score연산을 통해 최솟값을 구.. 더보기
[백준][Python][11053][DP]가장 긴 증가하는 부분 수열 문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net DP 문제 중에 유명한 문제다. Longest Increasing Subsequence LIS라는 문제다. 이 문제는 DP로 풀면 O(n^2) 가 나오고, binary search 등을 이용하면 O(nlogn)까지 줄일 수 있다고 한다. 물론 난 안줄인다. ㅎㅎ dp 배열을 만들고, 다음과 .. 더보기
[백준][Python][10815][이분탐색] 숫자 카드 문제 : https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 www.acmicpc.net 이분탐색 문제다. list.count() 는 O(N) 이므로, count 를 사용할 경우 O(N^2) 가 되어 시간초과가 .. 더보기
[백준][Python][10816][이분탐색] 숫자 카드 2 문제 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00 www.acmicpc.net 이분 탐색 문제다. list.index()는 O(N) 이므로, count를 사용할 경우 O(N^2)가 되어 시간 초과가.. 더보기

티스토리툴바