분류 전체보기326

• 

  [BOJ_10546] 배부른 마라토너 📌 문제 링크: https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 문제를 읽자마자 프로그래머스에서 풀어본 문제라는 것을 알았다. 심지어 예제의 이름도 똑같았다ㅋㅋㅋ 그래서 딕셔너리를 이용하면 이 문제를 쉽게 해결할 수 있을 것 같다는 생각을 했고, 별다른 고민없이 5분도 안걸려서 코드를 작성해서 제출했더니 통과할 수 있었다. 매일 알고리즘 문제를 푼 것은 아니지만 작년부터 문제 풀이에 꾸.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 28.

• 

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

• 

  [Python] 정렬 함수에 대해서 # 1 평소처럼 알고리즘 문제를 풀고 나서 내 풀이와 다른 사람의 풀이를 비교하는 중에 내 풀이보다 짧고 단순해 보이는 풀이를 발견해 내 풀이 맞게 코드를 수정했지만 결괏값이 일치하지 않았다. 그래서 전체 코드를 하나씩 비교해보니 내 풀이와 정렬하는 부분에서 다르다는 것을 확인했고, 이 차이는 아래와 같다. 나는 위의 1번 방법으로 정렬했지만, 다른 풀이는 2번 방법으로 정렬을 해주었다. 이렇게 서로 다른 방법으로 정렬을 했을 때의 결과는 아래의 이미지와 같은데, 보다시피 정렬의 결과가 다르게 나온다. 이 결과를 보고 파이썬의 문법을 다시 떠올려보니 내가 적용했던 첫 번째 방법은 인덱스 0번 원소를 기준으로 오름차순 정렬을 하고, 동일한 원소의 값이 존재하면 인덱스 1번 원소를 기준으로 또 정렬을 해주는.. 프로그래밍 공부/Python 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.