목록알고리즘/C++ (56)

수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 2468 안전 영역

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net dfs 를 사용하여 문제를 해결하였습니다. 최대 높이 maxH 측정 높이 0 부터 maxH 까지 각 경우를 고려 visited 배열을 ..
알고리즘/C++ 2019. 10. 31. 15:02
[C++] BAEKJOON 5212 지구 온난화

https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 문제 푸르고 아름다운 남해에는 많은 섬이 장관을 이루고 있다. 그림이 아니면 볼 수 없을 것 같은 아름다운 장관을 실제로 볼 수 있는 다도해로 상근이는 여행을 떠났다. 다도해에 도착한 상근이는 서울에서 보던 것과는 다른 풍경에 큰 충격을 받았다. 지구 온난화로 인해 해수면이 상승해 섬의 일부가 바다에 잠겨버렸다. 서울로 다시 돌아온 상근이는 이렇게 지구 온난화가 계속 될 경우 남해의 지도는 어떻게 바뀔지 궁금해졌다. 다도해의 지도는 R*C 크기의 그리드로 www.acmicpc.net 지도의 범위를 벗어나는 칸도 바다로 치기 때문에 바다와 땅을 저장할 배열에 대해서 상하좌우 한 칸씩 더 바다로 만들어주었습니다. 3,..
알고리즘/C++ 2019. 10. 29. 23:23
[C++] BAEKJOON 2246 콘도 선정

https://www.acmicpc.net/problem/2246 2246번: 콘도 선정 문제 콘도를 선정할 때에는 가급적이면 싸고 바닷가에 가까운 곳으로 하려 한다. 이를 위해 우선 적당한 콘도 몇 곳을 후보로 선정하려 하는데, 다음 두 조건을 만족하는 콘도 X가 후보가 된다. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다. 각 콘도의 바닷가에서의 거리와 숙박비에 대한 정보가 주어졌을 때, 후보 콘도의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄 www.acmicpc.net #include #include #include using namespace std; int main(int argc, const ch..
알고리즘/C++ 2019. 10. 29. 22:03
[C++] BAEKJOON 4949 균형잡힌 세상

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다. 모든 왼쪽 대괄호("[")는 오른쪽 대 www.acmicpc.net 일반적으로 스택를 써서 올바른 괄호를 체크하는 문제에서 괄호의 종류를 늘려 약간의 응용이 필요한 문제였습니다. 입력 string s..
알고리즘/C++ 2019. 10. 5. 01:56
[C++] BAEKJOON 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net dfs 를 이용해서 문제를 해결하였습니다. arr 배열을 만들어서 i 노드와 j 노드가 연결되었다면 양방향으로 올 수 있으므로 arr[i][j] 와 arr[j][i] 의 값에 1을 넣어주었습니다. 그리고 visited 배열을 만들어서 해당 노드를 순회한 적이 있는지 없는지 유무를 확인해주었습니다. 다른 노드로 건나가기 위해서는 ..
알고리즘/C++ 2019. 10. 2. 00:31
[C++] BAEKJOON 1012 유기농 배추

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net dfs 를 이용해서 구현하였습니다. K 번 만큼 받은 좌표를 통해 board 를 완성한 후, 연결되는 구간이 몇 개인지 세주는 문제였..
알고리즘/C++ 2019. 10. 1. 23:57
[C++] BAEKJOON 2667 단지번호붙이기

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net dfs 를 이용해서 구현하였습니다. BAEKJOON 2583 영역 구하기 문제와 동일한 풀이로 해결할 수 있습니다. #include #include #include..
알고리즘/C++ 2019. 10. 1. 23:15
[C++] BAEKJOON 2583 영역 구하기

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net dfs 를 이용해서 구현하였습니다. board 배열에서 가지 못하는 부분과 이미 간 부분을 1로 체크함으로서 visited 배열을 한 번에 표현할 수..
알고리즘/C++ 2019. 10. 1. 20:15
[C++] BAEKJOON 16282 Black Chain

https://www.acmicpc.net/problem/16282 16282번: Black Chain 문제 n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어야 하는데, 고리를 푸는데 힘이 들어 최소 개의 고리만 풀기를 원한다. 예를 들어 아래의 그림 A.1 처럼 7 개의 고리로 구성된 블랙 체인이 있다고 하자. 이 체인에서 3 번 고리 하나를 풀어 내면 그림 A.2 처럼 3 번 고리 1 개와 두 개의 체인 www.acmicpc.net 체인의 길이에 대해서 풀어야 할 고리의 최소 개수를 구하다보니 규칙을 찾을 수 있었습니다. 한 개의 고리를 끊을 경우 우..
알고리즘/C++ 2019. 9. 29. 19:42
[C++] BAEKJOON 16283 Farm

https://www.acmicpc.net/problem/16283 16283번: Farm 문제 목장 주인인 상배는 양과 염소들을 같이 기르고 있다. 기르는 양과 염소는 각각 한 마리 이상이다. 양과 염소는 같은 사료를 먹고, 양 한 마리는 하루에 사료를 정확히 a 그램 먹고, 염소 한 마리는 하루에 정확히 b 그램을 먹는다고 한다. 상배는 매일 아침 양과 염소가 각각 몇 마리인지를 확인하는 작업을 한다. 양과 염소가 각각 몇 마리인지 확인할 때, 양과 염소들이 돌아 다녀서 정확하게 그 수를 구하는 것이 쉽지 않았다. 대신에 양과 염소가 전체 www.acmicpc.net 반복문을 통해서 연립방정식의 해가 만족하는 경우를 찾아줍니다. 이 경우가 1개일 경우, 정답을 출력하고 0개 이거나 2개 이상이면 문제..
알고리즘/C++ 2019. 9. 29. 16:05
Prev 1 2 3 4 5 6 Next

티스토리툴바