승코딩당당당

문제[C++] 백준 1946: 신입 사원 SILVER 1https://www.acmicpc.net/problem/1946 접근 방법이 문제는 지원자들의 서류 성적, 면접 성적이 주어졌을 때,“두 성적 모두 다른 지원자에게 밀리는 경우 탈락”이라는 기준으로 합격할 수 있는 최대 인원 수를 구하는 문제다. 처음에는 각 지원자에 대해 “이 사람보다 서류, 면접 둘 다 더 좋은 사람이 있는지”를 2중 for문으로 전부 비교하는 방식으로 생각했다. 하지만 이렇게 하면 지원자 수 N이 클 때 O(N²) 가 되어 시간 초과가 발생했다.. 그래서 접근을 바꿔서,서류 성적 기준으로 오름차순 정렬을 하고서류 1등은 무조건 합격이므로 기준으로 삼고,뒤에서부터는 지금까지 본 면접 성적의 최솟값(Min)을 계속 갱신하면서,현..

문제[C++] 백준 5585: 거스름돈 BRONZE 2https://www.acmicpc.net/problem/5585 접근 방법이 문제는 1000엔을 냈을 때 거슬러 받아야 할 금액이 주어지면,동전의 개수를 최소로 사용해 거스름돈을 만드는 문제이다. 사용 가능한 동전은 500, 100, 50, 10, 5, 1 엔으로 이미 큰 값부터 작은 값까지 정렬된 상태이며,이 동전 체계에서는 그리디 알고리즘이 항상 최적해를 보장한다. 그래서 다음과 같은 전략을 사용했다.입력받은 금액을 1000엔에서 빼서 거스름돈(money) 을 계산한다.가장 큰 동전부터 차례대로 확인하면서,해당 동전을 최대한 많이 사용한다.남은 금액은 나머지 연산으로 갱신한다.사용한 동전의 개수를 누적해 최종 결과로 출력한다. 구현 시 주의할 ..

문제[C++] 백준 22864: 피로도 BRONZE 2https://www.acmicpc.net/problem/22864 접근 방법이 문제는 하루 24시간 동안 일을 할지, 쉴지 선택하면서피로도 한도(m)를 넘지 않도록 하면서 최대한 일을 많이 하는 시뮬레이션 문제다. 한 시간 일하면피로도 a 증가일량 b만큼 증가한 시간 쉬면피로도 c만큼 감소 (단, 0 미만으로는 내려가지 않음)피로도가 m을 초과하면 더 이상 일할 수 없다. 그래서 하루 24시간을 1시간 단위로 반복하면서,현재 피로도 now에 a를 더했을 때 m 이하여야 일을 할 수 있다.now + a 아니면 → 쉬기일을 한 시간은 cnt를 1 증가모든 시간이 끝나면 cnt * b가 총 일량이 된다.즉, 그리디하게 “가능하면 무조건 일하고, 아니면 ..

문제[C++] 백준 1541: 잃어버린 괄호 SILVER 2https://www.acmicpc.net/problem/1541 접근 방법이 문제는 주어진 식에 괄호를 적절히 쳐서 결과 값을 최소로 만드는 문제다.핵심 아이디어는 정말 단순하다.한 번 - 가 등장한 이후에는, 그 뒤에 나오는 모든 수를 한 덩어리로 묶어서 한 번에 빼면 전체 값을 최소로 만들 수 있다. 예를 들어,55-50+40 이라면→ 55-(50+40) 으로 묶는 게 최솟값즉, 첫 번째 -를 기준으로 식을 나누고,첫 번째 덩어리는 그대로 더하고두 번째 덩어리부터는 “+로 묶인 값들을 모두 더한 뒤” 통째로 빼면 된다. 상세 아이디어1. split 함수로 문자열 자르기먼저, 문자열을 특정 문자 기준으로 잘라주는 split 함수를 만들었다...

문제[C++] 백준 1744: 수 묶기 GOLD 4https://www.acmicpc.net/problem/1744 접근 방법이 문제는 주어진 정수들을 적절히 묶어서(곱하거나 더해서) 전체 합의 최댓값을 만드는 문제다.핵심 아이디어는 수의 성질에 따라 전략을 나누는 그리디 접근이다.수들을 다음 네 종류로 분리한다.1보다 큰 양수→ 두 개씩 묶어서 곱하는 것이 이득음수→ 두 개씩 묶어서 곱하면 양수가 되어 이득1→ 어떤 수와 곱해도 이득이 없으므로 그냥 더함0→ 남는 음수 하나를 제거(상쇄)하는 용도로 사용이를 위해양수(>1)는 내림차순 우선순위 큐음수는 오름차순 우선순위 큐로 관리한다.구현 시 주의할 점1은 절대 곱하지 않는다.1 × x ≤ 1 + x 이므로 항상 더하는 게 이득이다.음수가 하나 남았을..

문제[C++] 백준 1715: 카드 정렬하기 GOLD 4https://www.acmicpc.net/problem/1715 접근 방법이 문제는 여러 묶음의 카드가 주어졌을 때, 모든 카드를 하나로 합치는 데 필요한 비교 횟수의 최소값을 구하는 문제이다.핵심 아이디어는 항상 가장 작은 두 묶음을 먼저 합치는 것이다.두 묶음을 합칠 때 발생하는 비교 횟수는 두 묶음의 크기 합이고, 이 값은 이후에도 계속 누적되기 때문에 작은 값부터 처리해야 전체 합이 최소가 된다. 이를 효율적으로 구현하기 위해 우선순위 큐(priority_queue) 를 사용했다.모든 카드 묶음을 우선순위 큐에 넣는다. (오름차순)큐에서 가장 작은 두 값을 꺼내 합친다.그 합을 결과에 더하고, 다시 큐에 넣는다.큐에 하나만 남을 때까지 반..

문제[C++] 백준 11047: 동전 0 SILVER 4https://www.acmicpc.net/problem/11047 접근 방법이 문제는 주어진 동전들을 이용해 합이 K가 되도록 만들 때 필요한 최소 동전 개수를 구하는 문제이다.각 동전은 무한히 사용할 수 있고, 동전의 가치들은 오름차순으로 주어진다.이 문제의 핵심은 그리디 알고리즘이다.항상 가치가 가장 큰 동전부터 최대한 사용하는 것이 최적이라는 조건이 보장되어 있다.그래서 다음과 같은 방식으로 접근했다.동전 배열의 가장 뒤(가장 큰 가치) 부터 확인한다.현재 동전이 k보다 작거나 같다면,k / coin[i] 만큼 사용할 수 있고사용한 만큼 k %= coin[i]로 남은 금액을 갱신한다.모든 동전을 확인할 때까지 반복한다.이 과정을 거치면 최소..

그래프 탐색이나 탐색 알고리즘과는 다르게,선택의 기준이 핵심이 되는 알고리즘이 바로 그리디 알고리즘(Greedy Algorithm)이다.그리디 알고리즘은 매 순간 현재 상태에서 가장 좋아 보이는 선택을 하며 문제를 해결해 나가는 방식이다. 구현이 비교적 쉽고 빠르기 때문에 코딩 테스트에서 자주 등장하지만,항상 정답을 보장하지는 않는다는 점에서 주의가 필요하다.이번 글에서는 그리디 알고리즘의 개념과 특징, 동작 과정, 그리고 사용할 때 주의할 점을 중심으로 정리해보려고 한다. ✍️ 그리디 알고리즘이란?그리디 알고리즘(Greedy Algorithm)은현재 상태에서 볼 수 있는 선택지 중 최선의 선택을 반복하는 알고리즘이다. 즉,지금 당장 가장 좋아 보이는 선택을 하고그 선택이 이후의 선택에 어떤 영향을..

문제[C++] 백준 2512: 예산 SILVER 2https://www.acmicpc.net/problem/2512 접근 방법이 문제는 각 지방의 예산 요청이 주어졌을 때, 총 예산 M을 넘지 않도록 상한액을 정해 지방 예산을 배정하는 문제이다. 핵심은 “상한액을 X로 정했을 때, 각 지방에 min(요청 금액, X)를 배정하면 총합이 M을 넘는가?”를 판단하는 것이다.상한액이 커질수록 총 배정 예산은 증가하므로, 이 조건은 단조성을 가지게 된다.따라서 상한액을 대상으로 이분 탐색(Parametric Search) 을 사용할 수 있다.가능한 상한액의 범위: 0 ~ 요청 예산의 최댓값mid를 상한액이라고 가정하고 총 배정 예산을 계산총합이 M을 초과하면 상한액을 줄이고end = (mid - 1);초과하지 ..

이번 실습에서는 아두이노 UNO와 Easy Module Shield, Arduino Motor Shield를 이용해온도 변화에 따라 모터와 LED가 동작하는 제어 시스템을 구현해보았다. 실제 온도 센서 대신,Easy Module Shield에 장착된 가변 저항을 사용하여 온도가 변화하는 상황을 가상으로 구현하였다.(실제 온습도 센서를 사용하면, 테스트가 매우 힘들기 때문이다.. 냉장고에 넣었다 뺐다...) 사용한 하드웨어 구성Arduino UNOEasy Module ShieldArduino Motor ShieldDC 모터RGB LED (Easy Module Shield 내장)12V 전원 어댑터 동작 원리가변 저항 값 범위: 0 ~ 1023저항 값이 클수록 고온, 작을수록 저온을 의미이를 기준으로 온도..