개발자 이야기

문제 https://www.acmicpc.net/problem/13305 도시마다 주유소가 있고, 가격은 다 다르다. 도시에서 도시를 이동할 때 거리가 있는데 거리만큼 이동하기 위해서 기름이 필요하다. 그래프로 보자면, 노드가 도시이고, 해당 주유소의 가격을 나타낸다. 에지에 있는 값은 도시간 이동에 필요한 거리이다. 처음 도시에서 마지막 도시까지 이동할 때 가장 최소비용을 구하는 문제이다. 접근방식 가격이 5 -> 2 -> 4 -> 1 순으로 되어있다는 사실을 알았을 때, 도시를 한칸씩 이동하면서 현재보다 기름값이 싼 도시를 구합니다. 이 도시까지 이동할 때 필요한 기름을 현재 도시에서 다 넣고 이동하면 될 것이라고 생각했습니다. 그래서, 처음에는 이중루프를 생각하고, 현재 도시보다 싼 도시가 나올때까..

문제 https://www.acmicpc.net/problem/1541 숫자와 +, - 로 구성된 수식이 있다고 했을 때, 적당히 괄호를 쳐서 수식의 계산 값이 최소가 되도록 괄호의 위치를 결정하는 문제 실제로 괄호의 위치를 구할 필요는 없고, 괄호가 있다고 했을 때 계산값이 최소가 되기만 하면 된다. 접근방식 직관적으로 +,-로만 구성되어있다고 하면 연속된 +항을 모두 괄호로 묶어서 먼저 계산을 한다. 그다음 -만 남을텐데, -는 무조건 왼쪽에서 오른쪽으로 순서대로 빼주는 것이 최소가 된다. 생각해보면, 최소가 되려면 - 뒤에 있는 값은 무조건 커야 큰 수를 뺄 수 있다. 그리고 수식에 -로만 구성이 되어있다고 하면 일부러 괄호를 쳐서 작은 값을 만들어서 뺄 필요는 없다. 예) 2-2-2 = -2 지만..

문제 https://www.acmicpc.net/problem/1931 회의실은 하나이고, 시작과 끝시간이 명시된 회의가 N개 있다고 하자. 겹치지 않게 잘 배열하여 최대로 진행할 수 있는 회의의 개수를 찾는 문제 접근방식 1) 시작시간을 1차키, 회의시간을 2차키로 하여 정렬 후 탐색 - 가장 빠르게 개최되는 회의 중, 회의시간이 짧은 것을 선택해 나가는 방식 - 모든 시작시간을 대상으로 N번 탐색을 해야하므로 O(N^2)복잡도가 생김 - 당연히 시간 초과 2) 회의시간순으로 정렬하여 가장 짧은 시간회의부터 선택 - 짧은 것 먼저 선택하다보면, 다음 회의를 선택할 때 겹치는 지 여부를 판단할 때 조건이 복잡해진다. - 또한, 선택된 회의가 여러개라면 루프를 돌거나 정렬한 상태로 유지를 해야하는데 이게 ..

문제 https://www.acmicpc.net/problem/2217 N개의 로프가 있을 때, 각 로프별 최대로 들어올릴 수 있는 무게가 주어졌다고 하자. 로프를 여러개 사용하는 경우 균등하게 무게가 배분된다고 할때, 최대로 들어올릴 수 있는 무게를 구한다. 접근방식 로프가 감당할 수 있는 무게를 내림차순으로 정렬을 하게 되면, 첫번째 무게가 로프 1개를 사용했을 때 들 수 있는 최대 무게가 됩니다. 다음으로 첫번째, 두번째 두개의 로프를 사용한다고 했을 때 두번째 로프의 무게에 2를 곱해주면 두 개의 로프를 사용해서 들 수 있는 최대 무게가 됩니다. 다음으로 세번째 로프의 경우, 3을 곱해주면 세개의 로프를 사용해서 들 수 있는 최대 무게가 됩니다. 이런 방법으로 N까지 N개의 로프를 사용했을 때 들..

문제 https://www.acmicpc.net/problem/1026 a, b 두개의 배열이 있을 때, 같은 위치에 있는 값을 서로 곱했을 때 나오는 값이 최소가 되도록 a배열의 원소를 재배열 하는 문제 접근방식 a,b 두 배열은 0이거나 100이하의 자연수로만 구성된다. answer = (a[i] * b[i]) + ... + (a[N-1] * b[N-1]) 이 최소가 되는 수를 구하자. 가장 쉽게 생각하면, a배열은 오름차순으로, b배열은 내림차순으로 정렬 후 서로 곱해주면 항상 최소가 된다. b배열은 재배열 하지 말라는 조건때문에 좀 헷갈렸는데... (체크할 수도 없는 조건이 왜 들어가 있는지...) (풀이) 1 #include 2 #include 3 #include 4 5 using namespa..

문제 https://www.acmicpc.net/problem/11047 금액이 다양한 화폐가 있다고 했을 때, 특정 금액을 구성하기 위해 필요한 가장 최소 화폐개수를 구해보자. 예) 1000원은 100원짜리 10개도 되지만, 500원짜리 1개도 되고, 1원짜리 1개도 된다. 접근 방식 금액을 화폐단위로 나눈 몫이 그 개수이므로, 이것을 계속 더해나간다. 단 가장 큰 단위의 화폐단위부터 적용해야하므로, 오름차순 정렬되어있으므로, 가장 뒤에있는 단위부터 차례대로 나눠서 몫을 더한다. 그리고, 다음 단계에서는 이전에 카운트된 금액만큼 제외하고 다시 나누어야 하므로 나머지 연산자를 통해서 다음에 사용할 금액을 구한다. ex) 100원, 500원, 1000원이 있다고 했을 때, 2300원을 가지고 생각해보자. ..

문제 https://www.acmicpc.net/problem/11399 ATM앞에서 N명의 사람이 돈을 인출하는데 각각 pi의 시간이 걸린다. 당연히, 짧은 시간을 소비하는 사람부터 줄을 서서 처리하면 전체 걸리는 시간이 최소가 될 것이다. 이 최소 시간을 구하라. 접근방식 N명의 사람에 대해서 소비시간을 정렬한 후, 누적된 시간을 다 더하면 된다. (풀이) 1 #include 2 #include 3 4 using namespace std; 5 int main() 6 { 7 int N, i; 8 int time[1000]; 9 int acc = 0; 10 int answer = 0; 11 cin >> N; 12 13 for (i = 0 ; i > time[i]; 16 } 17 sort(time, tim..

문제 https://www.acmicpc.net/problem/2839 N kg의 설탕을 배달하기 위해, 3kg, 5kg을 담을 수 있는 주머니를 사용할 수 있다. 운반에 필요한 최소 주머니 개수를 구하라 ex) 18kg의 경우 3kg 6개도 되고 5kg 3개, 3Kg 1개 총 4개도 가능하다. 접근 방식 그리디 방법이라고 해서, 일단 모든 경우의 수를 다 탐색을 해야겠다고 생각했습니다. 그래서 쉽게 구현할 수 있는 재귀 호출을 이용해서, 3kg, 5kg일때 각각 경우의 수에 대해서 조사를 합니다. (풀이1) 1 #include 2 #include 3 4 #define P1 3 5 #define P2 5 6 7 void find(int N, int depth, int *answer) 8 { 9 if (d..

공부 순서 [Python/C++ 기본 문법 → 코드업 기초 100제 → BOJ 그리디/탐색 유형 문제 풀이 → 특정 기업 대상의 기출 문제 풀이] 계획 1. 코드업 기초 100제 : ~ 2023.3.10 2. Greedy : 3. Search : 4. Dynamic programming : 참고사이트 - 코드업: http://codeup.kr/ - BOJ: https://www.acmicpc.net/ - 프로그래머스: https://programmers.co.kr/ - 백준 : https://www.acmicpc.net/ - 리트코드 : https://leetcode.com/