본문 바로가기
[C++] 백준 1107번: 리모컨 문제 바로가기 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 수빈이는 악력이 지나치게 쎈가보다. 리모컨을 다루다가 일부 숫자 버튼이 고장났다. - 숫자 버튼이 고장났다는 내용을 문제 다 풀고 글 쓰는 지금 알았다. +, -도 고려하는 줄 알고 assert까지 써가봐 확인했는데... 역시 문제를 몇 번은 꼼꼼히 읽는 버릇을 들여야겠다. 0~9번까지의 숫자, +, - 버튼이 있다. 수빈이는 N번 채널로 이동하고 싶다. 어떤 버튼이 고장났는지 주어질 때, 채널 N으로 이동하려면 최소 몇 번 ..
[C++] 백준 10026번: 적록색약 문제 바로가기 문제 크기가 N×N인 그리드의 각 칸에 RGB 중 하나를 칠한 그림이 있다. 같은 색으로 이루어져 있는 구역으로 몇 개 나뉘어져 있다. 같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한다. 적록색약인 사람은 R과 G를 구별하지 못 한다. 그리드가 주어졌을 때, 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역수를 세어보자. 조건 1 ≤ N ≤ 100 풀이 이 문제는 2667번의 응용버전이다. 그리드에서 RGB 문자가 있는 한 칸을 기준으로 너비우선탐색을 하는데, 한 번 방문한 칸에는 숫자 등을 채워 넣는다. 그리고 더 이상 RGB 문자가 등장하지 않을 때까지 이를 반복한 뒤, 몇 번을 반복했는지만 출력하면 그게 구역의 수이다. 이 문제에서는 이를 두 번..
[C++] 백준 15686번: 치킨 배달 문제 바로가기 ⛳문제⛳ 1. 크기가 N×N인 도시는 (r, c) 좌표에 1×1크기의 칸으로 구성돼 있고, r과 c는 1부터 시작한다. 2. 도시의 각 칸은 치킨집(2)과 빈칸(0), 집(1) 중 하나이며 각 숫자로 주어진다. 3. 치킨 거리란 어떤 집과 그 집에서 가장 가까운 치킨집 사이의 거리이며 거리는 각 좌표의 차이(절댓값) 합이다. 4. 도시의 치킨 거리는 도시 내 모든 집 각각의 치킨거리 합이다. 5. 도시의 치킨 집 중 M개 점포를 남기고 나머지는 폐업시키고자 한다. 6. 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리가 최소가 됐을 때, 도시의 치킨 거리를 구해보자. 🧨입력조건🧨 2 ≤ N ≤ 50 1 ≤ M ≤ 13 ✨풀이✨ 1. 좌표 순서대로 입력을 받는다. 2. 입력된 수가 1 또는 ..
[C++] 백준 7569번: 토마토 문제 바로가기 🎊문제 개관🎊 이전에 풀었던 7576번과 유사하다. 하지만 그 때보다 한 차원 증가했다. 나는 오른쪽과 같은 좌표계를 사용할 것이다. // Vector3(h, r, c) typedef tuple Vector3; 🧨입력 조건🧨 2 ≤ N, M, H ≤ 100 🎢풀이🎢 📖 이전에 풀었던 7576번의 풀이를 많이 참고했다. 1. 토마토의 상태를 보여주는 3차원 배열 tomatos, 오늘 익은 토마토의 위치를 저장하는 큐 today, 내일 익을 토마토의 위치를 저장하는 큐 tomorrow가 있다. 2. 오늘 익은 토마토의 위치를 모두 한 번씩 방문하며 다음(3~5)을 반복한다. 3. 인접한 토마토(neighbor)가 아직 안 익었다면, 내일 익을 토마토에 위치를 저장해둔다. 4. 그 토마토의 상태..
[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\)이다. 하지만 이렇게 ..

티스토리툴바