본문 바로가기

Programming [Python]

 (411)
#162 백준 파이썬 [2667] 단지번호붙이기 - BFS https://www.acmicpc.net/problem/2667 #Solution BFS로 2차원 배열 리스트에 근접한 같은 수를 알아내는 문제이다. 미로 문제를 약간 변형한 것이라 보면된다. 다음과 같은 알고리즘을따른다. 1) house[0][0]부터 house[N][N]까지, 하나씩 검사한다. 2-0) 0이 나올 경우 pass 2-1) 1이 나올 경우 상하좌우 인접한 모든 집을 구해준다. 3) BFS(너비 우선 탐색)를 이용해 인접한 노드를 구한다. 4) queue의 앞에서 부터 하나씩 pop하여 block과 visited 두 리스트에 추가해준다. 5) 상하좌우에 집이 있고, block과 queue에 없다면 해당 집을 queue에 추가해준다. 6) queue가 빌 때까지 계속해준다. 7) block..
#161 백준 파이썬 [1541] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 #Solution 문제의 알고리즘은 간단하다. -가 존재할 시, 다음 -가 오기 전까지 모든 수를 더해주면 된다. 없다면 그대로 수식을 출력. eval을 이용해 야매로 계산하려고 했는데 0으로 시작하는 수 때문에 자꾸 Error가 났다. 따라서 처음 입력을 받을 때부터 +와 -로 split하고, int로 숫자를 받음으로써 이 문제를 해결하였다. string = [sum([int(plus) for plus in minus.split('+')]) for minus in input().split('-')] print(string[0] - sum(string[1:]))
#160 백준 파이썬 [1931] 회의실배정 - 그리디 알고리즘 https://www.acmicpc.net/problem/1931 #Solution 두 가지 코드를 시도해보았다. 1. 시작시간을 lambda 함수로 오름차순 정렬한 뒤, 가장 뒤 회의 부터 가능한 maximum 회의 수를 출력하는 방법 2. 끝나는 시간 -> 시작 시간 차례로 오른차순 정렬한 뒤, 끝나는 시간이 가장 이른 시간 부터 차곡차곡 더해가는 방법 결국 빨리 끝나는 것 중 빨리 시작하는 순서(시작과 끝이 같은 경우의 수를 걸러줌)대로 집어 넣으면, 더 빠르게 답을 구해낼 수 있다. 1번은 자체적으로 만든 함수로 O(nlogn)이 걸린다(고 생각했지만 O(n^2)이다). 물론 답은 맞다(반례 있을 수도). 2번은 람다를 두 번 활용하는 함수로 O(nlogn)의 시간복잡도가 걸린다. 결론은 내장함수..
#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘 https://www.acmicpc.net/problem/12865 #Solution https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C 참조하였음. 유명한 냅색 문제, 냅색 알고리즘이다. 간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누..
#158 백준 파이썬 [9251] LCS https://www.acmicpc.net/problem/9251 #Solution https://twinw.tistory.com/126 참조. 두 문자열의 LCS(Longest Common Subsequence)를 찾는 알고리즘은 2차원 배열로 정답을 구할 수 있다. 아래와 같은 알고리즘으로 푼다. 1) 각 문자열 길이에 1을 더한 값을 X축, Y축으로 두고 0을 대입한다. 2) A[i]와 B[j]가 같은 arr[j][i]자리의 값은 위 혹은 왼쪽 중 큰 값을 대입해준다. - A의 시작부터 본 값 or B의 시작부터 대입한 값 중 제일 긴 것이 들어가는 것 3) A[i]와 B[j]가 같은 arr[j][i]자리의 값은 대각선 왼쪽 위의 값에 +1 해준 값을 대입해준다. - 위나 왼쪽이 아닌이유?: 같은 ..
#157 백준 파이썬 [2565] 전깃줄 - LIS https://www.acmicpc.net/problem/2565 #Solution LIS를 이용해 간단하게 풀 수 있다. 가장 적은 전깃줄을 없애는 방법은 을 구하는 것과 동일하다. [A, B] 리스트를 만들고 A 오름차순으로 정렬해준 뒤, 각 항에 대하여 B의 가장 긴 증가하는 수열을 구해준다. 예를 들어 위 식은 아래와 같이 먼저 정렬된 뒤, A B 1 8 2 2 3 9 4 1 6 4 7 6 9 7 10 10 각 항의 가장 긴 증가하는 수열을 구해주게 된다. A B 증가 수열 1 8 8 2 2 2 3 9 2 9 4 1 2 9 6 4 2 9 7 6 2 4 6 9 7 2 4 6 7 10 10 2 4 6 7 10 or 1 4 6 7 10 가장 긴 증가하는 수열(2, 4, 6, 7, 10)을 만들기 위해 ..
#156 백준 파이썬 [11054] 가장 긴 바이토닉 부분 수열 - LIS https://www.acmicpc.net/problem/11054 #Solution 가장 긴 수열 찾기 https://claude-u.tistory.com/184 참조. 순방향 한번, 역방향 한번으로 함수를 돌려준 뒤, 더해준다. 그 뒤 가장 긴 수열을 출력해주면 된다. O(n^2)이 나올텐데 아직(?)은 시간 초과가 안나기에 쉬운 코드로 돌려주었다. A = int(input()) A_list = list(map(int, input().split())) result = [[] for _ in range(A)] #순방향 돌려주기 for i in range(A): if i == 0: result[i].append(A_list[i]) else: for j in range(0, i): if result[j][..
#155 백준 파이썬 [2156] 포도주 시식 - 점화식 https://www.acmicpc.net/problem/2156 #Solution result[i]의 최댓값을 구하는 것은 세 가지 방법에 의해 결정된다. 1) OXOO: 연속 두 개 2) OXO: 하나 띄고 한 개 3) X: i번째를 마시지 않는 경우 wine = int(input()) wine_capa = [0] result = [0 for _ in range(wine + 1)] for _ in range(wine): wine_capa.append(int(input())) for i in range(1, wine + 1): if i == 1: result[1] = wine_capa[1] elif i == 2: result[2] = wine_capa[1] + wine_capa[2] else: resu..

티스토리툴바