본문 바로가기

전체 글

[백준][Python][2293][DP] 동전 1 문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제다. 어떠한 동전 c 를 이용해서 1-x를 만드는 모든 방법을 value에 더하는 방식으로 구할 수 있다. 첫번째 동전까지 이용해서 x를 만드는 경우의 수 + 두번째 '' + 세번째 '' + ... ... 를 하면 모든 동전을 사용하여 x 를 만드는 모든 경우의 수를 구할 수 있다. 이때, 동전값을 c라 할 때, x-c >=0, 즉 목표값보다 동전값이 작을 때만 이전의 경우의 수 .. 더보기
[백준][Python][14891][시뮬레이션] 톱니바퀴 문제 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 방향 헷갈리지 말자. [1,2,3,4,5,6,7,8] 일때 시계방향 -> [8,1,2,3,4,5,6,7] 반시계방향 -> [.. 더보기
Go 1.14 출시 https://blog.golang.org/go1.14 Go 1.14 is released - The Go Blog Alex Rakoczy 25 February 2020 Today the Go team is very happy to announce the release of Go 1.14. You can get it from the download page. Some of the highlights include: For the complete list of changes and more information about the improvements above, see blog.golang.org 이제 Go module 이 production ready로 바뀜 이제 인터페이스에서 메서드 시그니쳐 중복이 .. 더보기
[백준][Python][14501][15486][DP]퇴사, 퇴사2 문제 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제:https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net DP 문제다. 둘 다 푸는 방법은 같고 개수만 15, 1500000개로 다르다. 따라서, 퇴사 1 은 O(N^2)로 풀어도 되지만 퇴사 2는 O(N)으로 풀어야 한다. i 번째 날,.. 더보기
[백준][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.. 더보기
next_permutation Python 구현 def next_permutation(arr): i,j = len(arr)-1, len(arr)-1 while i>0 and arr[i-1]>=arr[i]: i-=1 if i==0: return False while arr[i-1]>=arr[j]: j-=1 arr[i-1], arr[j] = arr[j],arr[i-1] k = len(arr)-1 while i= arr[i] 가 되는 i 중 제일 큰 값을 찾는다. i 가 0 이 되면 [5,4,3,2,1] 같이 역으로 정렬되어있는 값이라 순열의 끝이라 False 를 반환한다. arr[i-1] >= arr[j] 가 되는 j 중 가장 큰 값을 찾는다. 이 때, 1 번에서 arr[i-1] >= arr[i] 를 찾았기 때문에 무조건 i 더보기
[백준][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... 더보기

티스토리툴바