승코딩당당당

문제[C++] 백준 1927: 최소 힙 SILVER 2https://www.acmicpc.net/problem/1927 접근 방법이 문제는 수를 입력받아 최소값을 빠르게 출력하고 제거해야 하는 문제이다. 일반적인 배열이나 벡터를 사용하면 매번 정렬이 필요해 비효율적이므로,우선순위 큐(priority_queue) 를 사용하는 것이 적절하다. C++의 priority_queue는 기본적으로 최대 힙(max heap) 구조이지만,비교 함수를 변경하면 최소 힙(min heap) 으로 사용할 수 있다.priority_queue heap; // 최대 힙priority_queue, greater> heap; // 최소 힙 int : 저장할 자료형vector : 내부 컨테이너greater : 작은 값이 우선되도록..

문제[C++] 백준 2292: 벌집 BRONZE 2https://www.acmicpc.net/problem/2292 접근 방법이 문제는 벌집 모양으로 숫자가 증가할 때,주어진 숫자 n이 몇 번째 껍질(층) 에 속하는지를 구하는 문제이다. 먼저 직접 숫자들의 범위를 나열해보면 다음과 같은 규칙을 확인할 수 있다.12 ~ 78 ~ 1920 ~ 3738 ~ 61 각 층이 커질수록 증가하는 칸의 개수는 6의 배수로 증가한다는 패턴이 있다.16 1218241층: 12층: 1 + 6×13층: 1 + 6×1 + 6×24층: 1 + 6×1 + 6×2 + 6×3 …즉, 이런 방식으로 이전 범위의 끝값에 6 × i를 더해가며 범위를 확장하면 된다. 코드에서는 각 층의 마지막 숫자를 벡터에 저장하고 n이 해당 범위 안에 ..

문제[C++] 백준 5073: 삼각형과 세 변 BRONZE 3https://www.acmicpc.net/problem/5073 접근 방법이 문제는 세 변의 길이가 주어졌을 때 해당 삼각형이 유효한지, 그리고 어떤 삼각형 종류인지 판별하는 문제이다. 먼저 세 변을 배열에 저장한 뒤 오름차순으로 정렬한다.정렬을 하면 가장 긴 변이 항상 마지막에 위치하므로, 삼각형의 성립 조건을 간단하게 확인할 수 있다. 정렬 후,가장 긴 변 ≥ 나머지 두 변의 합 → Invalid세 변이 모두 같으면 → Equilateral세 변이 모두 다르면 → Scalene위 두 경우가 아니면 → Isosceles와 같은 순서로 판별한다. 구현 시 주의할 점sort 함수를 배열에 사용할 때는sort(배열, 배열 + 원소 개수) 형태로..

문제[C++] 백준 23971: ZOAC 4 BRONZE 3https://www.acmicpc.net/problem/23971 접근 방법이 문제는 강의실의 크기와 거리 제한이 주어졌을 때 사람을 최대로 배치할 수 있는 개수를 구하는 문제이다. 처음에는 2차원 벡터를 선언한 뒤,사람을 앉힐 수 있는 위치에만 표시하면서 하나씩 카운팅하는 방식으로 접근했다.하지만 이 방법은 불필요한 반복이 많아 시간 초과로 계속 실패했다. 곰곰이 생각해보니 굳이 모든 좌석을 직접 확인할 필요가 없었고,행과 열 각각에서 앉을 수 있는 개수를 공식으로 계산하면 되는 문제였다. 세로 방향에서는 (n+1)칸마다 한 명,가로 방향에서는 (m+1)칸마다 한 명씩 앉을 수 있으므로각각 ceil(h / (n+1)), ceil(w / (m..

문제[C++] 백준 1253: 좋다 GOLD 4https://www.acmicpc.net/problem/1253 접근 방법이 문제는 주어진 수열에서 어떤 수가 다른 두 수의 합으로 표현될 수 있는지를 판단하는 문제이다. 모든 수에 대해 두 수의 합을 일일이 비교하면 시간 초과가 발생할 수 있으므로,수열을 정렬한 뒤 투 포인터(Two Pointer) 기법을 사용한다. 각 원소 vect[i]를 목표 값으로 두고, 양쪽 끝에서 시작하는 두 포인터를 이동시키며vect[start] + vect[end]가 목표 값과 같은지 확인한다. 구현 시 주의할 점투 포인터를 사용하려면 반드시 수열을 정렬해야 한다. 두 수의 합을 구할 때 현재 찾고 있는 수(vect[i])가 덧셈에 포함되면 안 되므로, start == i ..

문제[C++] 백준 1260: DFS와 BFS SILVER 2https://www.acmicpc.net/problem/1260 접근 방법이 문제는 그래프가 주어졌을 때, 시작 정점 v에서부터 DFS와 BFS를 각각 수행한 결과를 출력하는 문제이다.정점과 간선의 관계를 그래프로 표현하면 아래와 같다.정점 → 노드(Node)간선 → 노드 간의 연결 관계그래프는 무방향 그래프이므로, 간선 정보 (x, y)가 주어지면 x → y, y → x 양방향으로 모두 연결해야 한다.DFS는 재귀를 이용해 구현하고, BFS는 큐(queue)를 이용해 구현한다. 구현 시 주의할 점방문 가능한 정점이 여러 개일 경우 번호가 작은 정점부터 방문해야 하므로 각 정점의 인접 리스트를 오름차순으로 정렬해야 한다. 정점 번호는 1 ~..

문제[C++] 백준 2164: 카드2 SILVER 4https://www.acmicpc.net/problem/2164 접근 방법이 문제는 카드가 놓인 상태에서 맨 위 카드를 버리고, 그 다음 카드를 맨 아래로 옮기는 과정을 반복하여마지막에 남는 카드의 번호를 구하는 문제이다.이러한 동작은 선입선출(FIFO) 구조와 정확히 일치하므로 queue 자료구조를 사용하면 문제를 직관적으로 해결할 수 있다.카드는 항상 앞에서 제거(pop) 되고일부 카드는 뒤로 추가(push) 된다 코드#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n ..

문제[C++] 백준 2644: 촌수계산 SILVER 2https://www.acmicpc.net/problem/2644 접근 방법이 문제는 사람 사이의 촌수(거리) 를 구하는 문제로,가족 관계를 그래프로 표현한 뒤 두 정점 사이의 거리를 탐색하면 된다.사람 → 정점(Node)부모–자식 관계 → 간선(Edge)결국 시작 노드(s)에서 목표 노드(e)까지의 최단 거리를 구하는 문제이므로 DFS 또는 BFS를 사용할 수 있으며,이번 풀이에서는 DFS를 이용하였다.가장 중요했던 점은 가족 관계가 방향 그래프가 아니라 무방향 그래프라는 것이다.처음에는 부모 → 자식 방향으로만 생각했지만, 촌수는 위아래 개념이 아니라 사람 사이의 거리 개념이기 때문에 부모와 자식은 서로 오갈 수 있어야 한다.DFS 탐색 시에는 ..