Algorithm (7) 썸네일형 리스트형 위상 정렬이란? - python 파이썬 오늘은 위상 정렬(Topological Sort)에 대해서 공부했다. 위상 정렬이란? '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 순서를 결정할 때 사용하는 알고리즘이다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으며 모든 정점을 나열하면 된다. 하나의 방향 그래프에는 여러 개의 위상 정렬이 가능하다. 그럼 그래프를 통해서 이해해보자 위와 같은 그래프가 주어졌다고 가정해보자. 이 그래프가 의미하는 것은 다음과 같다. 1번의 선행 노드: 없음 2번의 선행 노드: 없음 3번의 선행 노드: 1번 4번의 선행 노드: 1번 5번의 선행 노드: 2번 6번의 선행 노드: 3번, 4번, 5번 1,2번은 선행 노드가 없다. 이런 정점을 진입 차수가 0인 정점이라 부른다. 진입 차수가 0인 정.. [LeetCode] Word Break II 풀이 - (python 파이썬) 사용 언어: Python 파이썬 문제: https://leetcode.com/problems/word-break-ii/ Word Break II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 Word Break(Medium)과 연관된 문제로, 좀 더 난이도가 높은 문제이다. Word Break의 해설은 여기서 볼 수 있다. 이 문제의 핵심은 Memoization이다. Memoization은 동일한 계산을 반복할 때, 이전의 값을 메모리에 저장하여 .. [LeetCode] Word Break 풀이 - (python 파이썬) 사용 언어: Python 파이썬 문제: https://leetcode.com/problems/word-break/ Word Break - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 Dynamic Programming으로 풀었다. Dynamic Programming이란? Dynamic Programming(동적 계획법)은 주어진 문제를 잘게 나누어서 하위 문제들을 푼 후, 각 답을 이용하여 주어진 문제를 푸는 방식이다. DP를 풀 때 생각해야하는 것.. [백준] 1463 1로 만들기 풀이 - Dynamic Programming (python 파이썬) 사용 언어: Python 파이썬 문제: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 Dynamic Programming을 사용해서 풀 수 있다. Dynamic Programming이란? Dynamic Programming(동적 계획법)은 주어진 문제를 잘게 나누어서 하위 문제들을 푼 후, 각 답을 이용하여 주어진 문제를 푸는 방식이다. DP를 풀 때 생각해야하는 것은 딱 하나다. 바로 '점화식'이다. 점화식만 세우면 문제 풀이는 끝났다. 주어진 문제를 읽어보자. 정수 X로 할 수 있는 연산은 총 3가지이다. 1. X를 3으로 나누기 2. X를 .. [백준] 11054 가장 긴 바이토닉 부분 수열 풀이 - (python 파이썬) 문제: https://www.acmicpc.net/problem/11054 사용 언어: Python 파이썬 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제는 가장 긴 증가하는 부분 수열 구하는 문제유형을 약간(?) 꼬아둔 문제다. 가장 긴 증가하는 부분 수열 구하기 유형을 처음 접한다면 이 글을 읽어보길 바란다. 2020/10/08 - [Algorithm] - 가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬 가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬 최근 들어, 알고리즘에 재미를 붙였.. 가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬 최근 들어, 알고리즘에 재미를 붙였다. 백준 문제를 풀면 문제 난이도마다 티어가 올라가는 재밌는 사이트(solved.ac)가 생겨서 뭔가 동기 부여되는 것 같다. 언어는 python을 사용하고 있다. (취준 할 때는 안 하고 꼭 뒷북치는 스타일... 그렇다고 실무에서 알고리즘이 안중 요하단 뜻은 아니다. 해야 할 때 덜 했을 뿐) DP Dynamic Programming을 집중적으로 좀 보고 있는데 백준에서 신기한 문제를 마주쳤다. 가장 긴 증가하는 부분 수열 구하기이다. Longest Increasing Subsequence라고 불리기도 한다고 한다. 오늘은 LIS에 대해 작성해보았다. 가장 긴 증가하는 부분 수열 임의의 수열이 주어질 때, 수열에서 몇 개의 수를 제거하여 부분 수열을 만들 수 있다. .. (C++) BFS와 DFS, 인접행렬과 인접리스트 (블로그 이전 준비를 하면서 예전 블로그에 있던 글을 옮겨 적는중이다.) 알고리즘을 처음 시작할 때, 이것 저것 찾아보다가 python이나 c++ STL을 쓰세요. 라는 글을 꽤 봤었습니다. python으로 할 줄 아는건 for문정도..? 여서 C++을 과감하게 선택했습니다. 문제를 좀 풀어보면서 가장 많이 나오는 BFS/DFS에 대해 작성해보았습니다. STL이란? 표준 C++ 라이브러리 (Standard Template Library) 프로그램에 필요한 자료구조, 알고리즘을 Template으로 제공 일단 익숙해져보세요! 인접 행렬 인접 행렬이란 그래프의 연결 관계를 이차원배열로 표현합니다. 보통 adj[][]형태로 많이 작성합니다. adj[i][j]: i에서 j로 가는 간선이 있다면 1, 없다면 0 위.. 이전 1 다음
