본문 바로가기
728x90

Algorithm

[백준알고리즘] 2493번: 탑 -Python [백준알고리즘] 2493번: 탑 -Python https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. www.acmicpc.net 문제를 해결하기 위해서는 현재 탑의 바로 직전 탑의 높이만 알아야 하는 것이 아닌 자신이 도달할 수 있는 탑의 위치를 알기 위해서 어느 정도 이전 탑들의 정보가 필요하다. 하지만 탑의 개수도 많고, 높이의 범위도 넓기 때문에 이전에 나왔던 탑들을 모두 검사하는건 시간이 오래 걸릴 수밖에 없다. 그래서 필요.. 더보기
[백준알고리즘] 1946번: 신입 사원 -Python [백준알고리즘] 1946번: 신입 사원 -Python https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. www.acmicpc.net 문제 자체도 어려운 편이 아니었는데 계속 시간 초과가 나서 이상했었다. 한동안 sys.stdin.readline()대신 input()으로 다뤘더니 생긴 문제였다. 입력이 하나의 테스트케이스.. 더보기
[백준알고리즘] 9252번: LCS 2 -Python [백준알고리즘] 9252번: LCS 2 -Python https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 LCS 문제를 푼 적이 있다. 아래는 그때 풀었던 코드이다. https://suri78.tistory.com/11 오랜만에 LCS 문제를 풀려니까 머리가 아팠었다. 결국 방식은 동일하게 됐었다. 다만 문자열도 출력해주어야 하기 때문에 memoization 할 때 문자열을 직접 넣어주었다. .. 더보기
[백준알고리즘] 2096번: 내려가기 -Python [백준알고리즘] 2096번: 내려가기 -Python https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최대와 최소를 동시에 구해주어야 한다. 처음에는 large와 small을 구해주는 리스트를 처음에 주어진 크기와 같은 크기로 이중 리스트를 만들어 주었었다. 메모리 제한이 4MB이기 때문에 메모리 초과가 발생하게 되는데, 그래서 아래처럼 크기가 3인 리스트 두 개를 이용해서 최대 점수와 최소 점수를 구하도록 했다. n = int(input()) table = .. 더보기
[백준알고리즘] 1915번: 가장 큰 정사각형 -Python [백준알고리즘] 1915번: 가장 큰 정사각형 -Python https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이게 왜이리 오래 걸렸는지 모르겠다. 엄청 많이 틀렸다.. 틀린 이유는 시간초과였는데, 결국 다른 풀이들을 찾아봤다. 처음에 시간 초과가 걸리게 푼 방법은 재귀 방식을 사용했다. 현재 위치를 정사각형의 왼쪽 위 꼭짓점이라고 생각을 하고 만들어지는 최대 정사각형의 변을 구했다. 다음 세개의 길이의 최솟값+1을 해줌으로써 현재 구할 수 있는 정사각형의 가장 큰 길이를 구했다. 가로로 이어지는 길이 세로로 이어지.. 더보기
[백준알고리즘] 1965번: 상자넣기 -Python [백준알고리즘] 1965번: 상자넣기 -Python https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 www.acmicpc.net 앞에 자신보다 앞에 있었으면서 자신보다 작은 상자가 포함하고 있는 최대의 상자 개수를.. 더보기
[백준알고리즘] 1937번: 욕심쟁이 판다 -Python [백준알고리즘] 1937번: 욕심쟁이 판다 -Python https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 재귀를 사용한 동적 계획법으로 문제를 풀었다. 시작점이 주어지지 않았기 때문.. 더보기
[백준알고리즘] 1890번: 점프 -Python [백준알고리즘] 1890번: 점프 -Python https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 재귀를 사용한 동적계획법으로 문제를 풀었다. 동적 계획법으로 풀 수 있는 문제이다 보니 여러 .. 더보기
728x90

티스토리툴바