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

• 

  [BOJ_1743] 음식물 피하기 📌 문제 링크: https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 아직 방문하지 않은 음식물을 만날 때마다 너비 우선 탐색을 이용하여 상하좌우를 탐색한다. 탐색을 계속해서 진행한다는 것은 음식물을 만난다는 의미이므로 그때마다 크기가 음식물의 크기를 업데이트시킨다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 2.

• 

  [BOJ_11123] 양 한마리... 양 두마리... 📌 문제 링크: https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: - 쉬운 그래프 탐색 문제였다. 해당 유형의 풀이법을 잊지 않게 자주 풀어봐야겠다. - 2차원 배열관련 문제를 풀 때 변수 이름을 map으로 설정하지 않게 주의하자! 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 1.

• 

  [BOJ_8394] 악수 📌 문제 링크: https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 점화식을 구하는 것은 어렵지 않았지만, 문제를 통과하기까지 코드를 몇 번이나 수정하였다. 처음 시간 초과로 문제를 틀린 이후에 코드를 수정해서 제출했지만, 계속해서 시간 초과가 발생하였다. 그래도 거의 다 풀었다는 생각에 답안을 확인하기보다 예전에 문제를 풀었을 때의 기억을 되짚어 보며 해결 방법을 생각해 보았다. 고민해 본 결과 이전에 '형변환은 생각보다 시간이 오래 걸린다'라는 글을 블로그에서 본 것 같다.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

• 

  [BOJ_14235] 크리스마스 선물 📌 문제 링크: https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: "너 heap에 대해서 알고있니?" 라고 물어보는 수준의 문제이다. 🚩 Idea: 아이들에게 선물을 나눠준 때는 들고 있는 선물 중에서 가장 가치가 높은 것을 주어야 한다. 그래서 최대 힙을 이용할 수 있다면 어렵지 않게 풀 수 있는 문제이다. 파이썬에서 제공되는 heapq 라이브러리는 최소 힙으로 구현되어 있으므로 최대 힙 처럼 이.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

• 

  [BOJ_17952] 과제는 끝나지 않아! 📌 문제 링크: https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 중복된 코드를 함수로 뺐다면 좀 더 깔끔한 코드가 됐을 것 같다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

• 

  [BOJ_13417] 카드 문자열 📌 문제 링크: https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 첫 번째 카드를 뽑을 때는 비교할 카드가 없으므로 덱에 초기값으로 넣어주었고, 두 번째 카드부터 덱에 첫 번째 원소와 비교하여 놓을 위치를 정해주었다. 사전순으로 가장 빠른 문자를 만들기 위해서는 문자열의 앞의 원소들이 최대한 A에 가까운 문자열로 채우는 것이 필요하다. 그래서 덱에 첫 번째 원소와 비교하여 카드를 왼쪽에 추가할지 .. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

• 

  [BOJ_9081] 단어 맞추기 📌 문제 링크: https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🚩 Idea: 문제를 처음 접했을 때 주어진 단어의 모든 순열을 구하고, 사전 순으로 정렬한 뒤에 조건에 따라서 답을 반환하도록 코드를 작성했지만, 시간 초과가 발생하였다. 그래서 시간을 조금 더 줄여보기 위해 빠른 입출력으로 코드를 수정했지만 똑같이 시간 초과가 발생하였다. 조금 더 고민해 봤지만 코드를 .. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

• 

  [BOJ_12847] 꿀 아르바이트 📌 문제 링크: https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 슬라이딩 윈도우 또는 구간 합(Prefix Sum) 알고리즘에 대해 알고 있다면 크게 어려운 문제는 아니라고 생각한다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 6. 15.

• 

  [BOJ_20920] 영단어 암기는 괴로워 📌 문제 링크: https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 습관처럼 코테를 준비해야 되는데, 회사에서 살아남기 위한 공부도 있다보니 생각보다 코테를 준비할 시간이 없던 것 같다. 사실 이 말도 핑계이고, 시간을 계획적으로 분배해서 사용하는 연습을 해야겠다. 성격이 워낙 즉흥적이고, 무계획이라서 쉽지 않겠지만, 의식적인 연습.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 6. 14.

• 

  [BOJ_22233] 가희와 키워드 📌 문제 링크: https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 약 8개월 전인 22년 9월 24일에 처음 제출했던 문제였다. 당시 2번의 제출에도 시간초과로 틀린 것을 보고 이 문제를 잠시 덮어두었는데, 오랜만에 다시 보게 되어 문제를 풀어봤다. 기존 로직에서 많은 부분이 수정된 것은 아니지만 시간복잡도를 최대한 줄이는 방향으로 코드를 수정했다. 하지만 여전히.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 5. 29.