코딩테스트

[백준(BOJ)] #9328- 열쇠 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 풀이 구현 문제로 BFS 알고리즘을 사용하여 문서의 최대 개수를 구할 수 있습니다. 2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인..

[백준(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) [파이썬으로 배우는..

[백준(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 게임이 생소하신 분들은 직접 플레..

[백준(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 - [..

[백준(BOJ)] #1463- 1로 만들기 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 이 문제는 동적 계획법을 사용하여 풀 수 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생..

[백준(BOJ)] #1717- 집합의 표현 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 풀이 이 문제는 다른 거 할 거 없이 Union-Find 알고리즘만 적용하면 되는 문제입니다. 2022.07.24 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 Union-Find의 개념 Union-Find 알고리즘을 알기 위해서는 Disjoint S..