본문 바로가기

분류 전체보기170

1927 : 최소 힙 (C++) 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 앞의 문제인 최대 힙과 반대되는 문제로 루트노드에 가장 작은 값이 위치해야 한다. #include #include using namespace std; /* 왼쪽 자식 노드 = 부모 노드 * 2 + 1 오른쪽 자식 노드 = 부모 노드 * 2 + 2 부모 노드 = 현재 노드 - 1 / 2 */ vector heap; void push(int data) { int i = heap.size(); heap.push_back(data); while(i.. 2021. 2. 24.
11279 : 최대 힙 (C++) 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 우선순위 큐를 공부하기 위해 최대 힙을 공부했다. clude #include using namespace std; vector v; /* 왼쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 2 부모 인덱스 = 자신 인덱스 - 1 / 2 */ void push(int data) { int i = v.size(); v.push_back(data); while(i != 0 && v[i] > v[(i-1).. 2021. 2. 24.
2638 : 치즈 (C++) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 놀랍게도 앞에 글과 이름은 같지만 번호는 다른 문제이다! 앞에 치즈 문제와는 다르게 이번 치즈문제는 공기와 접촉한 변이 2개 이상 일 때만 녹는다! 이에 초점을 맞추고 문제를 해결하였다. #include #include #include using namespace std; int N, M, hours; int counting = 1; int map[100][100]; bool visit[100][100]; int dx[4] = {1, -1, 0, 0};.. 2021. 2. 22.
2636 : 치즈 (C++) 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 치즈문제! BFS로 풀었다 먼저 BFS탐색을 통해 공기로 차있는 부분들을 방문표시한다. 정사각형 칸의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다고 했으므로 항상 map[0][0]부분은 공기 부분이므로 queue에 0,0을 넣고 공기인 부분을 탐색한 후 치즈를 녹인다. 치즈가 모두 남아있지 않을 때까지 계속 수행한다. 또한 치즈가 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여있는 칸의 수를 구하라 했으므로 치즈를 녹이기 전 항상 치즈조각이 남아있는 갯수를 세준 후 탐색을.. 2021. 2. 22.
14502 : 연구소 (C++) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 6중 for문...! 을 사용해서 문제를 해결했다! 수영장에서 일하면서 문제를 어떻게 해결할지 생각하고 쉬는시간인 지금에 문제를 잘 풀었다. 못 풀것 같았는데 맞았습니다가 떠서 기분이 좋다 희희 #include #include #include using namespace std; int N, M; int maximum = 0; int map[8][8]; int temp[8][8]; bool visit[8][8]; int dx[4] = {1, -1, 0, 0}; int dy[4.. 2021. 2. 20.
13305 : 주유소 (C++) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 알고리즘으로 해결한 문제이다. 처음에 조금 헷갈려서 문제를 이해하고 푸는데 좀 시간이 걸렸다. 반성하자. #include #define ll long long int using namespace std; // 거리와 가격이 최대 1,000,000,000이하로 // 들어옴으로 int로는 계산이 불가능 하다. ll total = 0; ll mini = 1000000001; int main() { int N; cin >> N; ll distance.. 2021. 2. 19.
2573 : 빙산 (C++) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 좀 코드가 긴 것 같긴하지만 열심히 잘 풀었따! #include #include #include using namespace std; int N, M, years; int map[300][300]; bool visit[300][300]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; queue q; void bfs(int i, int j) { visit[i][j] = true; q.push({i, j}); .. 2021. 2. 18.
2579 : 계단 오르기 (C++) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 오랜만에 다이내믹 프로구래밍을 풀어보았따... 다른공부도 해야하는데 맨날 백준만 잡고있다니... #include using namespace std; int arr[301]; int dp[301]; /* 문제 접근 방법 : n번째 계단을 밟는 경우는 두가지 방법 밖에없다 1. n번째를 밟고 n-2번째 계단을 밟는 경우 2. n번째를 밟고, n-1번째와 n-3번째를 밟는 경우 문제에 나온 예로 6번째 계단을 밟는 경우에는 4번째 계단을 밟는 경우와 5, 3번째 계단을 밟는 경.. 2021. 2. 18.
20551 : Sort 마스터 배지훈의 후계자 (C++) 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net lower_bound 함수를 참조해서 만든 함수로 푼 문제이다. #include #include using namespace std; int grayLower_bound(int* arr, int N, int temp) { int left = 0; int right = N; int cnt = 0; // 탐색하려는 수가 없을 때 -1을 리턴하기 위해 카운트 변수 선언 int mid; while(left < right) { mid = (left .. 2021. 2. 18.

티스토리툴바