728x90 greedy 썸네일형 리스트형 [백준알고리즘] 4796번: 캠핑 -C++ [백준알고리즘] 4796번: 캠핑 -C++ 4796번: 캠핑 (acmicpc.net) 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 그리디의 다른 쉬운 문제를 풀었다. 이 문제도 예전에 풀었던 ATM 문제와 같이 SJF 방식으로 풀면 된다. 이게 그리디지 ㅋㅋ 하면서 쉬워서 기분 좋았다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 풀이 어떤 경우에서든 연속된 \(P\) 일 중에 최대 \(L\) 일만 사용할 수 있어야 한다. 즉, \(V+0 \sim V+P+0\) 까지도 \(L\) 일만 사.. 더보기 [백준알고리즘] 16953번: A → B -C++ [백준알고리즘] 16953번: A → B -C++ 16953번: A → B (acmicpc.net) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 그리디 느낌이 나는 쉬운 문제를 찾다가 발견했다. 어려운 문제는 아니었으나, 문제 풀이를 생각했을 때 직관적으로 그리디 하게 풀 수 있겠다고 느꼈다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 풀이 정수 A에서 B로 바꿔야 한다. 아래의 두 가지 경우를 하나씩 사용해 최종적으로 B로 바꿔야 한다. 2를 곱한다. 가장 오른쪽 수에 1을 추가한다. (자리수 이동) 즉, 예제와 같이 A와 B가 각각 2와 162라면, 아래와 같이 변경할 수 있다. 최종적으로 4개의 연산이 요구된다... 더보기 [백준알고리즘] 1439번: 뒤집기 -C++ [백준알고리즘] 1439번: 뒤집기 -C++ 1439번: 뒤집기 (acmicpc.net) 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 알고리즘을 풀어보고 싶어서, 안 푼 그리디 문제 중에 그나마 쉬운거부터 골랐다. 쉽게 풀긴 했는데, 이게 그리디인지는 느낌이 안 오는 문제였다. 다른 문제를 더 풀어봐야 할 것 같다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제풀이 0과 1로 이루어진 문자열이 주어진다. 이때 0은 1로, 1은 0으로 뒤집을 수 있다. 모두 같은 숫자로 이루어진 문자열을 .. 더보기 [백준알고리즘] 13305번: 주유소 -C++ [백준알고리즘] 13305번: 주유소 -C++ 13305번: 주유소 (acmicpc.net) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 처음에 메모이제이션을 사용한 방법을 사용해 각 도시에서 끝 도시까지의 최단 거리를 계산하는 방법을 사용했다. 이러한 방법은 시간 초과가 났다. 다시 생각해보니까 도시의 개수를 고려하니 시간이 훨씬 초과될만했다. 그래서 새로운 방법을 생각했고, 그리디한 방법으로 접근하면 된다는 것을 알게 됐다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제를 풀 때.. 더보기 [백준알고리즘] 1138번: 한 줄로 서기 -Python [백준알고리즘] 1138번: 한 줄로 서기 -Python https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 키가 1인 사람부터 차례대로 세워주었다. 주어진 입력에 따라서 자신보다 키가 큰 인원의 수만큼 왼쪽에 빈자리를 놔두고 자리를 잡으면 된다. 예를 들어 주어진 2 1 1 0 에 대해서는 1보다 키가 큰 사람이 왼쪽에 두 명이 있어야 하기 때문에 왼쪽에 빈자리를 두 개 두고 위치하면 된다. 0 0 .. 더보기 [백준알고리즘] 1080번: 행렬 -Python [백준알고리즘] 1080번: 행렬 -Python https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 코드가 조금 지저분해보이기는 하지만 그리디 알고리즘을 사용했다. 반복문을 사용하지 않고 재귀를 통해서 문제를 해결했다. DFS방식의 재귀 깊이 때문에 런타임에러가 발생했었고, 모든 경우에 대해서 3x3을 변환시키고, 다시 원상태로도 진행을 하는 2가지 방법을 적용했었기 때문에 시간 초과가 발생했었다. 시간 초과가 발생한 경우에 대해서 더 설명을 하자면, 현재 위치.. 더보기 [백준알고리즘] 1946번: 신입 사원 -Python [백준알고리즘] 1946번: 신입 사원 -Python https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. www.acmicpc.net 문제 자체도 어려운 편이 아니었는데 계속 시간 초과가 나서 이상했었다. 한동안 sys.stdin.readline()대신 input()으로 다뤘더니 생긴 문제였다. 입력이 하나의 테스트케이스.. 더보기 [백준알고리즘] 1339번: 단어 수학 -Python [백준알고리즘] 1339번: 단어 수학 -Python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 처음에는 DFS처럼 거의 완전탐색처럼 푸는 것 같다. 알고리즘 분류만 봐도 백트래킹으로 나와있다. 하지만 백트래킹으로 풀었을 때, 시간 초과가 발생했으며 시간을 줄이는 방법이 마땅치 않다. 실제로 다른 분들의 코드를 봐도 백트래킹처럼 푼 풀이는 보지 못했.. 더보기 이전 1 2 다음