본문 바로가기
반응형

전체 글163

[Python] Baekjoon - 8980. 택배 백준 8980번 택배는 직선 위의 마을을 순서대로 운행하는 트럭이 상자를 총 몇 개 배달하는지 맞히는 문제다. 현재 마을에서 상자를 최대한 효율적으로 담아가야 하기 때문에 그리디 알고리즘을 사용하여 해결할 수 있다. 난이도는 골드 3이다. 백준 8980번 택배 문제 정보 알고리즘 분류 - 그리디 알고리즘 및 정렬 난이도 - 골드 3 택배 문제 요약 왼쪽 첫 번째 마을부터 맨 오른쪽 마지막 마을까지 순서대로 운행하는 트럭이 있다. 각 마을에서 보낼 상자의 개수(출발 마을, 도착 마을, 개수)와 트럭의 용량이 주어질 때, 마지막 마을까지 도착한 후 배달한 총 상자의 개수를 구하는 문제다. 문제 풀이 과정 현재 마을에서 상자를 최대한 효율적으로 담아가는 그리디 알고리즘을 사용한다. 더 가까운 도착지 우선으로 .. 2021. 7. 14.
[Python] Baekjoon - 1931. 회의실 배정 백준 1931번 회의실 배정 문제를 파이썬을 이용해 풀어보았다. 그리디 알고리즘을 이용한 가장 기본적인 문제이며 정렬도 이용해야 한다. 문제는 N개의 회의가 1개의 회의실을 사용하려고 할 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다. 1931번 회의실 배정 문제 정보 알고리즘 분류 - 그리디 알고리즘 및 정렬 난이도 - 실버 2 회의실 배정 문제 요약 1개의 회의실을 예약한 N개의 회의 스케줄이 주어졌을 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다. 문제 풀이 과정 가장 기본적인 그리디 알고리즘 문제이다. 전체 회의 스케줄을 끝나는 시간이 이른 회의 순으로, 끝나는 시간이 같다면 시작 시간이 이른 순으로 정렬한다. 끝나는 시간이 이른 회의 먼저 회의 가능 여부를 판단하고 회의가 가능.. 2021. 7. 13.
[Python] Baekjoon - 9205. 맥주 마시면서 걸어가기 백준 9205번 맥주 마시면서 걸어가기는 그래프 탐색 알고리즘 중 BFS를 이용하여 해결할 수 있는 문제이다. 2차원 좌표평면 상에서 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는 지를 구하는 문제다. 난이도는 실버 1이다. 맥주 마시면서 걸어가기 문제 정보 알고리즘 분류 - 그래프 탐색 - BFS 난이도 - 실버 1 맥주 마시면서 걸어가기 문제 요약 2차원 좌표평면 상에 상근이의 집, 축제장소, 그리고 N개의 편의점의 좌표가 주어진다. 상근이는 맥주 20병을 담을 수 있는 상자를 들고 출발하는데, 맥주 한 병을 마시면 50m를 갈 수 있다. 가다가 맥주가 모자라면 편의점에서 맥주를 구매하여 빈병을 맥주로 바꿀 수 있다. 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는지의 여부를 구하여라. 문제 풀.. 2021. 7. 13.
[Python] Baekjoon - 11053. 가장 긴 증가하는 부분 수열 백준 11053번 가장 긴 증가하는 부분 수열은 다이내믹 프로그래밍(DP)을 이용해서 풀 수 있는 문제이다. 난이도는 실버 2로, DP를 이용해 효율적으로 푸는 방법을 떠올리기 어려운 문제다. 길이가 N인 수열에 등장하는 증가하는 부분 수열 중 가장 길이가 긴 것의 길이 구한다. 가장 긴 증가 부분 수열 문제 정보 알고리즘 분류 - 다이나믹 프로그래밍 난이도 - 실버 2 요약 길이가 N인 수열에 등장하는 증가하는 부분 수열 중 가장 길이가 긴 것의 길이 구하기 문제 풀이 과정 각 위치의 숫자를 포함하는 증가 부분 수열의 최대 길이를 저장하는 배열을 사용한다. 현재 숫자보다 작으면서, 가장 긴 증가 부분 수열을 갖는 부분 수열의 뒤에 추가한다. 풀이 cnt[i]: i번째 숫자를 포함하는 증가 부분 수열의 .. 2021. 7. 13.
반응형

티스토리툴바