알고리즘 문제 풀이: 파이썬/BOJ211

• 

  [BOJ_9625] BABBA 📌 문제 링크: https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 버튼을 누르지 않았을 때(dp 배열의 0번째 원소)는 A의 개수는 1이고, 버튼을 한 번 눌렀을 때(dp 배열의 1번째 원소)는 A의 개수는 0이 되고, B의 개수는 1이 된다. 2번째 원소부터 그 이전 두 개의 항의 원소의 값을 더해 A와 B의 개수를 구할 수 있다. 처음에는 'A'와 'B'를 이용해 문자열을 직접 더하고 dp 배열의.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 7.

• 

  [BOJ_2193] 이친수 📌 문제 링크: https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 위와 같이 경우의 수를 나열하면서 규칙성을 찾는다. 🚩 Idea: 1. dp문제로 경우의 수를 나열해보면서 규칙성을 찾는다. 2. 규칙성을 이용해 점화식을 세운다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 6.

• 

  [BOJ_9095] 1, 2, 3 더하기 📌 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 어제 풀었던 dp 문제가 재미있어서 오늘도 dp 문제를 풀어봤다. 규칙성은 5번째 원소까지 경우의 수를 구하고 이전 항들과의 비교를 통해 찾을 수 있었다. 🚩 Idea: 1. dp문제로 경우의 수를 나열해보면서 규칙성을 찾는다. 2. 규칙성을 이용해 점화식을 세운다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 6.

• 

  [BOJ_2579] 계단 오르기 📌 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 처음 문제를 접근했을 때는 모든 경우의 수를 나열해서 규칙성을 찾았다. 여섯 개의 계단을 오르는 경우까지 확인을 해보니 규칙성을 발견했고 점화식을 세울 수 있었다. 문제의 결괏값으로 계단 오르기 게임에서 얻을 수 있는 최고 점수를 반환해야 되는데, 해당 부분은 모든 경우의 수의 점수를 계산하고, 해당 데이터에 max값을 반환해주는 식으로 문제를.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 5.

• 

  [BOJ_2178] 미로 탐색 📌 문제 링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: - Reference에 첨부한 문제를 이전에 푼 경험으로 같은 방법을 이용해서 이 문제를 해결했다. 두 문제의 풀이 코드도 입력으로 주어지는 배열과 이동방향을 결정하는 방향벡터만 다를뿐 완전히 똑같은 코드였다. 🚩 Idea: - 문제를 읽자마자 BFS로 풀어야겠다는 생각이 들었다. 그런 생각이 들지 않았더라도 문제의 알고리즘 분류에 힌트가 주어지기 때문에 어떤 알.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 28.

• 

  [BOJ_1793] 타일링 📌 문제 링크: https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: n의 값에 따라 타일의 경우의 수를 체크하는데 n=5일 때 경우의 수를 잘못 구해서 점화식을 잘못 작성하게 되었고, 그래서 몇 번 틀렸던 문제이다. DP 문제를 풀 때는 보다 세심하게 경우의 수를 확인하도록 연습해야겠다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 17.

• 

  [BOJ_1697] 숨바꼭질 📌 문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: - 수빈이가 이동할 수 있는 경우 세 가지(x-1, x+1, 2*x) 중에서 순서를 적절하게 하지 못하면 코드를 다 작성했지만 틀릴 수도 있는 문제이다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 15.

• 

  [BOJ_1753] 최단경로 📌 문제 링크: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 단일 출발 최단경로 문제(그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드와의 최단경로를 찾는 문제)는 '다익스트라' 알고리즘을 이용한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 15.

• 

  [BOJ_2075] N번째 큰 수 📌 문제 링크: https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 문제를 읽자마자 힙을 이용하면 어렵지 않게 풀 수 있을 것이라고 생각했고 쉽게 코드를 작성할 수 있었지만, 막상 코드를 제출해보니 메모리 초과가 발생했다. 문제를 풀 때 시간 복잡도를 고려하여 코드를 작성하지만, 보통 메모리 제한은 크게 신경 쓰지 않았기 때문에 기존 코드를 어떻게 수정을 해야 할지 막막했다.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 14.

• 

  [BOJ_11286] 절댓값 힙 📌 문제 링크: https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 힙에 원소를 넣어줄 때 튜플을 이용해서 튜플의 첫 번째 값은 정렬의 기준을 제공하고, 두 번째 값은 실제 데이터 값이다. - 힙에서 원소를 꺼낼 때는 튜플의 두 번째 값을 출력해서 실제 데이터 값을 출력한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 14.