승코딩당당당

문제[C++] 백준 15654: N과 M (5) SILVER 3https://www.acmicpc.net/problem/15654 접근 방법이 문제(백준 15654)는 주어진 N개의 서로 다른 자연수 중에서 M개를 골라 나열하는 모든 수열을 출력하는 문제다.즉, 중복 없는 순열을 구하는 문제이고, 입력으로 주어진 수들을 사용한다는 점이 15649랑 다르다. 문제 조건:수들은 1, 2, 3, … 이 아니라 입력으로 주어지는 임의의 수들한 수는 한 번만 사용할 수 있음 (중복 선택 불가)출력은 사전 순(오름차순) 으로 나와야 함그래서 풀이 전략은:먼저 입력받은 수들을 vect에 저장하고 sort로 정렬한다.→ 이렇게 하면 백트래킹을 할 때 작은 수부터 탐색하게 되어, 자연스럽게 사전 순으로 수열이 출력된다..

문제[C++] 백준 2578: 빙고 SILVER 4https://www.acmicpc.net/problem/2578 접근 방법이 문제는 사회자가 숫자를 하나씩 부를 때마다, 현재 내 빙고판에서 몇 개의 빙고 줄이 완성되었는지를 확인해서가장 처음으로 빙고 3줄 이상이 되는 순간의 호출 횟수를 출력하는 문제다. 기본 아이디어는 다음과 같이 잡았다.빙고판 입력5×5 빙고판을 vect[5][5]에 저장한다.이후 사회자가 부르는 숫자 25개를 call 벡터에 저장한다.숫자가 불릴 때마다 처리find(call[i]) 함수로 현재 숫자 call[i]이 빙고판 어디에 있는지 찾아서 그 위치를 -1로 표시한다.(지워진 칸 = 체크된 칸)동시에, 그 칸의 좌표를 전역 변수 yy, xx에 저장해둔다.해당 위치 기준으로 빙..

문제[C++] 백준 15652: N과 M (4) SILVER 3https://www.acmicpc.net/problem/15652 접근 방법백준 15652번은 1부터 N까지의 자연수 중에서 M개를 고르는 경우를 출력하는 문제인데,비내림차순(오름차순+중복 허용)같은 수를 여러 번 골라도 됨이라는 점이 15650번(중복 허용 X)과 다르다.https://xeungcoding.tistory.com/87 [C++] 백준 15650: N과 M (2)문제[C++] 백준 15650: N과 M (2) SILVER 3https://www.acmicpc.net/problem/15650 접근 방법1부터 N까지 중에서 M개를 고르는 조합(오름차순) 을 모두 출력하는 문제다.순서가 바뀐 경우는 같은 조합으로 취급하므xeung..

문제[C++] 백준 15650: N과 M (2) SILVER 3https://www.acmicpc.net/problem/15650 접근 방법1부터 N까지 중에서 M개를 고르는 조합(오름차순) 을 모두 출력하는 문제다.순서가 바뀐 경우는 같은 조합으로 취급하므로(예: 1 2와 2 1은 같은 조합), 항상 작은 수부터 큰 수로만 뽑히도록 백트래킹을 구성하면 된다.이를 위해 start 변수를 사용해, 다음에 뽑을 수 있는 숫자의 시작 범위를 제한했다.현재 i를 뽑았다면 다음 재귀에서는 i+1부터만 고를 수 있게 함그래서 자동으로 중복/역순이 발생하지 않는다 상세 아이디어picked : 현재까지 선택한 숫자들을 담는 벡터depth : 현재까지 몇 개를 뽑았는지(선택 개수)start : 다음에 뽑을 수 있는 최..

문제[C++] 백준 1747: 소수&팰린드롬 SILVER 1https://www.acmicpc.net/problem/1747 접근 방법이 문제는 주어진 수 N 이상에서 가장 작은 소수이면서 팰린드롬(회문)인 수를 찾는 문제다.즉, 두 조건을 동시에 만족해야 한다.소수(Prime Number)앞뒤가 같은 수(팰린드롬)그래서 풀이를 두 단계로 나누었다. 1. 소수 판별 – 에라토스테네스의 체먼저 충분히 큰 범위(약 1003000까지)에 대해에라토스테네스의 체를 이용해 소수 여부를 미리 구해두었다.for (int i = 2; i 소수가 아닌 수는 -1로 표시마지막에 vect[0], vect[1]도 소수가 아니므로 -1 처리이렇게 하면 이후에는 빠르게 소수 여부를 확인할 수 있다. 2. 팰린드롬 검사N부터 시..

문제[C++] 백준 14940: 쉬운 최단거리 SILVER 1https://www.acmicpc.net/problem/14940 접근 방법이 문제는 시작점(값이 2인 위치)에서 각 칸까지의 최단 거리를 구하는 문제이다.이동은 상하좌우로 가능하며, 값이 1인 칸만 이동할 수 있고 0은 이동할 수 없다.최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색) 를 사용했다. 핵심 아이디어:시작점(2)의 좌표를 먼저 찾는다.BFS를 이용해 사방 탐색을 진행한다.이동 가능한 칸(값이 1)만 큐에 넣는다.현재 칸의 거리 + 1을 다음 칸의 거리로 저장한다.BFS는 먼저 방문한 경로가 곧 최단 거리이므로 별도의 최단 거리 비교 없이도 정확한 값이 저장된다.결과 배열 ret은 -1로 초기화하여 도달하지 못한 칸을 구분..

문제[C++] 백준 18111: 마인크래프트 SILVER 2https://www.acmicpc.net/problem/18111 접근 방법이 문제는 땅의 모든 칸을 같은 높이 i로 평탄화할 때 걸리는 최소 시간과 그때의 높이를 구하는 문제다. 핵심 아이디어는 다음과 같다.목표 높이 i는 0 ~ 256 전부 후보다.현재 맵에 “i 높이 칸이 0개”라도 그 높이로 평탄화하는 게 최적일 수 있다.각 후보 높이 i에 대해,높이가 더 높은 칸(j > i)은 블록을 제거해야 하고 (1개당 2초)높이가 더 낮은 칸(j 블록을 설치해야 한다 (1개당 1초)제거하면 블록이 인벤토리에 들어오므로, 최종적으로 인벤토리 블록이 음수가 되면 그 높이는 불가능하다.(인벤토리 블록이 음수라는 것은, 갖고 있는 블록보다 오바해서 사..

문제[C++] 백준 21736: 헌내기는 친구가 필요해 SILVER 2https://www.acmicpc.net/problem/21736 접근 방법이 문제는 캠퍼스 지도가 주어졌을 때, 도연이(I)가 있는 위치에서 출발하여 벽(X)을 제외한 모든 경로를 탐색하면서 사람(P)의 수를 세는 문제다. 캠퍼스는 2차원 격자 형태이므로, 상·하·좌·우로 이동하면서 탐색하는 그래프 탐색 문제로 볼 수 있고,한 번 방문한 곳을 다시 방문하지 않기 위해 visited 배열을 사용한 DFS(깊이 우선 탐색) 로 해결했다. 풀이 흐름은 다음과 같다.캠퍼스 정보를 2차원 배열에 저장하면서, 도연이의 시작 위치(I)를 찾는다.시작 위치에서 DFS를 시작한다.이동할 수 있는 조건은캠퍼스 범위 안에 있고아직 방문하지 않았으며벽..

문제[C++] 백준 11279: 최대 힙 SILVER 2https://www.acmicpc.net/problem/11279 접근 방법이 문제는 최대 힙(Max Heap)을 직접 구현하는 대신,C++의 priority_queue를 이용해 처리하는 전형적인 자료구조 문제다. 문제의 규칙은 간단하다.입력값 x가 0이 아니면 → 자료구조에 값을 넣고입력값 x가 0이면비어 있으면 0 출력비어 있지 않으면 가장 큰 값을 출력하고 제거C++의 priority_queue는 기본적으로 가장 큰 값이 top에 오는 최대 힙 구조이기 때문에 문제 조건과 정확히 일치한다.따라서 별도의 힙 구현 없이 입력에 따라 push, top, pop만 사용하면 된다. 구현 시 주의할 점priority_queue는 기본이 내림차순(최대 ..

문제[C++] 백준 9375: 패션왕 신해빈 SILVER 3https://www.acmicpc.net/problem/9375 접근 방법이 문제는 옷의 이름은 필요 없고, 종류(type)별로 몇 개 있는지만 알면 되는 경우의 수 문제다.입력으로 (옷 이름, 옷 종류)가 들어오지만, 실제로 필요한 건 “종류별 개수”이기 때문에map을 사용해서 아래와 같이 저장했다.key : 옷의 종류value: 그 종류에 속하는 옷의 개수예를 들어, 아래와 같다면 각 종류별 선택지는 다음과 같다.headgear 2개eyewear 1개headgear: (안 씀) + 2개 중 하나 = 3가지eyewear: (안 씀) + 1개 중 하나 = 2가지따라서, 전체 경우의 수는 3 * 2 = 6이 된다.이를 일반화하면, 각 종류마다 ..