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

• 

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

• 

  [BOJ_4158] CD 📌 문제 링크: https://www.acmicpc.net/problem/4158 4158번: CD 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 이 문제는 '입력은 여러 개의 테스트 케이스로 이루어져 있다.'라는 부분이 핵심이라고 생각한다. 문제에서 주어진 예시는 하나의 테스트 케이스가 주어지고 입력의 마지막에 '0 0'으로 끝나서 하나의 테스트 케이스만 판별하는 문제처럼 보이지만, 해당 예시가 테스트 케이스가 하나뿐인 것이다. 처음에는 해당 부분을 생각하지 못한 채 코.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 10.

• 

  [BOJ_10815] 숫자 카드 📌 문제 링크: https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 이진 탐색을 이용해 check에 있는 숫자가 card에 있으면 1을 출력하고, 없다면 0을 출력한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 7.

• 

  [BOJ_1620] 나는야 포켓몬 마스터 이다솜 📌 문제 링크: https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 1. 포켓몬의 이름이 input으로 들어올때 배열과 딕셔너리에 데이터를 추가한다. 2. 문제의 input 값을 판별 - 값이 숫자 -> input 값을 배열의 인덱스로 포켓몬의 이름을 출력 - 값이 문자 -> input 값을 딕셔너리의 key로 value인 포켓몬의 순서를 출력 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 7.

• 

  [BOJ_2012] 등수 매기기 📌 문제 링크: https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 실패했던 풀이는 문제의 예제 입력처럼 변칙적이지 않은 데이터가 들어올 때는 정확히 값을 찾아낸다. 하지만 이 문제에서 학생의 수인 N의 범위는 1과 500,000 사이의 자연수 범위를 갖고, 예상 등수는 500,000 이하의 자연수이다. 그래서 학생의 수가 1명이지만, 본인이 예상 등수를 500,000까지도.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 7.

• 

  [BOJ_1325] 효율적인 해킹 📌 문제 링크: https://www.acmicpc.net/problem/1325 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 6.

• 

  [BOJ_24444] 알고리즘 수업 - 너비 우선 탐색 1 📌 문제 링크: https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 큐 자료구조를 이용해서 너비 우선 탐색(BFS) 진행하고, 노드를 방문할때마다 방문 순서를 기록한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 6.

• 

  [BOJ_24479] 알고리즘 수업 - 깊이 우선 탐색 1 📌 문제 링크: https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net ✅ 내 풀이(Sucess) : 🧐 Review: 위의 코드를 Python3로 제출했을 때 '런타임 에러 (RecursionError)'가 발생하지만, PyPy3으로 제출하면 에러 없이 통과할 수 있다. 이게 재귀의 깊이 때문에 발생하는 문제 같아서 재귀 제한을 100,000보다 더 높게 잡아준다면 Python.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 6.