개발일지

문제설명 입출력 예제 개념 K원을 만드는데 필요한 최소한의 동전 개수를 구하는 문제다. 가장 가치가 큰 동전부터 사용하는 것이 최선의 서택이므로, 이러한 선택을 통해 가장 적은 동전을 사용하여 주어진 금액을 만들 수 있는 최적의 해답을 찾을 수 있다. 즉, 그리디 알고리즘을 사용하여 문제를 효율적으로 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, K, n, answer = 0; cin >> N >> K; vector v(N); for (int i = 0; i > v[i]; for (auto it = v.rbegin(); it != v.rend(); ++it) { if (*it < K) { answer..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 최대 2명만 탑승 가능한 구명보트를 최소한으로 사용해 모든 사람을 구조하는 문제다. 이러한 상황에서 구명보트의 수를 최소화하려면, 남은 사람들 중 가장 가벼운 사람과 가장 무거운 사람을 동시에 태울 수 있는지 확인하면 된다. 따라서 투 포인터 알고리즘을 이용하여, 매 순간 보트에 최대한 많은 사람을 태우는 그리디 알고리즘을 구현하면 문제를 해결할 수 있다. 가장 가벼운 사람과 가장 무거운 사람이 보트의 무게 제한 내에 함께 탈 수 있다면, 두 사람을 동시에 태우는 것이 최선의 선택 그렇지 않다면, 가장 무거운 사람만 보트에 태우는 것이 최선의 선택 풀이 #include #include using namespace std; int solution(vec..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 끝말잇기 게임의 참가자들 중에서 규칙을 어긴 첫 번째 참가자와 그 참가자의 턴을 식별하고 출력하는 것을 목표로 한다. 여기서 주요 과제는 두 가지다. 각 턴에서 주어진 단어가 이전 단어의 마지막 글자로 시작하는지 판별 각 턴에서 주어진 단어가 이전에 사용된 적 있는 단어인지 확인 첫 번째 규칙은 문자열의 마지막 문자와 첫 문자를 비교하는 방식으로 해결할 수 있고, 두 번째 규칙은 find() 함수를 이용하여 단어의 이력을 관리하는 데이터 구조를 검색함으로써 해결할 수 있다. 이 두 가지 체크를 통과하지 못하는 첫 번째 단어를 발견하면, 해당 단어를 말한 참가자의 번호와 차례를 리턴하게 하면 된다. 풀이 #include #include #include ..

문제 설명 제한 사항 및 입출력 예제 개념 연속된 문자를 제거한다는 측면에서 스택을 활용하면 쉽게 해결할 수 있다. 풀이 #include #include using namespace std; int solution(string s) { stack st; for (int i = 0; i < s.size(); ++i) { if (st.empty()) st.push(s[i]); else if (st.top() == s[i]) st.pop(); else st.push(s[i]); } return st.empty(); }

문제 설명 제한 사항 및 입출력 예제 개념 주어진 정수 벡터에서 모든 숫자의 조합 중 가장 큰 수를 찾는 문제다. 다음과 같은 조건을 고려해 보자. 숫자의 순서: 수를 이루는 각 숫자들의 배치 순서를 문자열로 바꾸어 정렬 숫자의 자릿수: 두 숫자가 주어졌을 때, 자릿수가 다르다면 두 숫자의 문자열로 바꾼 후 이어 붙였을 때 큰 방향을 확인 따라서 정렬 기준을 두 문자열을 더했을 때 큰 쪽을 리턴하게 새롭게 정의하면 된다. 풀이 #include #include using namespace std; string solution(vector numbers) { string answer = ""; vector v; 정답을 저장할 문자열 answer와 벡터 v를 초기화한다. for (const auto& val ..

명령어 저급 언어와 고급 언어 우리가 프로그램을 만들 때 사용하는 프로그래밍 언어는 컴퓨터가 이해하는 언어와 인간이 이해하는 언어로 나뉜다. 여기서 사람을 위한 언어는 고급(high-level) 언어라고 하고, 컴퓨터를 위한 언어는 저급(low-level) 언어라고 한다. 즉, 고급 언어로 작성된 소스 코드가 실행되려면 반드시 저급 언어, 즉 명령어로 변환되어야 한다. 먼저 명령어로 이루어진 저급 언어에 대해 다뤄보자. 저급 언어에는 기계어와 어셈블리어 두 가지 종류가 있다. 기계(machine)어는 0과 1의 명령어 비트로 이루어진 명령어 모음이다. 기계어는 이진수로 이루어져 있지만, 가독성을 위해 아래와 같이 16진수로 표현하기도 한다. 하지만 오로지 컴퓨터만을 위해 만들어진 기계어는 사람이 읽으면 ..

문제 설명 제한 사항 및 입출력 예제 개념 피보나치 수를 나눈 나머지를 구하는 문제다. 일반적인 재귀 함수 방식으로 피보나치 수열을 구해서 계산하면 같은 값을 여러 번 계산하게 되기 때문에 높은 확률로 시간 초과가 걸린다. 따라서 소수를 구할 때 에라토스테네스의 체 방식으로 미리 값들을 구해놓은 것처럼, 피보나치 수도 미리 구해놓고 계산하는 다이나믹 프로그래밍 방식을 채용하면 문제를 효율적으로 해결할 수 있다. 풀이 #include using namespace std; int solution(int n) { vector dp(n + 1, 0); dp[0] = 0; dp[1] = 1; for (int i = 2; i

문제 설명 제한 사항 및 입출력 예제 개념 주어진 정수 n의 이진 표현에서 1의 개수가 같은 n보다 큰 정수 중 가장 작은 정수를 찾는 문제다. 이진 표현을 하기 위해 bitset 라이브러리를 이용하면 효율적으로 문제를 해결할 수 있다. 풀이 #include #include #include using namespace std; int CountOnesInBinary(int number) { bitset binaryRepresentation(number); string binaryString = binaryRepresentation.to_string(); return count(binaryString.begin(), binaryString.end(), '1'); } int solution(int n) { ..

문자 표현 개요 문자를 0과 1의 의진 코드로 변환하는 메커니즘을 공부하기에 앞서, 문자 표현과 관련된 기본적인 용어들을 간단하게 살펴보자. 먼저 문자 집합(character set)이라는 개념이 존재한다. 이는 컴퓨터가 인식하고 표현할 수 있는 문자의 집합체를 의미한다. 컴퓨터는 이러한 문자 집합에 포함된 문자들만 인식 가능하다. 하지만 문자 집합에 속한 문자라 하더라도 컴퓨터가 바로 이해하는 것은 아니다. 사람이 이해하는 문자를 컴퓨터가 이해할 수 있는 이진 코드, 즉 0과 1로 변환해야만 컴퓨터가 인식하고 처리할 수 있다. 이처럼 인간이 이해하는 정보를 컴퓨터가 처리할 수 있는 형태로 변환하는 과정을 인코딩(encoding)이라고 한다. 반대로 컴퓨터가 처리하는 정보를 인간이 이해할 수 있는 형태로..

정보 단위와 진법 개요 데이터는 정적인 정보로서 컴퓨터에서 처리하는 기본적인 단위다. 이는 정보를 구성하는 최소 단위인 비트로(bit)로 이루어져 있으며, 0과 1로 표현된다. 따라서 1비트는 2개의 데이터를 가질 수 있고, n비트는 2^n가지 정보를 표현할 수 있다. 데이터는 이 비트들이 모여서 더 큰 단위인 바이트(Byte)를 형성하게 된다. 바이트는 일반적으로 8비트로 구성되며, 컴퓨터에서 데이터를 저장하고 처리하는 기본 단위로 사용된다. 바이트 또한 더 큰 단위로 묶일 수 있는데, 1000바이트가 모여 1킬로바이트(kB, Kilobyte)가 되고, 1000킬로바이트가 모여 1메가바이트(MB, Megabyte), 1000메가바이트가 모여 1기가바이트(GB, Gigabyte), 1000기가바이트가 모..