본문 바로가기

전체23

[ 백준 11053번 ] 가장 긴 증가하는 부분 수열(LIS) 파이썬 [백준 11053번 바로가기] 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 논리 주어진 문자열을 seq라고 할 때 seq[i]까지의 lis[i]를 기록해놓는다 i < j 인 seq[j]로 끝나는 lis 길이를 알기 위해 이전까지의 lis[i](i < j)를 참고한다 이때, seq[i] < seq[j]라면 lis[j] = max(lis[j], lis[i]+1)로 계속 갱신한다 코드 import sys def LIS(): # inpu.. 2021. 9. 1.
[ 백준 2573번 ] 빙산 파이썬 [백준 2573번 빙산 바로가기] 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 논리 빙산의 개수 파악: dfs탐색(원래 field를 변경하지 않기 위해 check_points라는 다른 배열 사용) 매 턴마다 다음 녹은 빙산을 계산하여 적용 매 턴마다 모든 field를 탐색하는 것은 불필요하므로 상한, 하한선을 갱신하여 그 안에서만 탐색하도록 함(xl, xr, yl, yr) 코드 import sys sys.setrecursionlimit(10000000) def iceburg(field, R, C): .. 2021. 8. 25.
[ 백준 2623번 ] 음악프로그램 파이썬 [백준 2623번 음악 프로그램 바로가기] 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1 큐를 이용한 위상정렬 논리 진입차수가 0인 노드를 큐에 넣는다 큐에서 꺼내면서 result에 순차적으로 기록하고, 해당 노드에 연결을 없앤다 연결이 해제된 노드들 중 새로 진입차수가 0이 된 노드를 큐에 넣는다 탐색 완료시 result의 개수가 총 노드의 개수보다 적으면 순환구조가 발생한 것이라 판단 2 dfs를 이용한 위상정렬 논리 진입차수가 0인 노드부터 dfs진행(방문한 노드 기록하여 중복된.. 2021. 8. 25.
정글일기 20210825 오늘의 일기 오늘은 정글 3주차 되는 날이다. 알고리즘 공부를 하고 있다. 현재까지 공부한 것은 다음과 같다. 1주차: sorting, recursion 2주차: 이진탐색, 분할정복, 스택, 큐, 우선순위 큐(힙큐) 3주차: 그래프 탐색(dfs, bfs, 위상정렬) 백준 문제를 통과하기는 어렵지만 배운 알고리즘을 구현한다는 것에 의미를 두고 있다. 세계적인 석학들과 선현들이 문제를 효율적으로 해결하기 위해 많은 것들을 남겼음을 다시 한번 깨닫는다. 우리는 이를 잘 활용해서 각자의 문제를 해결하는 데 사용하면 매우 좋을 듯하다. 그리고 그들이 이런 해결방법을 어떻게 고안했는지 당시의 문제 상황과 함께 사고과정을 따라가보면 좋겠다는 생각이 들었다(실천하지는 않았다). 2021. 8. 25.

티스토리툴바