Heap 은

최소 힙과

최대 힙이 있다.


Heap 은 완전 이진트리다.


#include <cstdio>
/**
* https://www.acmicpc.net/problem/1927
* BOJ 백준온라인져지 1927 최소 힙 풀이
*/
using namespace std;
class Heap {
public:
Heap (int capacity);
void push (int data);
int pop ();
private:
int *heap;
int capacity;
int pos;
};
Heap::Heap (int capacity) : capacity(capacity) {
heap = new int[capacity];
pos = 0;
}
int Heap::pop () {
if (pos == 0) return 0;
int data = heap[0];
pos--;
heap[0] = heap[pos];
int parentPos = 0;
while (true) {
int leftPos = parentPos * 2 + 1;
int rightPos = leftPos + 1;
if (leftPos >= pos) break; // 마지막에는 맨 위에 있던것이 들어간다.
int temp = heap[parentPos]; // swap 하기 위함
if ((rightPos >= pos || heap[leftPos] <= heap[rightPos]) && heap[leftPos] < heap[parentPos]) {
heap[parentPos] = heap[leftPos];
heap[leftPos] = temp;
parentPos = leftPos;
} else if(heap[leftPos] > heap[rightPos] && heap[rightPos] < heap[parentPos]) {
heap[parentPos] = heap[rightPos];
heap[rightPos] = temp;
parentPos = rightPos;
} else {
break;
}
}
return data;
}
void Heap::push (int number) {
if (pos == capacity) return;
int curPos = pos;
int parentPos = (curPos - 1) / 2;
heap[pos] = number;
while (curPos > 0 && heap[curPos] < heap[parentPos]) {
int temp = heap[curPos];
heap[curPos] = heap[parentPos];
heap[parentPos] = temp;
curPos = parentPos;
parentPos = (curPos - 1) / 2;
}
pos++;
}
int main () {
int capacity;
scanf("%d", &capacity);
Heap heap(capacity);
while (capacity--) {
int number;
scanf("%d", &number);
if (number == 0) printf("%d\n", heap.pop());
else heap.push(number);
}
}
view raw BOJ_1927.cpp hosted with ❤ by GitHub

맨 위의 전구는 한 번씩 다 껐다 켜본다.

모든 전구는 2번 이상 건드리지 않는다.


대충 나오는 시간복잡도

O(2^N*N^2)

=> O(2^N)

N은 최대 18





풀이 방법 : 위의 전구가 켜져있으면 끈다.

근데 맨 위의 전구는 방법이 없다.

그래서 다 해본다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/14927
* BOJ 백준온라인져지 14927 전구 끄기 풀이
*/
using namespace std;
int yyyy[] = {0, 0, 1, 0, -1};
int xxxx[] = {0, -1, 0, 1, 0};
int result = 1e9, N;
int min (int a, int b) {
return a < b ? a : b;
}
void recursive2 (vector<vector<int> > lights, int count) {
for (int i = 2; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lights[i - 1][j]) {
count++;
for (int k = 0; k < 5; k++) {
int x = i + xxxx[k], y = j + yyyy[k];
if (x <= 0 || y <= 0 || x >= N || y >= N) continue;
lights[x][y] = lights[x][y] * -1 + 1;
}
}
}
}
bool isBreaked = false;
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lights[i][j]) {
isBreaked = true;
goto breakLoop;
}
}
}
breakLoop:
if (!isBreaked) result = min(count, result);
}
void recursive1 (vector<vector<int> > lights, int length) {
int count = 0;
for (int i = 0; i < N - 1; i++) {
if (length & 1 << i) {
count++;
for (int k = 0; k < 5; k++) {
int x = 1 + xxxx[k], y = i + 1 + yyyy[k];
if (x <= 0 || y <= 0 || x >= N || y >= N) continue;
lights[x][y] = lights[x][y] * -1 + 1;
}
}
}
recursive2(lights, count);
}
int main () {
scanf("%d", &N);
N++;
vector<vector<int> > originalLights;
originalLights.resize(N);
for (int i = 1; i < N; i++) {
originalLights[i].resize(N);
for (int j = 1; j < N; j++) {
scanf("%d", &originalLights[i][j]);
}
}
for (int i = (1 << (N - 1)) - 1; i >= 0; i--) {
recursive1(originalLights, i);
}
printf("%d", result == 1e9 ? -1 : result);
}
view raw BOJ_14927.cpp hosted with ❤ by GitHub
#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/2623
* BOJ 백준온라인져지 2623 음악프로그램 풀이
*/
using namespace std;
int main () {
int numberOfVector;
int testCase;
scanf("%d%d", &numberOfVector, &testCase);
numberOfVector++;
int *indegree = new int[numberOfVector];
vector<vector<int> > edges;
edges.resize(numberOfVector);
for (int i = 1; i < numberOfVector; i++) {
indegree[i] = 0;
}
while(testCase--) {
int numberOfEdge;
int firstSinger;
scanf("%d%d", &numberOfEdge, &firstSinger);
for (int i = 1; i < numberOfEdge; i++) {
int lastSinger;
scanf("%d", &lastSinger);
indegree[lastSinger]++;
edges[firstSinger].push_back(lastSinger);
firstSinger = lastSinger;
}
}
queue<int> result;
queue<int> queue;
for (int i = 1; i < numberOfVector; i++) {
if (indegree[i] == 0) queue.push(i);
}
while (queue.size()) {
int here = queue.front();
queue.pop();
result.push(here);
for (int i = 0, size = edges[here].size(); i < size; i++) {
int there = edges[here][i];
indegree[there]--;
if (indegree[there] == 0) queue.push(there);
}
}
if(result.size() == numberOfVector - 1) {
while(result.size()) {
printf("%d\n", result.front());
result.pop();
}
} else {
printf("0");
}
}
view raw BOJ_2623.cpp hosted with ❤ by GitHub

위상 정렬 Week 끝!


내일은 Merge Sort 를 다시 복습 해야겠다.


다음주는 MST 를 공부해야지!

음.. 친구의 부탁으로 만들어봤다.


애니팡이 맞으려나?


게임 진행하는 코드를 짰다기보단.

게임에서 사용하는 로직들을 짰다.


상하좌우 3개가 같은게 있으면 클리어하고, 정렬


*.spec은 테스트하는 코드

코드링크



flowchart를 그리면서 했으면, 더 최적화가 가능했을거 같다.

ACM CRAFT와 비슷한 문제다.

1. in-degree가 0인거 부터

2. 문제 번호가 낮은거 우선순위


문제 번호가 낮은거 우선순위는 priority_queue로 하면되고,

in-degree는 위상정렬



#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/1766
* BOJ 백준온라인져지 1766 문제집 풀이
*/
using namespace std;
int main () {
int numberOfVector;
int numberOfEdge;
scanf("%d%d", &numberOfVector, &numberOfEdge);
numberOfVector++;
numberOfEdge++;
int *indegree = new int[numberOfVector];
vector<vector<int> > edges;
edges.resize(numberOfVector);
for (int i = 1; i < numberOfVector; i++) {
indegree[i] = 0;
}
for (int i = 1; i < numberOfEdge; i++) {
int firstSolve;
int lastSolve;
scanf("%d%d", &firstSolve, &lastSolve);
edges[firstSolve].push_back(lastSolve);
indegree[lastSolve]++;
}
priority_queue<int, vector<int>, greater<int> > queue;
for (int i = 1; i < numberOfVector; i++) {
if (indegree[i] == 0) queue.push(i);
}
while (queue.size()) {
int here = queue.top();
queue.pop();
printf("%d\n", here);
for (int i = 0, size = edges[here].size(); i < size; i++) {
int there = edges[here][i];
indegree[there]--;
if (indegree[there] == 0) queue.push(there);
}
}
}
view raw BOJ_1766.cpp hosted with ❤ by GitHub

A -> B

C -> B 일때,


B = MAX(A, C)

이런식으로 값이 들어간다.



이번주는 위상 정렬 문제만 풀어야지 ㅋㅋ


만약 진입차수가 0인게 endVertex 인 것을 처리하기 위해

if(indegree[i] == 0) queue.push(i), minimumSecond[i] = second[i];


#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/1005
* BOJ 백준온라인져지 1005 ACM Craft 풀이
*/
int max(int a, int b) {
return a > b ? a : b;
}
using namespace std;
int main() {
int testCase;
scanf("%d", &testCase);
while(testCase--) {
int numberOfVertex;
int numberOfEdge;
scanf("%d%d", &numberOfVertex, &numberOfEdge);
numberOfVertex++;
int *minimumSecond = new int[numberOfVertex];
int *second = new int[numberOfVertex];
int *indegree = new int[numberOfVertex];
for(int i = 1; i < numberOfVertex; i++) {
indegree[i] = second[i] = minimumSecond[i] = 0;
scanf("%d", &second[i]);
}
queue<int> queue;
vector<vector<int> > vector;
vector.resize(numberOfVertex);
for(int i = 0; i < numberOfEdge; i++) {
int startVertex;
int endVertex;
scanf("%d%d", &startVertex, &endVertex);
vector[startVertex].push_back(endVertex);
indegree[endVertex]++;
}
for(int i = 1; i < numberOfVertex; i++) {
if(indegree[i] == 0) queue.push(i), minimumSecond[i] = second[i];
}
int endVertex;
scanf("%d", &endVertex);
while(queue.size()) {
int cur = queue.front();
queue.pop();
for(int i = 0, size = vector[cur].size(); i < size; i++) {
int next = vector[cur][i];
indegree[next]--;
minimumSecond[next] = max(minimumSecond[next], minimumSecond[cur] + second[next]);
if(indegree[next] == 0) queue.push(next);
}
}
printf("%d\n", minimumSecond[endVertex]);
}
}
view raw BOJ_1005.cpp hosted with ❤ by GitHub

dp로 풀었다. O(NM)


입력차례대로 위칸과 왼쪽칸과 왼쪽위 대각선 칸을 비교해서 가장 작은값 + 1로 새로운 정사각형을 만들 수 있다.

#include <cstdio>
/**
* https://www.acmicpc.net/problem/14925
* BOJ 백준온라인져지 14925 목장 건설하기 풀이
*/
int min(int a, int b){
return a < b ? a : b;
}
int max(int a, int b){
return a > b ? a : b;
}
int main(){
int rowSize, columnSize, result = 0;
scanf("%d%d", &rowSize, &columnSize);
rowSize++, columnSize++;
bool **map = new bool*[rowSize];
int **dp = new int*[rowSize];
for(int i = 0; i < rowSize; i++){
map[i] = new bool[columnSize];
map[i][0] = true;
dp[i] = new int[columnSize];
}
for(int i = 0; i < columnSize; i++){
map[0][i] = true;
}
for(int i = 1; i < rowSize; i++){
for(int j = 1; j < columnSize; j++){
dp[i][j] = 0;
int temp;
scanf("%d", &temp);
map[i][j] = temp == 0;
if(map[i][j]){
dp[i][j] = 1;
int t = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
dp[i][j] = t + 1;
result = max(dp[i][j], result);
}
}
}
printf("%d", result);
}
view raw BOJ_14925.cpp hosted with ❤ by GitHub


NYPC에서 풀었던 문제와 유사하다.


NYPC문제때는 급수를 이용해서 풀었었는데 틀리다고 나왔었다.


#include <cstdio>
/**
* https://www.acmicpc.net/problem/14924
* BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이
*/
int main(){
int trainVelocity, aFlyVelocity, distance;
scanf("%d%d%d", &trainVelocity, &aFlyVelocity, &distance);
printf("%d", distance / (trainVelocity * 2) * aFlyVelocity);
}
view raw BOJ_14924.cpp hosted with ❤ by GitHub


벽 부신다!!!

#include <cstdio>
#include <queue>
/**
* https://www.acmicpc.net/problem/2206
* BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이
*/
#define INF 99999999
using namespace std;
int xxxx[] = {0, 1, 0 , -1};
int yyyy[] = {-1, 0, 1 , 0};
class coordinate{
public:
int x, y;
bool z;
coordinate(int _x, int _y, bool _z) :x(_x), y(_y), z(_z){}
};
int min(int a, int b){
return a < b ? a : b;
}
int main(){
int rowSize, columnSize;
scanf("%d%d", &rowSize, &columnSize);
rowSize++, columnSize++;
int ***resultArray = new int**[rowSize], **map = new int*[rowSize];
for(int i = 1; i < rowSize; i++){
resultArray[i] = new int*[columnSize];
map[i] = new int[columnSize];
for(int j = 1; j < columnSize; j++){
resultArray[i][j] = new int[2];
char temp;
scanf("%c", &temp);
if(temp < '0' || temp > '9'){
j--;
continue;
}
resultArray[i][j][0] = resultArray[i][j][1] = INF, map[i][j] = temp - 48;
}
}
int startX = 1, startY = 1;
int endX = rowSize - 1, endY = columnSize - 1;
resultArray[startX][startY][0] = 1;
queue<coordinate> queue;
queue.push(coordinate(1, 1, false));
while(!queue.empty()){
coordinate polledData = queue.front();
queue.pop();
int x = polledData.x;
int y = polledData.y;
bool z = polledData.z;
int moveCount = resultArray[x][y][z] + 1;
for(int i = 0 ; i < 4; i++){
int newX = xxxx[i] + x;
int newY = yyyy[i] + y;
if(newX <= 0 || newX >= rowSize || newY <= 0 || newY >= columnSize) continue;
if(map[newX][newY] == 0 && moveCount < resultArray[newX][newY][z]){
queue.push(coordinate(newX, newY, z)), resultArray[newX][newY][z] = moveCount;
}else if(map[newX][newY] == 1 && !z && moveCount < resultArray[newX][newY][1]){
queue.push(coordinate(newX, newY, 1)), resultArray[newX][newY][1] = moveCount,
resultArray[newX][newY][2] = 1;
}
}
}
int result = min(resultArray[endX][endY][0], resultArray[endX][endY][1]);
if(result == INF) result = -1;
printf("%d", result);
}
view raw BOJ_2206.cpp hosted with ❤ by GitHub


벽을 한 번 부신다!!


코드가 길지 않으니 설명은 없다.

#include <cstdio>
#include <queue>
/**
* https://www.acmicpc.net/problem/14923
* BOJ 백준온라인져지 14923 미로탈출 풀이
*/
#define INF 99999999
using namespace std;
int xxxx[] = {0, 1, 0 , -1};
int yyyy[] = {-1, 0, 1 , 0};
class coordinate{
public:
int x, y;
bool z;
coordinate(int _x, int _y, bool _z) :x(_x), y(_y), z(_z){}
};
int min(int a, int b){
return a < b ? a : b;
}
int main(){
int rowSize, columnSize;
scanf("%d%d", &rowSize, &columnSize);
rowSize++, columnSize++;
int ***resultArray = new int**[rowSize], **map = new int*[rowSize];
int startX, startY;
int endX, endY;
scanf("%d%d%d%d", &startX, &startY, &endX, &endY);
for(int i = 1; i < rowSize; i++){
resultArray[i] = new int*[columnSize];
map[i] = new int[columnSize];
for(int j = 1; j < columnSize; j++){
resultArray[i][j] = new int[2];
scanf("%d", &map[i][j]);
resultArray[i][j][0] = resultArray[i][j][1] = INF;
}
}
resultArray[startX][startY][0] = 0;
queue<coordinate> queue;
queue.push(coordinate(startX, startY, false));
while(!queue.empty()){
coordinate polledData = queue.front();
queue.pop();
int x = polledData.x;
int y = polledData.y;
bool z = polledData.z;
int moveCount = resultArray[x][y][z] + 1;
for(int i = 0 ; i < 4; i++){
int newX = xxxx[i] + x;
int newY = yyyy[i] + y;
if(newX <= 0 || newX >= rowSize || newY <= 0 || newY >= columnSize) continue;
if(map[newX][newY] == 0 && moveCount < resultArray[newX][newY][z]){
queue.push(coordinate(newX, newY, z)), resultArray[newX][newY][z] = moveCount;
}else if(map[newX][newY] == 1 && !z && moveCount < resultArray[newX][newY][1]){
queue.push(coordinate(newX, newY, 1)), resultArray[newX][newY][1] = moveCount,
resultArray[newX][newY][2] = 1;
}
}
}
int result = min(resultArray[endX][endY][0], resultArray[endX][endY][1]);
if(result == INF) result = -1;
printf("%d", result);
}
view raw BOJ_14923.cpp hosted with ❤ by GitHub


+ Recent posts