분류 전체보기

[백준(BOJ)] #1208- 부분수열의 합 2 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 2022.08.16 - [PS/백준] - [백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3) [백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3) 문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤..

[백준(BOJ)] #1182- 부분수열의 합 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 n개의 정수에서 가능한 모든 부분 수열을 구한 뒤(*Brute Force) 부분 수열의 합이 s가 되는 경우를 찾아 더해주면 됩니다. Brute Force 알고리즘: Brute(무식한) + Force(힘) 무식하게 모든 경우의 수를 탐색하는 방법으로 완전 탐색을 의미함. n개의 정수 -7, -3, -2, 5, 8 s = 0 크기가 1인 부분 수열..

[백준(BOJ)] #14728- 벼락치기 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 문제 풀이 2022.08.12 - [PS/백준] - [백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3) [백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3) 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 ..

[백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 이 문제는 대표적인 냅색 문제(Knapsack Problem)입니다. 냅색 문제는 배낭 문제라고도 불리며 동적 계획법을 사용해 푸는 문제 중 유명한 유형의 문제입니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는..

[파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

이분 탐색(Binary Search)이란? 이분 탐색(Binary Search)이란 탐색 범위를 절반으로 나눠가며 데이터를 탐색하는 방법입니다. 우리가 흔히 알고 있는 순차 탐색(Linear Search)은 데이터를 앞에서부터 하나씩 탐색하여 시간 복잡도가 O(N)(N은 데이터의 개수)으로 그렇게 효율적인 탐색 방법은 아닙니다. 하지만 이분 탐색은 데이터의 범위를 절반씩 계속 나눠 탐색하기 때문에 시간 복잡도가 O(logN)으로 순차 탐색보다는 훨씬 효율적인 탐색 알고리즘이라고 볼 수 있습니다. 하지만 데이터가 속해 있는 범위를 알아야 하기 때문에 정렬되어 있는 데이터에서만 이분 탐색을 사용할 수 있습니다. 그러면 이분 탐색이 어떻게 사용되는지 순차 탐색과 어떻게 다른지 과정을 보며 확인해보겠습니다. 이..

[백준(BOJ)] #1005- ACM Craft (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 이 문제는 위상 정렬과 동적 계획법 알고리즘을 사용하여 해결할 수 있습니다. 2022.08.08 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort) [파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)이란? 위상 정렬(Topology Sort)은 순서가 정해져 있는 작업을 수행해..

[백준(BOJ)] #12100- 2048 (Easy) (파이썬, Python3)

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 문제 설명 그대로 2048 게임을 구현하는 문제입니다. https://play2048.co/ 2048 Join the numbers and get to the 2048 tile! Careful: this game is extremely addictive! play2048.co 문제에도 나와있지만 위 링크를 통해 2048 게임이 생소하신 분들은 직접 플레..

[파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란? 위상 정렬(Topology Sort)은 순서가 정해져 있는 작업을 수행해야 할 때 사용하는 사용할 수 있는 알고리즘입니다. 대학교 수강 과목 리스트를 예로 나타내 볼게요! 저는 컴퓨터공학과 학생이기 때문에 저의 수강 리스트를 위상 정렬로 예를 들면 위와 같이 나타낼 수 있습니다. 자료구조와 컴퓨터구조 수업을 수강하기 위해서는 프로그래밍 실습수업을 선수강해야 하고 알고리즘 수업을 수강하기 위해서는 자료구조 수업을 선수강해야 합니다. 이 과목들을 모두 수강한 후에야 비로소 최종적으로 운영체제 수업을 수강할 수 있습니다. 기억나는 대로 그냥 예시로 든 것이니 실제 선수 과목과 다를지라도 그냥 넘어가 주시면 감사하겠습니다.ㅋㅋㅋㅋ 위상 정렬의 특징 1) 위상 정렬에서는..

[백준(BOJ)] #1197- 최소 스패닝 트리 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 이 문제는 최소 신장 트리의 가중치를 구하는 문제로 크루스칼 알고리즘을 적용하여 풀었습니다. 2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 크루스칼(Kruskal) 알고리즘이란? 2022.07.28 - [..

[파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘

플로이드 워셜(Floyd Warshall) 알고리즘이란? 플로이드 워셜(Floyd Warshall) 알고리즘은 최단 경로 알고리즘이지만 그래프에서 특정한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 다익스트라 알고리즘과 달리 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 동적 계획법을 활용한 알고리즘입니다. 2022.07.31 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서..