알고리즘266

• 

  [BOJ_2531] 회전 초밥 📌 문제 링크: https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 1. 일단 문제에서 N의 수가 최대 30,000으로 꽤 크다. 이때는 입력을 받는 시간을 최대한 줄이기 위해 빠른 입출력을 사용하자. 2. 회전하는 벨트를 보고 데큐의 rotate() 함수를 떠올랐다. 3. 문제에서 구하고자 하는 값은 '최대한 많은 종류의 초밥을 먹고, 그 수를 반환하는 것'이다.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 7.

• 

  [BOJ_1141] 접두사 📌 문제 링크: https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 문제를 풀고 나서 다른 풀이들을 확인해 보니 슬라이싱을 이용한 풀이가 많았다. 해당 내용을 정리해 둔 문서를 다시 읽어봐야겠다. 🚩 Idea: - 중복된 문자열을 확인하는 과정을 줄이기 위해 집합(set)에 문자들을 담아 중복된 문자열을 제거한다. - 위의 처리를 거친 문자.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 6.

• 

  [BOJ_15903] 카드 합체 놀이 📌 문제 링크: https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: heap이라는 리스트를 따로 생성하지 않고, 기존 cards에 heapify()로 원소를 재정렬을 해주었다면, 2줄의 코드는 더 줄일 수 있었을 것 같다. 🚩 Idea: '너 힙에 대해서 알고있니?'라고 물어보는 문제이다. 힙이나 우선순위큐에 대해서 알고 있다면 쉽게 풀 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 6.

• 

  [BOJ_2841] 외계인의 기타 연주 📌 문제 링크: https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 2차원 배열(스택)에 초기 값으로 0을 미리 넣어주었다면, 스택의 원소가 들어있는지 확인하는 코드가 필요하지 않았을 것 같다. 🚩 Idea: 멜로디를 연주할 때 음에 해당하는 하나의 줄을 튕겨야 소리가 나기 때문에 여러 줄의 서로 다른 프렛을 누르고 있더라도 멜로디에는 영향이 없다. 결국 입.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 3.

• 

  [BOJ_7576] 토마토 📌 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 같은 유형의 실버 문제를 몇 문제 풀고 나서 도전해 보니 골드 난이도의 문제도 어렵지 않게 풀 수 있었다. 유형별로 문제를 풀면서 난이도를 높여가는 방법으로 연습을 해봐야겠다. 위 문제에서는 기존 배열(grid)의 값을 수정하면서 탐색을 진행하기 때문에 굳이 visited 배열을 이용해서 방문 여부를 확인할 필요가 .. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 2.

• 

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