백준199

• 

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

• 

  [BOJ_1927] 최소 힙 📌 문제 링크: https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: heapq 라이브러리가 최소힙으로 구현되어 있기 때문에 해당 라이브러리를 이용하면 쉽게 문제를 해결할 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 14.

• 

  [BOJ_1072] 게임 📌 문제 링크: https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: - 승률 Z가 절대 변하지 않는 경우는 Z가 100%와 99%인 경우이다. 처음 문제를 접근했을 때는 100%만 해당하는 줄 알았는데 '질문 답변 게시판'을 보고 99%도 포함한다는 것을 배웠다. - 승률을 계산할 때 주의해야 하는 문제이다. 승률 계산을 위해 단순히 y을 x로 나누고, 100을 곱한 뒤, 소수점 이하 자리를.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 11.

• 

  [BOJ_20551] Sort 마스터 배지훈의 후계자 📌 문제 링크: https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 값의 존재 유무를 O(1)의 시간 복잡도로 체크하기 위해서는 딕셔너리를 사용하자! 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 11.