문제 문제 바로가기> BOJ 9466번: 텀 프로젝트 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 dfs 를 이용하여 팀을 이루는 학생들을 구하고, 이를 전체 학생 수에서 빼주는 방식으로 문제를 풀었다. N이 최대 100,000이므로, 방문했던 cycle을 재방문하는 것을 피해야한다. 이를 위해 방문을 시작하고 중간에 cycle이 이루어졌더라도 해당 cycle을 구해주기 위해 cnt 배열을 이용해주었다. #include #include #define MAX 100005 using namespace std;..

문제 문제 바로가기> BOJ 2617번: 구슬 찾기 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 dfs를 이용하여 중간 크기의 구슬이 될 수 없는 경우를 체크해주었다. #include #include #include #define MAX 100 using namespace std; int N, M; bool visited[MAX]; set fs[MAX], rs[MAX]; void input(){ cin >> N >> M; int a, b; for (int i = 0; i < M; i..

문제 문제 바로가기> BOJ 20040번: 사이클 게임 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 union-find를 이용하여 cycle을 찾아주었다. #include #define MAX 500005 using namespace std; int N, M; int par[MAX]; int find_(int x){ if(par[x] == x) return x; return par[x] = find_(par[x]); } int union_(int y, int x){ int py = find_(y)..

문제 문제 바로가기> BOJ 3020번: 개똥벌레 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 각각의 높이(h)로 날 때, 파괴하게 되는 장애물 수를 이분탐색을 이용해서 구해주었다. 석순, 종유석으로 나눠 하면서 이상한 부분에서 너무 헷갈렸다 ................ #include #include #include using namespace std; int N, H; vector up, down; // 석순, 종유석 void input(){ cin >> N >> H; for (int i = 0; ..

문제 문제 바로가기> BOJ 16947번: 서울 지하철 2호선 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 1. dfs를 이용해 cycle을 구해준다. 이전 노드가 아닌, 다른 노드에서 방문한 노드를 재방문 하는 경우, cycle이라고 볼 수 있다! 2. bfs를 이용해 역과 순환선 사이의 거리를 구해준다! #include #include #include #include #define MAX 3005 using namespace std; struct QUEUE{ int n, ..

문제문제 바로가기> BOJ 5719번: 거의 최단 경로 5719번: 거의 최단 경로입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있www.acmicpc.net 풀이다익스트라를 돌리고, 역방향 그래프를 만들어서 bfs 탐색을 진행하면, 해당 경로가 최단 경로인지 판별이 가능하다.예를 들어 a -> b 인 경우, 역 방향 그래프에서 a까지의 최단 경로 + a에서 b로이어지는 간선 = b까지의 최단 경로라면, 해당 간선은 최단 경로에 포함된다.이를 이용하여 최단 경로를 INF 로 변경 (사실상 제거) 해주었고, 최단 경로가 제거된 상태에서 다..

문제 문제 바로가기> BOJ 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 동생을 찾는 가장 빠른 시간이므로 bfs를 이용하였고, 가중치가 같지 않은 경우(걸음과 순간이동은 시간 당 이동할 수 있는 칸 수가 다름)에 속하므로 더 빠르게 찾을 수 있는 경우 큐에 다시 한번 넣어 주었다. #include #include #define MAX 100001 using namespace std; int N, K; int cost[MAX]; void ..

문제 문제 바로가기> BOJ 1938번: 통나무 옮기기 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 풀이 최소 동작 횟수를 구하는 것이기 때문에 bfs를 이용했다. 또한 한 지점에서 통나무의 모양이 ㅡ(가로) 또는 ㅣ(세로) 일 수 있기 때문에 visited 배열을 3차원으로 선언해주었다! 코드가 지저분해서,, 언제 한번 다시 깔끔하게 짜보아야겠다 ,, #include #include #define MAX 55 #define SIZE 3 using namespace std; stru..

문제 문제 바로가기> BOJ 1005번: ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 건물을 지을 때, 건설 순서 규칙이 존재하므로, 위상정렬을 이용해 문제를 풀었다. 내가 지어지기 이전에 지어져야 하는 건물들 중 가장 오랜 시간이 걸리는 건물 + 내가 지어지는 데 걸리는 시간이 정답이다. #include #include #include #define MAX 1005 using namespace std; int N; // 건물의 개수 int K; // 건물간의 건설순서 규칙의 ..

문제 문제 바로가기> BOJ 1477번: 휴게소 세우기 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 풀이 M개의 휴게소를 가능한 빈 공간에 모두 세워보는 조합 방식으로는 너무 많은 경우의 수가 있다. 따라서 입력 받은 위치를 정렬하고, "각 휴게소 간 거리 중 최대값"으로 이분 탐색하여 문제를 해결하였다. ( + 거리이기 때문에 low 값을 0이 아닌 1로 설정하였다.) 문제를 풀기 전에 "예제 입력 1"을 손으로 그려보고 문제를 푸니, 문제를 금방 풀 수 있었던 거 같다. 문제를 이해하고, ..

문제 문제 바로가기> BOJ 2933번: 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 옛날에 풀다가 때려쳤었는데,, 오랜만에 싹 지우고 다시 풀어봤다! 중력을 작용시키는 클러스터를 찾는 부분, 중력을 처리하는 부분만 주의해주면 된다! 클러스터가 지면에 닿아있지 않다면, 중력이 작용하는 클러스터이다! #include #include #include #define MAX 101 using namespace std; struct POS{int y, x;}; vector cluster; int R, C, N; ch..

문제 문제 바로가기> BOJ 2812번: 크게 만들기 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 큰 수를 만났을 때, 현재 수보다 작은 수가 앞에 있다면 해당 수를 지우기 위해 스택을 이용하였다! #include #include using namespace std; int N, K; string str; deque s; void input(){ cin >> N >> K; cin >> str; } void solve(){ // 숫자 K개를 지워서 얻을 수 있는 가장 큰 수 for(char c : str){ while(!s.empty() && s.back()

문제 문제 바로가기> BOJ 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택을 이용하여 O(N)만에 정답을 구할 수 있다. 낮아지는 경우와 높아지는 경우로 구분하고, 낮아지는 경우에 pop한 idx를 현재 높이와 함께 다시 스택에 넣어주는 부분이 핵심인듯 하다!! #include #include #define MAX 100005 using namespace std; struct DATA{int id..

문제 문제 바로가기> BOJ 8980번: 택배 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 도착지를 기준으로 오름차순 정렬하여, 현재 보낼 수 있는 양의 최대치를 구 방식으로 문제를 풀었다! 그리디는 진짜 ,, 생각해내기가 쉽지 않다 ,, #include #include #include #define MAX 2001 using namespace std; struct PARCEL { int s, e, c; bool operator < (const PARCEL &p) const { i..

문제 문제 바로가기> BOJ 1963번: 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 두 소수 사이의 변환에 필요한 최소 회수를 구하는 것이므로 bfs를 이용하여 문제를 해결해주었다. #include #include #include #define MAX 10000 using namespace std; struct DATA{int num, cnt;}; int arr[4]; bool visited[MAX]; bool notPrime[MAX]; void eratosthenes(){ for (int a=2..