본문 바로가기

분류 전체보기

 (109)
[C++] 백준 17626번: Four Sqaures 문제 바로가기 ⚽문제가 무엇일까?⚽ 1 ≤ N ≤ 50,000인 자연수 N이 입력되면, 이 수를 제곱수의 합으로 나타낼 수 있다. 라그랑주는 모든 자연수를 4개 이하의 제곱수 합으로 표현할 수 있음을 증명했다. 어떤 자연수를 제곱수의 합으로 나타내는 여러가지일 수 있다. 우리는 주어진 자연수 N을 제곱수의 합으로 나타낼 때, 그 개수의 최소값을 찾는게 목표다. ⚾어떻게 풀지?⚾ 위 사진처럼 차근차근 적어봐도, 규칙성을 찾기란 어렵다. 그래서 단순하게 생각했다. N 이하의 제곱수 중 가장 큰 수부터 연산을 하는 것이다. 예로, N이 8이면 4 두 번으로 표현이 된다. 하지만, 이렇게 설계하고 예제를 돌려보면 다른 답이 나온다. 가장 큰 제곱수가 항상 옳은 선택은 아니라는 뜻이다. 따라서, 이를 상한선을 낮..
[C++] 백준 14500번: 테트로미노 문제 바로가기 ⛳문제에서 요구하는 것⛳ 1. 크기가 N×M인 종이 위에 테트로미노 하나를 놓는다. 2. 테트로미노가 놓인 칸에 쓰여있는 수들의 합의 최대값을 알아보자. 3. 테트로미노를 회전, 대칭을 시켜도 된다. 🧨주어진 조건🧨 1. 4 ≤ N, M ≤ 500 2. 각 칸의 입력은 1000 미만의 자연수다. ✨처음 생각한 풀이✨ 1. 각 점을 방문한다. 2. 다섯가지의 테트로미노에 대해, 3. 기준 위치를 방문한 점에 놓고 4. 90도씩 회전시키며 테트로미노가 놓인 칸에 쓰여있는 수의 합을 구한다. 5. 이번엔 좌우, 상하 대칭을 시켜서 확인한다. - 그런데, 테트로미노가 놓인 칸을 어떻게 알아내냐가 관건이다. - 나는 각 테트로미노의 기준 위치를 (0, 0)으로 두고, 그 테트로미노를 구성하는 다른 ..
[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++] 새로 알게 된 사실 몇 가지 (계속추가예정) 1. 전역배열을 선언하면 자동으로 0으로 초기화된다. 2. STL 관련 정의오류는 적절한 Container 조합을 썼는지 확인하자. 예를 들어, priority_queue의 Container가 들어갈 인수 자리에 queue를 넣으면 초기화 과정 중 begin 함수가 없어서 컴파일 오류가 발생한다. 3. algroithm 헤더 내 함수들과 내장 함수를 구분해 쓰자. 예를 들어 내장함수 qsort는 STL Container를 지원하지 않는다. 4. C++17부터 튜플을 다음처럼 쓸 수 있다. auto [a, b, c] = make_tuple(1, 2, 3); 5. typedef tuple Vector3 와 같은 표현으로 using Vector3 = tuple가 있다. - 둘의 차이라면, using에서는 템플..
[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\)이다. 하지만 이렇게 ..

티스토리툴바