BOJ198

• 

  [BOJ_1051] 숫자 정사각형 📌 문제 링크: https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 두 번째 for문에서 len(rectangle[i])을 m으로 변경하는 것이 좀 더 깔끔한 코드가 될 것 같다. 🚩 Idea: - n과 m의 길이가 50이하의 수로 완전 탐색을 이용해 모든 경우의 수를 확인해도 시간 초과가 발생하지 않을 것 같다. - 정사각형의 최소 크기(넓이)는 1이므로 area에 해당 값을 넣고 시작한다. - .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 9.

• 

  [BOJ_4796] 캠핑 📌 문제 링크: https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - L, P, V의 값의 나눗셈을 통해 휴가 기간인 V에서 며칠 동안 캠핑장을 이용할 수 있는지 확인한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 8.

• 

  [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.