'IT/알고리즘' 카테고리의 글 목록 (20 Page)

IT/알고리즘

BOJ 백준온라인져지 11375 열혈강호 풀이 2018.01.23
BOJ 백준온라인져지 14502 연구소 풀이 2018.01.14
BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 2018.01.13
BOJ 백준온라인져지 1261 알고스팟 풀이 Raw 2018.01.11
BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 2018.01.09
BOJ 백준온라인져지 1918 후위표기식 풀이 2018.01.07
BOJ 백준온라인져지 1655 가운데를 말해요 풀이 2018.01.06
BOJ 백준온라인져지 1715 카드 정렬하기 풀이 2018.01.04
BOJ 백준온라인져지 11286 절대값 힙 풀이 2018.01.02
BOJ 백준온라인져지 11279 최대 힙 풀이 2017.12.30 1

BOJ 백준온라인져지 11375 열혈강호 풀이

2018. 1. 23. 22:49

이분 매칭 문제를 엄청 오랜만에 풀어봤다.

https://en.wikipedia.org/wiki/Matching_(graph_theory)

http://koosaga.com/18

http://1ambda.github.io/algorithm/algorithm-part2-5/

위 링크에 많은 설명이 있고, 읽지는 않았다.

이 문제를 풀이한 방법은 아주 기초적인 DFS 를 이용한 O(V * E) 이다.

오늘은 시간이 없어서 이론보다는 구현을 목적으로 공부했다.

풀이 방법

1. 사람을 한명씩 dfs 로 연결할 수 있는 일을 잡는다.

2. 이미 연결돼있는 선이라면 그 선에 연결된 사람이 다른 일을 잡을 수 있는지 확인한다.

3. 반복

4. 끝

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/11375
	* BOJ 백준온라인져지 11375 열혈강호 풀이
	*/
	using namespace std;
	vector<vector<int> > adj;
	vector<int> match;
	vector<bool> visited;
	int workCount;
	bool dfs (int here) {
	if (visited[here]) return false;
	visited[here] = true;
	for (int there = 1; there <= workCount; there++) {
	if (adj[here][there]) {
	if (match[there] == -1 \|\| dfs(match[there])) {
	match[there] = here;
	return true;
	}
	}
	}
	return false;
	}
	int main () {
	int personCount;
	scanf("%d%d", &personCount, &workCount);
	adj.resize(personCount + 1);
	for (int i = 1; i <= personCount; i++) {
	adj[i].resize(workCount + 1);
	int length;
	scanf("%d", &length);
	for (int j = 0; j < length; j++) {
	int work;
	scanf("%d", &work);
	adj[i][work] = 1;
	}
	}
	int result = 0;
	match = vector<int>(workCount + 1, -1);
	for (int i = 1; i <= personCount; i++) {
	visited = vector<bool>(personCount + 1, false);
	if (dfs(i)) result++;
	}
	printf("%d", result);
	}

view raw BOJ_11375.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11376 열혈강호 2 풀이 (0)	2018.01.27
BOJ 백준온라인져지 2822 점수 계산 풀이 (0)	2018.01.25
BOJ 백준온라인져지 14502 연구소 풀이 (0)	2018.01.14
BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0)	2018.01.13
BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0)	2018.01.11

BOJ 백준온라인져지 14502 연구소 풀이

2018. 1. 14. 15:10

기둥 세우는 부분을 어떻게 처리할까 고민을 했다.

1. forloop

2. recursive 한 방법

2번은 뭔가 생각을 더 해줘야 될거같아서 귀찮았다.

그래서 1번을 선택함.

1. 정렬하는거 처럼 forloop 을 작성해주고 기둥을 세워준다음, 맵을 복사

2. BFS 로 세균 옮기기

3. 안전한 부분 확인

1 -> 2 -> 3 -> 1

쭉 반복해주고,

최댓값을 출력하면 끝

	#include <cstdio>
	#include <queue>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/14502
	* BOJ 백준온라인져지 14502 연구소 풀이
	*/
	using namespace std;
	int xxxx[] = {0, 1, 0, -1};
	int yyyy[] = {-1, 0, 1, 0};
	vector<pair<int, int> > virusZone;
	int row, col, result = 0;
	int bfs (int **map) {
	bool *visited = new bool[row];
	for (int i = 0; i < row; i++) {
	visited[i] = new bool[col];
	for (int j = 0; j < col; j++) {
	visited[i][j] = false;
	}
	}

	queue<pair<int, int> > q;
	for (int i = 0; i < virusZone.size(); i++) {
	q.push(virusZone[i]);
	}

	while (q.size()) {
	int x = q.front().first; int y = q.front().second; q.pop();
	visited[x][y] = true;
	map[x][y] = 2;
	for (int i = 0; i < 4; i++) {
	int nx = x + xxxx[i]; int ny = y + yyyy[i];
	if (nx < 0 \|\| ny < 0 \|\| nx >= row \|\| ny >= col \|\| visited[nx][ny] \|\| map[nx][ny]) continue;
	q.push(make_pair(nx, ny));
	}
	}

	int tempSafetyZone = 0;
	for (int i = 0; i < row; i++) {
	for (int j = 0; j < col; j++) {
	if (map[i][j] == 0) {
	tempSafetyZone++;
	}
	}
	}
	return tempSafetyZone;
	}
	int main () {
	scanf("%d%d", &row, &col);
	int *map = new int[row];
	vector<pair<int, int> > safetyZone;
	for (int i = 0; i < row; i++) {
	map[i] = new int[col];
	for (int j = 0; j < col; j++) {
	scanf("%d", &map[i][j]);
	if (map[i][j] == 0) safetyZone.push_back(make_pair(i, j));
	else if (map[i][j] == 2) virusZone.push_back(make_pair(i, j));
	}
	}

	for (int i = 0; i < safetyZone.size() - 2; i++) {
	for (int j = i + 1; j < safetyZone.size() - 1; j++) {
	for (int k = j + 1; k < safetyZone.size(); k++) {
	int *tempMap = new int[row];
	for (int ii = 0; ii < row; ii++) {
	tempMap[ii] = new int[col];
	for (int jj = 0; jj < col; jj++) {
	tempMap[ii][jj] = map[ii][jj];
	}
	}
	tempMap[safetyZone[i].first][safetyZone[i].second] = 1;
	tempMap[safetyZone[j].first][safetyZone[j].second] = 1;
	tempMap[safetyZone[k].first][safetyZone[k].second] = 1;
	int tempResult = bfs(tempMap);
	if (result < tempResult) {
	result = tempResult;
	}
	}
	}
	}
	printf("%d", result);
	}

view raw BOJ_14502.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2822 점수 계산 풀이 (0)	2018.01.25
BOJ 백준온라인져지 11375 열혈강호 풀이 (0)	2018.01.23
BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0)	2018.01.13
BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0)	2018.01.11
BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0)	2018.01.09

BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이

2018. 1. 13. 23:29

알고스팟 문제와 동일해서 쉽게 풀었다.

달라진 점이라면 시작점이 0이 아니라는것과 test case 가 여러개라는것

struct node {
    int x, y, w;
    node (int x, int y, int w): x(x), y(y), w(w) {}
    bool operator < (node other) const {
        return w > other.w;
    }
};

이 부분만 잘 기억해야겠다.

	#include <cstdio>
	#include <queue>
	#include <string.h>
	/**
	* https://www.acmicpc.net/problem/4485
	* BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이
	*/
	using namespace std;
	int xxxx[] = {0, 1, 0, -1};
	int yyyy[] = {-1, 0, 1, 0};
	struct node {
	int x, y, w;
	node (int x, int y, int w): x(x), y(y), w(w) {}
	bool operator < (node other) const {
	return w > other.w;
	}
	};
	int main () {
	for (int z = 1;; z++) {
	int size;
	scanf("%d", &size);
	if (size == 0) break;
	int row = size, col = size;
	bool visited[row][col];
	int map[row][col];
	for (int i = 0; i < row; i++) {
	for (int j = 0; j < col; j++) {
	scanf("%d", &map[i][j]);
	}
	}
	memset(visited, 0, sizeof(visited));
	priority_queue<node> pq;
	pq.push(node(0, 0, map[0][0]));
	while(pq.size()) {
	node n = pq.top(); pq.pop();

	int cx = n.x; int cy = n.y; int cw = n.w;
	if (cx == row - 1 && cy == col - 1) {
	printf("Problem %d: %d\n", z, cw);
	break;
	}
	visited[cx][cy] = true;
	for (int i = 0; i < 4; i++) {
	int nx = cx + xxxx[i]; int ny = cy + yyyy[i];
	if (visited[nx][ny] \|\| nx < 0 \|\| ny < 0 \|\| nx >= row \|\| ny >= col) continue;
	int nw = cw + map[nx][ny];
	pq.push(node(nx, ny, nw));
	}
	}
	}
	}

view raw BOJ_4485.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11375 열혈강호 풀이 (0)	2018.01.23
BOJ 백준온라인져지 14502 연구소 풀이 (0)	2018.01.14
BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0)	2018.01.11
BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0)	2018.01.09
BOJ 백준온라인져지 1918 후위표기식 풀이 (0)	2018.01.07

BOJ 백준온라인져지 1261 알고스팟 풀이 Raw

2018. 1. 11. 22:32

분류가 다익스트라로 돼있어서 의문이 들었었다.

BFS 또는 DFS 면 되지 않을까??

질문 게시판을 가보니 BFS & Prirority queue 를 이용해서 최단거리를 구하는 것은 다익스트라다!

질문 게시판에서 솔루션은 얻었는데, 아이디어를 모르겠었다.

그래서 검색을 좀 하니까 바로 아이디어를 얻었다.

1. 도착지점에 도착할때, 가장 작은 가중치를 출력하라.

가장 작은 가중치를 출력할 때, Prioritiy queue 를 이용한다.

weight 를 기준으로 Priority queue 를 구성

2. 그러면 도착한 순간이 가장 작은 가중치를 갖게된다.

끝.

	#include <cstdio>
	#include <queue>
	#include <string.h>
	/**
	* https://www.acmicpc.net/problem/1261
	* BOJ 백준온라인져지 1261 알고스팟 풀이
	*/
	using namespace std;
	int xxxx[] = {0, 1, 0, -1};
	int yyyy[] = {-1, 0, 1, 0};
	struct node {
	int x, y, w;
	node (int x, int y, int w): x(x), y(y), w(w) {}
	bool operator < (node other) const {
	return w > other.w;
	}
	};
	int main () {
	int row, col;
	scanf("%d%d", &col, &row);
	bool visited[row][col];
	char map[row][col];
	for (int i = 0; i < row; i++) {
	scanf("%s", map[i]);
	}
	memset(visited, 0, sizeof(visited));
	priority_queue<node> pq;
	pq.push(node(0, 0, 0));
	while(pq.size()) {
	node n = pq.top(); pq.pop();

	int cx = n.x; int cy = n.y; int cw = n.w;
	if (cx == row - 1 && cy == col - 1) {
	printf("%d", cw);
	break;
	}
	visited[cx][cy] = true;
	for (int i = 0; i < 4; i++) {
	int nx = cx + xxxx[i]; int ny = cy + yyyy[i];
	if (visited[nx][ny] \|\| nx < 0 \|\| ny < 0 \|\| nx >= row \|\| ny >= col) continue;
	int nw = cw + map[nx][ny] - 48;
	pq.push(node(nx, ny, nw));
	}
	}
	}

view raw BOJ_1261.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14502 연구소 풀이 (0)	2018.01.14
BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0)	2018.01.13
BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0)	2018.01.09
BOJ 백준온라인져지 1918 후위표기식 풀이 (0)	2018.01.07
BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0)	2018.01.06

BOJ 백준온라인져지 1504 특정한 최단 경로 풀이

2018. 1. 9. 21:08

1 -> N 의 최단거리를 구하면 된다.

조건

1. v1 를 거쳐야 된다.

2. v2 를 거쳐야 된다.

3. 양방향 그래프다.

문제를 보니 민힙을 구현한 다익스트라를 사용해야 될 것 같았다.

풀이 방법

1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N

2 개중에 낮은 distance 를 출력하면 된다.

둘다 INF 면 -1 를 출력

다익스트라 알고리즘을 정리해보면

u -> v 의 minimum distance 를 구하는 알고리즘.

민힙을 사용해서 구현하면,

현재점을 startVertex, startVertex 에 연결된 점을 endVertex 라고 하자.

u -> startVertex -> endVertex 의 거리가

u -> 이미 간 점 -> endVertex 의 거리보다 작거나 처음 갱신한다면,

민힙에 push 해주고, 거리를 u -> startVertex -> endVertex 의 거리로 갱신해준다.

	#include <cstdio>
	#include <queue>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/1504
	* BOJ 백준온라인져지 1504 특정한 최단 경로 풀이
	*/
	#define INF 1e+9
	using namespace std;
	int vertexCount;
	vector<vector<pair<int, int> > > edges;
	int dijkstra (int start, int end) {
	int *distance = new int[vertexCount];
	distance[start] = 0;
	priority_queue<pair<int, int> > queue;
	queue.push(make_pair(0, start));
	for (int i = 1; i < vertexCount; i++) {
	if (start == i) continue;
	distance[i] = INF;
	}
	while (queue.size()) {
	int start = queue.top().second, startDist = queue.top().first;
	queue.pop();
	for (int i = 0; i < edges[start].size(); i++) {
	int there = edges[start][i].first;
	int newDist = startDist + edges[start][i].second;
	if (distance[there] > newDist) {
	distance[there] = newDist;
	queue.push(make_pair(newDist, there));
	}
	}
	}
	return distance[end];
	}
	int main () {
	int edgeCount;
	scanf("%d%d", &vertexCount, &edgeCount);

	edgeCount++, vertexCount++;
	edges.resize(vertexCount);

	for (int i = 1; i < edgeCount; i++) {
	int u, v, w;
	scanf("%d%d%d", &u, &v, &w);
	edges[u].push_back(make_pair(v, w));
	edges[v].push_back(make_pair(u, w));
	}
	int v1, v2;
	scanf("%d%d", &v1, &v2);
	int result = INF;
	int temp = dijkstra(1, v1);
	if (temp != INF) {
	int temp2 = dijkstra(v1, v2);
	if (temp2 != INF) {
	int temp3 = dijkstra(v2, vertexCount - 1);
	if (temp3 != INF) {
	result = temp + temp2 + temp3;
	}
	}
	}
	temp = dijkstra(1, v2);
	if (temp != INF) {
	int temp2 = dijkstra(v2, v1);
	if (temp2 != INF) {
	int temp3 = dijkstra(v1, vertexCount - 1);
	if (temp3 != INF) {
	if (result > temp + temp2 + temp3)
	result = temp + temp2 + temp3;
	}
	}
	}


	printf("%d", result == INF ? -1 : result);
	}

view raw BOJ_1504.cpp hosted with ❤ by GitHub

위의 3줄을 반복하면 정답이 나옴

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이 (0)	2018.01.13
BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0)	2018.01.11
BOJ 백준온라인져지 1918 후위표기식 풀이 (0)	2018.01.07
BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0)	2018.01.06
BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0)	2018.01.04

BOJ 백준온라인져지 1918 후위표기식 풀이

2018. 1. 7. 13:49

중위 표기식을 후위 표기식으로 변경해 주면 된다.

1. 스택에 자기 자신보다 높은 우선순위를 가진 연산자가 있으면 빼서 사용한다.

2. 스택에 입력된 연산자를 push 한다.

3. 괄호가 끝나면 사용하지 않은 연산자를 다 출력한다.

4. 남은 연산자들을 출력한다.

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0)	2018.01.11
BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0)	2018.01.09
BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0)	2018.01.06
BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0)	2018.01.04
BOJ 백준온라인져지 11286 절대값 힙 풀이 (0)	2018.01.02

BOJ 백준온라인져지 1655 가운데를 말해요 풀이

2018. 1. 6. 21:53

중간 값을 출력 하면 된다.

처음 풀이는

그냥 min-heap 이던 max-heap 이던 구현한 다음에, 그 중간값을 출력했는데 틀렷다.

그래서 질문 게시판을 보니까.

중간값을 기준으로 왼쪽 오른쪽을 나누라는 거다!

그래서 나눔

	#include <cstdio>
	#include <queue>
	/**
	* https://www.acmicpc.net/problem/1655
	* BOJ 백준온라인져지 1655 가운데를 말해요 풀이
	*/
	using namespace std;
	priority_queue<int, vector<int>, less<int> > maxHeap;
	priority_queue<int, vector<int>, greater<int> > minHeap;
	int main () {
	int testCase;
	scanf("%d", &testCase);

	while (testCase--) {
	int temp;
	scanf("%d", &temp);
	if (maxHeap.empty()) maxHeap.push(temp);
	else if (maxHeap.top() < temp) minHeap.push(temp);
	else maxHeap.push(temp);

	if (maxHeap.size() < minHeap.size()) maxHeap.push(minHeap.top()), minHeap.pop();
	else if (maxHeap.size() > minHeap.size() + 1) minHeap.push(maxHeap.top()), maxHeap.pop();
	printf("%d\n", maxHeap.top());
	}
	}

view raw BOJ_1655.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0)	2018.01.09
BOJ 백준온라인져지 1918 후위표기식 풀이 (0)	2018.01.07
BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0)	2018.01.04
BOJ 백준온라인져지 11286 절대값 힙 풀이 (0)	2018.01.02
BOJ 백준온라인져지 11279 최대 힙 풀이 (1)	2017.12.30

BOJ 백준온라인져지 1715 카드 정렬하기 풀이

2018. 1. 4. 23:24

이제 heap 을 직접 구현하지 않고, priority queue 를 사용한다.

그리고 이 문제를 푸는데 계속 틀렸다.

틀린 이유는 card 의 조합 개수가 1일 때 0을 출력해야 되는데,

입력 된 카드를 다 출력해서 계속 100%에서 틀렸다.

수식은

a + b + ((a + b) + c)

위에 단계가 반복되면 결과가 나온다.

(a + b) = result 에 계속 더해주면 된다.

증명은 아직 할줄을 몰라서..

	#include <cstdio>
	#include <queue>
	/**
	* https://www.acmicpc.net/problem/1715
	* BOJ 백준온라인져지 1715 카드 정렬하기 풀이
	*/
	using namespace std;
	int main () {
	int cardCount;
	scanf("%d", &cardCount);
	priority_queue<int, vector<int>, greater<int> > queue;
	while (cardCount--) {
	int temp;
	scanf("%d", &temp);
	queue.push(temp);
	}
	int result = 0;
	while (queue.size() > 1) {
	// a + b + ((a + b) + c)
	// result = (a + b)
	int a = queue.top(); queue.pop();
	int b = queue.top(); queue.pop();
	result += a + b;
	queue.push(a + b);
	}
	printf("%d", result);
	}

view raw BOJ_1715.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1918 후위표기식 풀이 (0)	2018.01.07
BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0)	2018.01.06
BOJ 백준온라인져지 11286 절대값 힙 풀이 (0)	2018.01.02
BOJ 백준온라인져지 11279 최대 힙 풀이 (1)	2017.12.30
BOJ 백준온라인져지 1927 최소 힙 풀이 (0)	2017.12.28

BOJ 백준온라인져지 11286 절대값 힙 풀이

2018. 1. 2. 22:13

예제가 잘 돼있는 문제다.


	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/11286
	* BOJ 백준온라인져지 11286 절대값 힙 풀이
	*/
	int heap[100000] = {0}, pos = 0;
	int abs (int a) {
	if (a < 0) return -a;
	return a;
	}
	void push (int number) {
	int curPos = pos;
	heap[curPos] = number;
	int parentPos = (curPos - 1) / 2;
	while (curPos > 0 && (abs(heap[parentPos]) > abs(heap[curPos]) \|\| (abs(heap[parentPos]) == abs(heap[curPos]) && heap[curPos] <= heap[parentPos]))) {
	int temp = heap[curPos];
	heap[curPos] = heap[parentPos];
	heap[parentPos] = temp;
	curPos = parentPos;
	parentPos = (curPos - 1) / 2;
	}
	pos++;
	}
	int pop () {
	if (pos == 0) return 0;
	int result = heap[0];
	pos--; // Push 하면 다음 값을 위해 1이 올라있는 상태다.
	heap[0] = heap[pos];

	int parentPos = 0;
	while (true) {
	int leftPos = parentPos * 2 + 1;
	int rightPos = leftPos + 1;
	if (leftPos >= pos) break; // 왼쪽의 Node 가 뺀 노드였다면
	int temp = heap[parentPos];
	if ((rightPos >= pos \|\| abs(heap[leftPos]) < abs(heap[parentPos]) \|\| (abs(heap[leftPos]) == abs(heap[parentPos]) && heap[leftPos] <= heap[parentPos])) && (abs(heap[rightPos]) > abs(heap[leftPos]) \|\| (abs(heap[rightPos]) == abs(heap[leftPos]) && heap[leftPos] < heap[rightPos]))) {
	heap[parentPos] = heap[leftPos];
	heap[leftPos] = temp;
	parentPos = leftPos;
	} else if ((abs(heap[rightPos]) == abs(heap[parentPos]) && heap[rightPos] <= heap[parentPos]) \|\| abs(heap[rightPos]) < abs(heap[parentPos])) {
	heap[parentPos] = heap[rightPos];
	heap[rightPos] = temp;
	parentPos = rightPos;
	} else {
	break;
	}
	}
	return result;
	}
	int main () {
	int capacity;
	scanf("%d", &capacity);
	while (capacity--) {
	int number;
	scanf("%d", &number);
	if (number) push(number);
	else printf("%d\n", pop());
	}
	}

view raw BOJ_11286.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0)	2018.01.06
BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0)	2018.01.04
BOJ 백준온라인져지 11279 최대 힙 풀이 (1)	2017.12.30
BOJ 백준온라인져지 1927 최소 힙 풀이 (0)	2017.12.28
BOJ 백준온라인져지 14927 전구 끄기 풀이 (0)	2017.12.26

BOJ 백준온라인져지 11279 최대 힙 풀이

2017. 12. 30. 21:20

이제 아무것도 안 보고 최대힙이나 최소힙을 짤 수 있다.

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/11279
	* BOJ 백준온라인져지 11279 최대 힙 풀이
	*/
	int heap[100000] = {0}, pos = 0;
	void push (int number) {
	int curPos = pos;
	heap[curPos] = number;
	int parentPos = (curPos - 1) / 2;
	while (curPos > 0 && heap[parentPos] < heap[curPos]) {
	int temp = heap[curPos];
	heap[curPos] = heap[parentPos];
	heap[parentPos] = temp;
	curPos = parentPos;
	parentPos = (curPos - 1) / 2;
	}
	pos++;
	}
	int pop () {
	if (pos == 0) return 0;
	int result = heap[0];
	pos--; // Push 하면 다음 값을 위해 1이 올라있는 상태다.
	heap[0] = heap[pos];

	int parentPos = 0;
	while (true) {
	int leftPos = parentPos * 2 + 1;
	int rightPos = leftPos + 1;
	if (leftPos >= pos) break; // 왼쪽의 Node 가 뺀 노드였다면
	int temp = heap[parentPos];
	if ((rightPos >= pos \|\| heap[leftPos] >= heap[rightPos]) && heap[leftPos] > heap[parentPos]) {
	heap[parentPos] = heap[leftPos];
	heap[leftPos] = temp;
	parentPos = leftPos;
	} else if (heap[rightPos] > heap[leftPos] && heap[rightPos] > heap[parentPos]) {
	heap[parentPos] = heap[rightPos];
	heap[rightPos] = temp;
	parentPos = rightPos;
	} else {
	break;
	}
	}
	return result;
	}
	int main () {
	int capacity;
	scanf("%d", &capacity);
	while (capacity--) {
	int number;
	scanf("%d", &number);
	if (number) push(number);
	else printf("%d\n", pop());
	}
	}

view raw BOJ_11279.cpp hosted with ❤ by GitHub

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0)	2018.01.04
BOJ 백준온라인져지 11286 절대값 힙 풀이 (0)	2018.01.02
BOJ 백준온라인져지 1927 최소 힙 풀이 (0)	2017.12.28
BOJ 백준온라인져지 14927 전구 끄기 풀이 (0)	2017.12.26
BOJ 백준온라인져지 2623 음악프로그램 풀이 (0)	2017.12.23

PREV 1 ···17 18 19 20 21 22 23 ···30 NEXT

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

알고리즘을 좋아하는 나

IT/알고리즘

BOJ 백준온라인져지 11375 열혈강호 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14502 연구소 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 4485 녹색 옷 입은 애가 젤다지? 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1261 알고스팟 풀이 Raw

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1504 특정한 최단 경로 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1918 후위표기식 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1655 가운데를 말해요 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1715 카드 정렬하기 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11286 절대값 힙 풀이

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11279 최대 힙 풀이

'IT > 알고리즘' 카테고리의 다른 글

+ Recent posts

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역