승코딩당당당

문제[C++] 백준 1991: 트리 순회 SILVER 1https://www.acmicpc.net/problem/1991 접근 방법백준 1991번은 이진 트리의 전위, 중위, 후위 순회 결과를 출력하는 문제다. 각 노드는 대문자 알파벳으로 표현되고, 입력으로 (부모, 왼쪽 자식, 오른쪽 자식) 형태가 주어진다.자식이 없는 경우는 '.'로 표시된다. 이 문제의 핵심은:트리를 직접 구성하고재귀를 이용해 3가지 순회 방식을 구현하는 것트리의 노드는 최대 26개(알파벳 A~Z)이므로 배열을 이용해 간단히 표현할 수 있다. 처음에 DFS로 푸는 문제라고 생각하여 DFS로 전위순회를 구현했지만 중위순회부터 막혔다..ㅠㅠ다른 사람들이 푼 걸 보니 너무 간단하게 푸는 문제여서 현타MAX.... 아래 블로그를 참고하였..

문제[C++] 백준 16953: A → B SILVER 2https://www.acmicpc.net/problem/16953 접근 방법백준 16953번은 정수 A를 B로 바꾸는 최소 연산 횟수를 구하는 문제다.사용할 수 있는 연산은 두 가지뿐이다.현재 값 × 2현재 값 뒤에 1을 붙이기 (예: 23 → 231)이 문제는 연산이 두 갈래로 계속 뻗어나가는 구조이기 때문에 그래프 탐색 문제로 볼 수 있다. 각 숫자를 하나의 노드라고 생각하면,val → val * 2val → val * 10 + 1이렇게 두 개의 간선이 존재하는 셈이다.최소 연산 횟수를 구해야 하므로 BFS(너비 우선 탐색) 을 사용했다. 상세 아이디어1. BFS로 최소 횟수 탐색queue> Q;Q.push(make_pair(a, 1)); ..

문제[C++] 백준 1764: 듣보잡 SILVER 4https://www.acmicpc.net/problem/1764 접근 방법이 문제는 듣도 못한 사람 N명 + 보도 못한 사람 M명이 주어졌을 때, 두 목록에 모두 속하는 사람(= 듣보잡) 을 찾는 문제다. 즉, 간단히 말하면문자열 집합 A와 집합 B의 교집합을 구한 뒤, 그 결과를 사전 순으로 정렬해서 출력하는 문제. 풀이 아이디어는 이렇게 잡았다.먼저 듣도 못한 사람 N명을 입력받으면서 map who에 이름을 저장한다.이름을 key, 값을 1로 저장 → 존재 여부 체크용다음으로 보도 못한 사람 M명을 입력받으면서who[str] == 1이면 듣도 보도 못한 사람이므로 ret 벡터에 push.ret에 모아둔 이름들을 sort로 사전 순 정렬한 뒤,개수..

문제[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초)제거하면 블록이 인벤토리에 들어오므로, 최종적으로 인벤토리 블록이 음수가 되면 그 높이는 불가능하다.(인벤토리 블록이 음수라는 것은, 갖고 있는 블록보다 오바해서 사..