본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 2579번: 계단 오르기 문제 바로가기 ⛳문제에서 요구하는 것⛳ 1. 일정한 점수가 쓰여 있는 계단이 있다. 2. 계단을 밟으면 그 계단에 쓰인 점수를 얻는다. 3. 한 번에 한 계단 혹은 두 계단씩 오를 수 있다. 4. 연속된 세 개의 계단을 모두 밟으면 안 된다. 5. 마지막 도착 계단은 반드시 밟아야 한다. 6. 얻을 수 있는 총 점수의 최대값을 출력하자 🧨주어진 조건🧨 1. 계단의 개수 ≤ 300, 자연수 2. 계단의 점수 ≤ 10,000, 자연수 ✨내가 처음 생각한 풀이✨ 1. 그리디 알고리즘을 적용해보기로 했다. 2. 하지만 구현 후 예제와 비교했을 때 결과 값이 다르다. 3. 이 풀이가 아닌가보다. ✨두 번째로 생각한 풀이✨ 1. 알고리즘 분류가 DP이길래, DP로 풀기로 했다. 2. N이 1일 땐, 첫 번째 계단의..
[C++] 백준 7662번: 이중 우선순위 큐 문제 바로가기 ⛳문제에서 요구하는 것⛳ 1. 이중 우선순위 큐(Q)는 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제할 수 있다. 2. Q에 적용될 연산이 주어질 때, 이를 처리한 후 남은 데이터에서 최대와 최소를 출력하자. 🧨주어진 조건🧨 1. 정수 T의 범위는 주어지지 않았다. 2. K ≤ 1,000,000 3. N은 32비트 정수다. 즉, int로 커버된다. 4. 동일한 정수가 삽입될 수 있다. 5. 최댓값(최솟값)이 둘 이상일 때, 삭제 연산이 진행되면 하나만 삭제된다. 6. Q가 비어있는데 'D' 입력이 주어지면 이 연산은 무시해도 된다. ✨내가 처음 생각한 풀이✨ 1. MinHeap을 구현하고, 값을 차례로 넣는다. 2. 최솟값을 삭제할 때는 root를 제거한다. 3. 최댓..
[C++] 백준 1931번: 회의실배정 문제 바로가기 ⛳문제에서 요구하는 것⛳ 1. 한 개의 회의실이 있다. 2. N개의 회의가 주어진다. 3. 각 회의를 서로 겹치지 않게 배치한다. 4. 배치할 수 있는 회의의 최대 개수를 찾아보자. 🧨주어진 조건🧨 1. 1 ≤ N ≤ 100,000 2. 0 ≤ 시작시간 ≤ 종료시간 ≤ 2³¹-1 3. 한 회의가 끝남과 동시에 다음 회의가 시작될 수 있다. 4. 회의의 시작과 종료가 같을 수 있다. ✨내가 처음에 생각한 풀이✨ 1. vector에 각 회의를 담는다. 2. 시작, 종료 우선순위로 오름차순 정렬한다. 3. 각 회의에 대해서 다음(4~6)을 수행한다. 4. 선택된 회의의 다음부터 끝 중 ⅰ. 시작시간 ≥ 현재 회의의 종료시간 ⅱ. 가장 빠른 종료시간인 회의를 찾는다. 5. 만약, 그런 회의가 없다..
[C++] 백준 2447번: 별 찍기 - 10 문제 바로가기 파이썬을 배우면 무조건 배운다는 별찍기 문제가 발전한 형태의 문제다. 재귀함수를 사용하는 유형인데, 아이디어를 생각하는데 조금 어려웠다. 3x3 블럭을 기준으로 어떻게 해보려고 했는데, 3x3 블럭 옆에 3x3 블럭을 놓는다는 개념을 구현하는게 불가능이었다. 3x3 블럭이 개행문자를 포함하고 있기 때문. 이 개행처리를 어떻게 해야할지 꽤 오랫동안 고민했다. 하지만 불가능하다고 판단하고, 다른 방법을 강구했다. 차라리, N * N 블럭에 모두 별표를 칠하고 빈 공간만 뚫기로 했다. 이 쪽이 훨씬 쉽고 또 옳은 풀이일거라고 판단했다. 블럭을 나타내는 배열 table과 한 변의 길이를 나타내는 변수 N을 전역변수로 선언했다. 블럭에 빈 공간을 뚫는 함수는 eidt으로, 인수로 대상이 되는 블럭의..
[C++] 백준 1011번: Fly me to the Alpha Centauri 문제 바로가기 수학을 이용하는 문제다. 내 경험 상 이런 문제를 풀 땐, 차근차근 손으로 풀어가며 패턴을 찾아야 한다. 이 문제도 그렇게 풀기 시작했다. 그랬더니 역시나 패턴이 보였다. $$1 : 1$$ $$2 : 1, 1$$ $$3 : 1, 1, 1$$ $$4 : 1, 2, 1$$ $$...$$ $$9 : 1, 2, 3, 2, 1$$ $$10 : 1, 1, 2, 3, 2, 1$$ 좌우대칭이다. 아닌 것도 있지만... 일단 어느정도 좌우대칭의 성질을 가지고 있다. 또한, 가운데를 기점으로 양 옆으로 1씩 차이가 나는 등차수열을 어느정도 이룬다. 여기까지 생각한 나는 다음과 같은 식을 세웠다. $$L = 2\sum_{i=1}^{n}{i} + K$$ 위에서 \(L\)은 \(y - x\)이다. 하지만 이렇게 ..
[C++] 백준 1193번: 분수찾기 문제 바로가기 문제에서 주어진 표는 다음과 같다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 각 대각선에서 분모는 ↗ 방향으로 증가하고, 분자는 ↙ 방향으로 증가한다. 주어진 표에서 방문 순서대로 값을 메기면, 1 2 6 7 15 … 3 5 8 14 … … 4 9 13 … … … 10 12 … … … … 11 … … … … … … … … … … … 사실 나는 문제를 제대로 읽지 않아, 아래처럼 생각했었다. 1 2 4 7 11 … 3 5 8 12 … … 6 9 13 … … … 10 14 … … … … 15 … … … … … … … … … … … 하지만 결정적으로 이러한..
[C++] 백준 2941번: 크로아티아 알파벳 문제 바로가기 처음에는 문자열 입력을 받고, 각 크로아티아 알파벳 마다 문자열 내에서 찾아, 0 등의 임의문자로 대치한 후 총 알파벳 수를 세아리려고 했다. 하지만, 그렇게 하면 반복을 많이 하기 때문에, 문자열의 첫 글자부터 시작하여 한 글자씩 크로아티아 알파벳에 해당하는지 확인하기로 했다. 그러기 위해 switch-case를 이용했다. 큰 틀에서 for문으로 각 문자를 확인한다. 문자에 도달하면 일단 수를 세어준다. 이제, 크로아티아 알파벳에 해당하는지 검사하는데, 크로아티아 알파벳에 해당하면 그 길이만큼 인덱스를 건너 뛴다. 예를 들어 dz= 같은 경우는 인덱스를 두 문자 건너 뛰는 방식이다. 이 문제를 풀며 두 번의 실수가 있었다. 아래 코드는 첫 번째 실수이다. switch-case의 이해 부족..
[C++] 백준 1074번: Z 문제 바로가기 이 문제를 재귀함수를 통해 풀 수 있을 것이라 생각했다. 큰 영역에서 시작해서 한 변의 길이를 절반씩 줄여나가며 그 길이가 2가 됐을 때, 네 칸에 Z 순서로 방문하여 순서를 저장하는 방식으로 코드를 구현했다. 다음 코드가 이 방식을 나타낸 코드 전문이다. #include using namespace std; // pivot: [r, c], interval : [2^N, K] void move(int* table, int* pivot, int* interval, int& order) { // Step 1. If interval is minimum, Mark. if (interval[1] == 2) { int delta[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1}..

티스토리툴바