백준
-
백준 파이썬 15486 : 퇴사 2 풀이기타/알고리즘 2020. 12. 26. 23:32
15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net n 1일 2일 3일 4일 5일 6일 7일 T[i] 3 5 1 1 2 4 2 P[i] 10 20 10 20 15 40 200 M 0 0 0 10 30 30 45 dp[i] 0 0 0 10 30 0 45 각각의 날들을 '그날 상담을 시작하는 경우'와 '그날 상담을 시작하지 않는 경우'로 나눌 수 있다 만약 1일이라면 T = 3인 일을 시작할 수도 있고, 시작하지 않을 수도 있는 것이다 상담을 시작한다면, 상담이 끝난 다음 날의 수익이 P..
-
백준 파이썬 11722번 : 가장 긴 감소하는 부분 수열 풀이기타/알고리즘 2020. 12. 25. 10:54
11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net nums 안의 수에 대해 가장 긴 감소하는 부분 수열의 길이를 구하는 문제다. 앞의 수가 다음 수보다 크다면 문제의 조건을 만족한다 각 인덱스에 대해 자신보다 인덱스가 작은 값을 검색하여 조건을 만족하는 수의 개수를 찾는다 앞의 인덱스에서 조건을 만족하는 수의 개수를 찾으면, 다음 계산시에 이를 이용해준다. 예제로 주어진 nums = [10, 30, 10, 20, 20, 10]로 생각해보면..
-
백준 파이썬 18352 : 특정 거리의 도시 찾기 풀이기타/알고리즘 2020. 12. 22. 10:40
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net x에서 출발하여 최단 거리가 k인 도시를 모두 출력해야 한다 1. 그래프를 입력받는다. 일반적으로 탐색 문제에서는 '1 2'라는 입력이 들어오면 graph[1]에 2를 넣고, graph[2]에는 1을 넣어서 양방향으로 연결된 관계를 표현해준다 그러나 이 문제에서는 최단 거리를 구하기 때문에 양방향 관계가 필요가 없다. 왔던 ..
-
백준 파이썬 2667번 : 단지번호 붙이기 풀이기타/알고리즘 2020. 12. 19. 15:32
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 그래프 탐색 문제로, 동서남북으로 인접한 곳에 집이 있으면(= 1이라면) 집이 연결되어 있다고 하고, 연결된 집의 모임을 단지라고 한다. 여기서 단지의 개수, 각 단지내 집의 수를 출력해야 한다. 1. 어느 한 점에 대해서 인접한 곳에 1이 있는지를 탐색하고 2. 1이 있다면 그 점에서 다시 인접한 곳을 탐색하길 반복하고 3. 탐색을 할 때마다 카운트를 세다가 4. 탐색이 끝나면 카운트를 정답에 저..
-
백준 파이썬 2583번 : 영역 구하기 풀이기타/알고리즘 2020. 12. 18. 23:39
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 영역이 주어지고, 갈 수 없는 영역이 주어졌을 때, 갈 수 있는 영역의 개수를 구하는 문제다. 0,0에서 시작해서 BFS(너비 우선 탐색)을 동서남북 네 방향으로 실행하고, 한 칸 이동할 때마다 카운트를 더해주다가, 더 이상 갈 수 있는 영역이 없어졌을 때 카운트를 답에 저장해주면 된다. 1. 사각형의 세로 길이는 m, 가로 길이는 n, 갈 수 없는 영역의 개수는 k개다 2. ..
-
백준 파이썬 11501 : 주식 풀이 (시간초과 해결)기타/알고리즘 2020. 12. 16. 23:08
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 미래의 가격을 알고 있고, 매일 한 주를 사거나 팔 수 있고, 아무것도 하지 않을 수 있다. 이때의 최대 이익을 구해야 한다. 주식은 싸게 사서 그보다 비싸게 팔면 되는 '매우 간단한' 게임이므로 1. 현재 가격이 미래 가격보다 싸면 사고 2. 미래 가격보다 비싸면 아무것도 하지 않고 3. 지금 가격이 최대 가격이면 팔면 된다 따라서 1. 현재 이후의 가격의 최대값을 구하고 2. 현재..
-
백준 파이썬 17952번 : 과제는 끝나지 않아! 풀이기타/알고리즘 2020. 12. 15. 23:35
https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 과제를 최근에 나온 순서대로 하고있다. 그러므로 스택을 이용한 문제임을 알 수 있다 스택을 이용하면 조건 1, 2, 3을 자동으로 만족하기 때문에 간단히 풀 수 있다 굳이 데크를 이용하지 않아도 풀 수 있다 1. 과제의 정보를 입력받고 과제의 점수와 시간을 따로따로 저장해준다 2. 시간이 지남에 따라 가장 마지막에 받은 과제의 시간을 -1해준다 3. 가장 마지막 과제의 시간이 0이 되면 시..
-
백준 파이썬 10828번 : 스택 시간초과 해결기타/알고리즘 2020. 12. 3. 22:35
10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택을 몰라도 충분히 풀 수 있다. solved.ac에서 실버4 판정을 받고 있는데, 절대 그럴만한 문제는 아니다. 다만 정답률이 상당히 낮은데, 시간이 빡빡해서 그렇다. 별다른 궁리가 필요하지는 않고, input대신에 값을 입력받는 데 더 빠른 readline을 쓰면 된다. 백준 문제에서 시간초과가 날 때는 대부분 readline을 쓰거나 PyPy로 제출하면 해결된다. 참고로 import sys input = sys.stdin.readline ..