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

• 

  [BOJ_2828] 사과 담기 게임 📌 문제 링크: https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 27.

• 

  [BOJ_1931] 회의실 배정 📌 문제 링크: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 처음 제출한 코드에서는 중첩 for문을 사용해서 시간 복잡도가 O(n^2)으로 '시간 초과'로 인해 문제를 통과하지 못했다. 그래서 중첩 for문이 아닌 단일 for문으로 코드를 수정해서 문제를 해결할 수 있었다. 질문 게시판의 반례들이 항상 맞는 것은 아니다. 틀린 반례가 올려져 있는 경우도 있으니 주의해서 적용하자. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 27.

• 

  [BOJ_2003] 수들의 합 2 📌 문제 링크: https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 문제를 읽자마자 투포인터를 이용한 풀이가 떠올랐고 구현하는 것도 어렵지 않았다. 하지만 문제에서 주어진 두 번째 예제의 답이 어떻게해서 3이 나오는지 이해가 안됐다. 계속 계산해봐도 2로 나오는데 고민을 하다가 두 개의 포인터가 같은 위치를 가리킬 수 있게 변경하니 문제의 예시의 답과 같이 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 27.

• 

  [BOJ_14916] 거스름돈 📌 문제 링크: https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 그리디 문제의 대표 유형인 거스름돈 문제이다. 입력값으로 주어진 N원을 2원과 5원의 동전으로 거슬러 줄 때, 거슬러 주는 돈의 개수를 최소한으로 만들어 반환해주면 되는 문제이다. 단순하게 생각해보면 5원의 개수를 최대한으로, 2원의 개수를 최소한으로 한다면 거슬러주는 동전의 개수를 최소한으로 만들 수 있다. (만약 입력값으로 10원이 주어졌다면 2원 동전 5개로 거슬러 줄 수도 있지만, 5원 동전 2개로 거슬러 주는 것이 더 적은 동전을 사용한다.).. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 21.

• 

  [BOJ_16953] A -> B 📌 문제 링크: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: BFS를 이용해서 풀이를 구현하는 것은 어렵지 않았고, 주어진 테스트 케이스도 모두 통과해서 제출했지만 메모리 초과가 발생했다. 그래서 문제를 다시 읽어보니 입력 값으로 주어지는 a와 b의 값이 최대 10억으로 정말 큰 수였다. 그래서 b의 값을 이용해 배열을 선언한다면 메모리 초과가 발생할 수밖에 없었다. 그래도 혹시 모르니까 기존의 풀이에서 배열을 1개만 사용하도록 변경했지만 여전히 메모리 초과가 발생했다. 따라서 b의 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 20.

• 

  [BOJ_21921] 블로그 📌 문제 링크: https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 이 문제는 약 5개월 전인 3월 5일에 풀어보려고 했으나 틀렸던 문제다. 그때 당시 풀이를 확인하지 않고 다음에 다시 풀어보겠다는 생각에 넘어갔었고 꽤 시간이 흘렀지만 이 문제를 풀기 위한 알고리즘을 공부하고 다시 풀어보니 어렵지 않게 해결할 수 있었다. 문제를 풀고 나서 다른 사람들의 풀이를 찾아보니 누적 합과 슬라이딩 윈.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 16.

• 

  [BOJ_11659] 구간 합 구하기 4 📌 문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 특정 구간의 합을 구하기 위해 누적 합을 이용한다. 예를 들자면 인덱스 2 ~ 4 사이의 구간 합을 구하기 위해 인덱스 4까지의 누적 합에서 인덱스 1까지의 누적 합을 뺀다면 해당 구간 사이의 구간 합을 구할 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 15.

• 

  [BOJ_4963] 섬의 개수 📌 문제 링크: https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 가장 최근에 풀었던 그래프 탐색문제들을 모두 bfs로 풀어서 dfs로 문제를 풀려고 하니 조건들을 어떤 순서로 배치해야할지 꽤 고민을 했었다. 알고 있는 풀이법이라고 해도 지속적으로 연습하지 않는다면 알면서도 풀지 못하는 경우가 생길 수 있음을 깨닫게 해준 문제였다. 또, 2차원 배열관련 문제를 풀때는 x, y 좌표를 잘 확인.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 15.

• 

  [BOJ_7562] 나이트의 이동 📌 문제 링크: https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 방향벡터를 이용해서 나이트가 이동해야 하는 좌표를 어떻게 나타내는지에 따라서 bfs 안의 코드를 좀 더 깔끔하게 표현할 수 있다. x와 y의 좌표가 이동할 수 있는 좌표를 서로 다른 리스트에 저장하기 보다 위의 코드처럼 하나의 좌표쌍으로 표현해보면 어떨까? 🚩 Idea: - "너 BFS를 이용해서 특정 좌표를 찾아갈 수 있니?"라고 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 14.

• 

  [BOJ_20291] 파일 정리 📌 문제 링크: https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 간단한 문자열 파싱과 정렬만 이용할 수 있다면 해결할 수 있는 문제였다. 커밋 로그가 끊기지 않게 하기 위해서 급하게 문제를 풀고 제출한 코드라 하루가 지난 시점에서 다시 코드를 보니 개선사항이 보인다. 컴프리헨션을 이용했더라면 적어도 두 줄정도는 코드를 줄일 수 있을 것 같다는 생각이 들었다. 🚩 Idea: - 입력값으로 주어지는 문자열.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 12.