Jesus saw the crowd who were there. He went up on a hill and sat there. His foloowers came to him. Jesus taught the people and said: "Those people who know htey have great spiritual needs are happy. The kingdom of heaven belongs to them. Thos who are sad now are happy. The earth will belong to them. Those who want to do right more than anything else are happy. God will fully satisfy them. Those who give mercy to others are happy. Mercy will be given to them. Those who are pure in their thinking are happy. They will be with God. Those who work to bring peace are happy. God will call them his sons. Those who are treated badly for doing good are happy. The kingdom of heaven belongs to them. People will say bad things about you and hurt you. They will lie and say all kinds of evil things about you because you follow me. But when they do these things to you, you are happy. Rejoice and be glad. You have a great reward waiting for you in heaven. People did the same evil things to the prophets who lived before you. "You are the salt of the earth. But if the salt loses its salty taste, it cannt be made salty again. It is good for nothing. It must be thrown out for people to walk on. "You are the light that gives light to the world. A city that is built on al hill cannot be hidden. And people don't hide a light under a bowl. They put the light on a lampstand. Then the light shines for all the people in the house. In the same way, you should be a light for other people. Live so that they will see the good things you do. Live so that they will praise you Father in heaven. "Don't think that I have come to destroy the law of Moses or the teaching of the prophets. I have not come to destroy their teachings but to do what they said. I tell you the truth. Nothing will disappear from the law until heaven and earth are gone. The law will not lose even the smallest letter or the smallest part of a letter until all has happened. Whoever refuses to obey any command and teaches other people not to obey taht command will be the least important in the kingdom of heaven. But whoever obeys the law and teaches other people to obey the law will be great in the kingdom of heaven. I tell you that you must do better then the teachers of the law and the Pharisees. If you are not better than they are, you will not enter the kingdom of heave. "You have heard that it was said to our people long ago, 'You must not murder anyone. Anyone who murders another will be judged.' But I tell you, if you are angry with your brother, you will be judged. And if you say bad things to your brother, you will be judged by the Jewish council. And if you call your brother a fool, they you will be in danger of the fire of heall. "So when you offer your gift to God at the altar, and you remember that your brother has something agaist you, leave your gift there at the altar. Go and make peace with him. Then come and offer your gift. "If your enemy is taking you to court, become friends with him quickly. You should do that before you go to court. It you don't become his friend, he might turn you over to the judge. And the judge might give you to a guard to put you in jail. I tell you that you will not leave that jail until you have paid everything you owe. "You have heard that it was waid, 'You must not be guilty of adultery. But I tell you that if anyone looks at a wonman and wants to sin sexually with her, then he has already done that sin with the woman in his mind. If your right eye causes you to sin, then take it out and throw it away. It is better to lose one part of your body than to have your whold body thrown into hell. If your right hand causes you to sin, then cut if off and throw it away. It is better to lose one part of your body than for your whole body to go into hell. "It was also said, 'Anyone who divorces his wife must give her a writter divorce paper.' But I tell you that anyone who divorces his wife is causing his wife to be guild of adultery. The only reason for a man to divorce his wife is if she has sexual relations with another man. And anyone who marries that divorced woman is guilty of adultery. "You have heard that it was said to our people long ago, 'When you make a promise, don't break your promise. Keep the rpomises that you make to the Lord.' But I tell you, never make an oath. Don't make an oath using the name of heaven, because heaven is God's throne. Don't make an oath using the name of the earth, because the earth belongs to God. Don't make an oathe using the name of Jerusalem, because that is the city of the great King. And don't even say that your own head is proof that you will keep your oath. You cannot make one hair on your head become white or black. Say only 'yes' if you mean 'yes', and say only 'no' if you mean 'no'. If you must say more than 'yes' or 'no', if is from the Evil One. "You have heard that it was said. And eye for an eye, and a tooth for a tooth. But I tell you, don't stand up against an evil person. If someone slaps you on the right cheek, then turn and let him slap the other cheek too. If someone wants to sue you in court and take your shirt, then let him have your coat too. If a soldier forces you to go with him on mile, then go with him two miles. If a person asks you for something, then five it to him. Don't refuse to give to a person who warnts to borrow from you. "You have heard that it was said. 'Love your neighbor and hate your enemies.' But I tell you, love your enemies. Pray for those who hurt you. If you do this, then you will the true sons of your Father in heaven. Your Father casues the sun to rise on good people and on bad people. You Father sends rain to those who do good and to those who do wrong. If you love only the people who love you, then you will get no reward. Even the tax collectors do that. And if you are nice only to your friends, then you are no better than other people. Even people without God are nice to their friends. So you must be perfect, just as your Father in heave is perfect.

Then the Spirit led Jesus into the desert to be tempted by the devil. Jesus ate nothing for 40days and nights. After this, he was very hungty. The devil came to Jesus to tempt him. The devil said. "If you are the Son of God, tell these rocks to become bread." Jesus answered, "It is written in the Scriptures. 'A person does not live only by eating bread. But a person lives by everything the Lord says.'" Then the devil led Jesus to the holy city of Jerusalem. He put Jesus on a very high place of the Temple. The devil said, "If you are the Son of God, jump off. It is written in the Scriptures. 'He has put his angels in charge of you. They will catch you with their hands. And you will not hit your foot on a rock.'" Jesus answered him. "It also says in the Scriptures, 'Do not test the Lord your God.'" Then the devil led Jesus to the top of a very high mountain. He shoved Jesus all the kingdoms of the world and all the great things that are in those kingdoms. The devil said, "If you will bow down and worship me, I will give you all these things." Jesus said to the devil, "Go away from me, Satan! It is written in the Scriptures. 'You must worship the Lord you God. Serve only him!'" So the devil left Jesus. And then some angels came to Jesus and helped him. Jesus heard that John had been put in prison. So Jesus went back to Galilee. He left Nazareth and went and lived in Cpermaum, a town near Lake Galilee. Carpernaum is the area near Zebulun and Naphtali. Jesus did this to make true what the prophet Isaih said: "Land of Zebulun and land of Naptali are on the way to the sea. They are along the Jordan River. This is Galilee where the non-Jewish people live. These people who live in darkness will see a great light. They live in a place that is very dark. But a light will shine on him." From that time Jesus began to preach, saying "Change your hearts and lives, because the kingdom of heaven is coming soon." Jesus was walking by Lake Galilee. He was two brothers, Simon(called Peter) and Simon's brother Andrew. The brothers were fishermen, and they were fishing in the lake with a net. Jesus said, "Come follow me. I will make you fishermen for men." At once Simon and Andrew left their nets and followed him. Jesus continued walking by Lake Galilee. Hew saw two other brothers, James and John, the son of Zebedee. They were in a boat with their father Zebedee, preparing their nets to catch fish. Jesus told them to come with him. At once they left the boat and their father, and they followed Jesus. Jesus went everywhere in Galilee. He taught in the synagogus and preached the Good News about the kingom of heaven. And he healed all the people's diseases and sickness. the news about Jesus spread all over Syria, and people brought all the sick to him. These sick people were suffering from different kinds of diseases and pain, some had demons, some were epiliptics, and some were paralyzed. Jesus healed all of them. Many people followed him. They came from Galilee, the Ten Towns, Jerusalem, Judae, and the land across the Jordan River.

About that time John the Baptist came and began preaching in the desert area of Judea. John said, "Change your hearts and lives because the kingdom of heaven is coming soon." John the Baptist is the one Isaiah the prophet was talking about. Isaiah the prophet was talking about Isaiah said: "This is a voice of a man who calls out in the desert: Make the road straight for him." John's clothes were made from camel's hair. He wore a leather belt around his waist. For foo, he ate locusts and and wild honey. Many people went to hear John preach. They came from Jerusalem and all Judea and all the are aroung the Jordan River. They told of the sins they had done, and John baptized them in the Jordan River. Many of the Phrisees and Sadducess came to the place where John was baptizing people. When John saw them, he said: "You are all snakes! Who warned you to run away from God's anger that is coming? You must do the things that show that you have really changed your hearts and lives. And don't think that you can say to yourselves, 'Abraham is our father.' I tell you that God could make children for Abraham from these rocks. The ax is now ready to cut down the tress. Every tree that does not produce good fruit will be cut down and thrown into the fire." I baptize you with water to show that your hearts and lives have changes. But there is one coming later who is greater than I am. I am not good enough greater than I am. I am not good enough to carry his sandals. He will baptize you with the Holy Spirit and with fire. He will come ready to clean the grain. He will seperater the good grain from the chaff. He will put the good part of the grain into his barn. And he will burn the chaff with a fire that cannot be putout." At that time Jesus came from Calilee to the Jordan River. He came to John and wanted John to baptize him. But John tried to stop him. John said, "Why do you come to me to be baptized? I should be baptized by you!" Jesus answered, "Let it be this way for now. We should do all things that are for now." So John agreed to baptize Jesus. Jesus was baptized and came up out of the water. Heaven opened, and he saw God's Spirit coming down on him like a God's Spirit coming down on him like a dove. And a voice spoke from heaven. The voice said, "This is my Son and I love him. I am very pleased with him."

Jesus was born in the town of Bethlehem in Judea duing the time when Herod was king. After Jesus was born, some wise men from the east came to Jerusalem. they asked, "Where is the baby who was born to be the king of the Jews? We was his star in the east. We came to worship him." When King Herod heard about this new king of the Jews, he was troubled. And all the people in Jerusalem were worried too. Herod called a meeting of all the leading priests and teachers of the law. He asked them where the Christ would be born. They answered, "In the town of Bethlehem in Judea. The prophet wrote about this in the Scriptures: But you Bethlehem, in the land of Judah, you are important among the rulers of Judah. A ruler will come from you. He will be like a shepherd for my people, the Israelites." Then Herod had a secret meeting with the wise men from the east. He learned from them the exact time they first saw the star. Then Herod sent the wise men to Bethlehem. He said to them, "Go and look carefully to find the child. When you find him, come tell me. Then I can go worship him too." The wise men heard the king and then left. They saw the samestar they had seen in the east. It went before them until it stopped above the place where the child was. When the wise men saw the star, they were filled with joy. They went to the house where the child was ans saw him with his mother, Mary. They bowed down and worshiped the child. They opened the gifts they brought for him. They gave him treasures of gold, frankincese, and myrrh. But God warned the wise men in a dream not to go back to Herod. So they went home to their own country by a different way. After they left, an angel of the Lord came to Joseph in a dream. The angel said, "Get up! Take the child and his mother and escape to Egypt. Herod will start looking for the child to kill him. Stay in Egypt until I tell you to return." So Joseph got up and left for Egypt during the night with the child and his mother. Joseph stayed in Egypt until Herod died. This was to make clear the full meaning of what the :ord had said through the prophet. The Lord said, "I called my son out of Egypt." When Herod saw that the wise men had tricked him, he was very angry. So he gave an order to kill all the baby boys in Bethlehem and in all the area around Bethlehem who were two years old or younger. This was in keeping with the time he learned from the wise men. So what God had said throuhg the prophet Jeremiah came true: "A sound was heard in Ramah. It was painful crying and much sadness. Rachel cried for her children, and she cannot be comforted because her children are dead." After Herod died, an angel of the Lord came to Joseph in a dream. This happened while Joseph was in Egypt. The angel said, "Get up! Take the child and his mother and go to Israel. The people who werer trying to kill the child are now dead." So Joseph took the hild and his mother and went to Israel. But he heard that Archelaus was now king in Judea. Archelaus became king whem his father Herod died. So Joseph was afraid to go ther. After being warned in a dream, he went to the area of Galilee. He went to a town called Nazareth and lived ther. And so what God had said throught the prophets came true : "He will be alled a Nazarene."

13975: 파일 합치기3

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오. 예를 들어, C1, C2, C3, C4가 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다. 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

예제 입력1

2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력1

300
826

풀이방법

우선순위 큐를 사용하여 현재 힙에 있는 최소값을 두 개 꺼내서 두 개를 더하고 더한 값을 다시 큐에 저장한다. 더한 값은 다른 변수에 누적하여 더한다. 이 행동들을 큐에 저장된 값이 1개가 될 때까지 반복해준다.

코드

#include <iostream>
#include <queue>
#include<vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
priority_queue<long long, vector<long long >, greater<long long>> pq;

long long sum(priority_queue<long long, vector<long long>, greater<long long>>& p) {
    long long min = 0;
    while (p.size() > 1) {
        long long a = p.top();
        p.pop();
        long long b = p.top();
        p.pop();
        long long n = a + b;
        min += n;
        p.push(n);
    }
    p.pop();
    return min;
}
int main() {
    int T;
    long long K,f;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%lld", &K);
        for (int j = 0; j < K; j++) {
            scanf("%lld", &f);
            pq.push(f);
        }
        printf("%lld\n", sum(pq));
    }
}

후기

이 문제 역시 앞서 푼 문제들과 비슷한데 자료형에 유의해야했다. 파일의 크기를 누적해서 더하다보니 int의 범위를 넘어갈 수 있다. 그래서 long long 으로 바꿔주면 쉽게 정답 처리가 된다.

정의

• 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 됨
• 부여되는 우선순위에 따라 스택이나 큐로 동작 가능
• 배열, 연결리스트, 히프로 구현 가능
• 우선순위 큐의 종류
  • 최소 우선순위 큐: 가장 우선순위가 낮은 요소를 먼저 삭제
  • 최대 우선순위 큐: 가장 우선순위가 높은 요소를 먼저 삭제

추상자료형

힙

정의

• 우선순위 큐를 완전 이진 트리로 구현하는 방법
• 최솟값이나 최댓값을 쉽게 추출 가능
• 내부노드에 키를 저장하며 두 가지 속성를 만족하는 이진트리
  • 힙순서 : key(v) ≥ key(parent(v))
  • 완전 이진트리
• 히프의 종류
  • 최소 히프(min heap): 부모 노드의 값 ≤ 자식노드의 값인 완전 이진 트리 (최소 히프의 루트 노드: 가장 작은 값을 가짐)
    • 정렬 시 최소 히프의 사용 권장
  • 최대 히프(max heap): 부모 노드의 값 ≥ 자식노드의 값인 완전 이진 트리 (최대 히프의 루트 노드: 가장 큰 값을 가짐)
• 완전이진트리: 높이 h의 완전 트리에서 레벨 1~레벨 h-1까지는 포화 이진 트리이며 레벨 h에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리(중간에 빈 노드가 없다)
• 1차원 배열로도 구현 가능
• 배열을 이용한 완전이진트리 구현 시 응용 식
  • (왼쪽 자식의 인덱스)=(부모의 인덱스)*2
  • (오른쪽 자식의 인덱스)=(부모의 인덱스)*2+1
  • (부모의 인덱스)=(자식의 인덱스)/2
• 힙의 마지막 노드: 깊이 (h-1)의 가장 오른쪽 내부노드

추상자료형

구현1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0

typedef struct HeapElementType {
    int key;
    char data;
}HeapNode;

typedef struct ArrayHeapType {
    int maxElementCount;//최대 노드 개수
    int currentElementCount;//현재 노드 개수
    HeapNode* pElement;//노드 저장을 위한 1차원 array
}ArrayMaxHeap, ArrayMinHeap;

ArrayMaxHeap* createArrayMaxHeap(int maxElementCount) {
    ArrayMaxHeap* pReturn = NULL;
    int i = 0;
    if (maxElementCount > 0) {
        pReturn = (ArrayMaxHeap*)malloc(sizeof(ArrayMaxHeap));
        if (pReturn != NULL) {
            pReturn->maxElementCount = maxElementCount;
            pReturn->currentElementCount = 0;
            pReturn->pElement = (HeapNode*)malloc(sizeof(HeapNode) * (maxElementCount + 1));
            if (pReturn->pElement == NULL) {
                printf("오류, 2번째 메모리 할당, createArrayList()\n");
                free(pReturn);
                return NULL;
            }
            memset(pReturn->pElement, 0, sizeof(HeapNode) * (maxElementCount + 1));
        }
        else {
            printf("오류, 메모리 할당, createArrayList()\n");
        }
    }
    else {
        printf("최대 원소 개수는 0보다 커야 합니다\n");
    }
    return pReturn;
}
void insertMaxHeapAH(ArrayMaxHeap* pHeap, HeapNode element) {
    int i = 0;
    if (pHeap != NULL) {
        if (pHeap->currentElementCount == pHeap->maxElementCount) {//히프의 크기를 초과하여 저장하는지 점검
            printf("오류, 히프가 가득찼습니다 [%d], insertMaxHeapAH()\n", pHeap->maxElementCount);
        }
        pHeap->currentElementCount++;//현재 노드 개수를 1증가
        i = pHeap->currentElementCount;//변수i는 현재 히프에서의 마지막 노드를 가르키는 위치 인덱스
        while ((i != 1) && (element.key > pHeap->pElement[i / 2].key)) {//부모 노드와 키 값 비교
            pHeap->pElement[i] = pHeap->pElement[i / 2];
            i /= 2;
        }
        pHeap->pElement[i] = element;
    }
}
HeapNode* deleteMaxHeapAH(ArrayMaxHeap* pHeap) {
    HeapNode* pReturn = NULL;
    HeapNode* pTemp = NULL;
    int i = 0;
    int parent = 0, child=0;
    if (pHeap != NULL && pHeap->currentElementCount > 0) {//현재 반환 가능한 노드가 있는지 점검
        pReturn = (HeapNode*)malloc(sizeof(HeapNode));
        if (pReturn == NULL) {//반환되는 노드에 대한 메모리 할당 및 점검
            printf("오류, 메모리 할당, deleteMaxHeapAH()\n");
            return NULL;
        }
        *pReturn = pHeap->pElement[1];//루트 노드가 반환되는 노드임. 반환되는 노드의 값으로 기존 루트 노드의 값을 대입
        i = pHeap->currentElementCount;//히프의 제일 마지막 위치 인덱스
        pTemp = &(pHeap->pElement[i]);//히프의 제일 마지막 노드를 가리킴
        pHeap->currentElementCount--;//현재 노드 개수 1개 감소

        parent = 1;//루프가 시작되는 곳은 루트 노드
        child = 2;//루트 노드의 왼쪽 자식 노드
        while (child <= pHeap->currentElementCount) {//히프의 제일 마지막 위치에 있는 노드를 만날 때까지
            if ((child < pHeap->currentElementCount)&&(pHeap->pElement[child].key<pHeap->[child+1].key)) {
                child++;//왼쪽 자식노드보다 오른쪽 자식노드의 키 값이 더 크다면, 오른쪽 자식 노드가 비교 대상이 되도록 위치 인덱스 child를 수정
            }
            if (pTemp->key >= pHeap->pElement[child].key) {
                break;//히프의 제일 마지막 노드와 현재 노드의 키 값을 비교하여 만약 마지막 노드의 키 값이 현재 노드보다 크거나 같다면 루프를 빠져 나온다. 이 위치에 삽입
            }
            pHeap->pElement[parent] = pHeap->pElement[child];//현재의 노드를 부모노드의 위치로 한 칸 이동
            parent = child;//아래 레벨로 이동
            child *= 2;
        }
        pHeap->pElement[parent] = *pTemp;
    }
    return pReturn;
}
void deleteArrayMaxHeap(ArrayMaxHeap* pHeap) {
    if (pHeap != NULL) {
        if (pHeap->pElement != NULL) {
            free(pHeap->pElement);
        }
        free(pHeap);
    }
}

구현2

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_ELEMENT 200
typedef struct {
    int key;
}element;
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;
HeapType* create() {
    return (HeapType*)malloc(sizeof(HeapType));
}
void init(HeapType* h) {
    h->heap_size = 0;
}
void insert_max_heap(HeapType* h, element item) {
    int i;
    i = ++(h->heap_size);
    while ((i != 1) && (item.key > h->heap[i / 2].key)) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;
}
element delete_max_heap(HeapType* h) {
    int parent, child;
    element item, temp;
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    while (child <= h->heap_size) {
        //현재 노드의 자식노드 중 더 큰 자식노드 찾기
        if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key))
            child++;
        if (temp.key >= h->heap[child].key)
            break;
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}
int main(void) {
    element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
    element e4, e5, e6;
    HeapType* heap;
    heap = create();
    init(heap);

    insert_max_heap(heap, e1);
    insert_max_heap(heap, e2);
    insert_max_heap(heap, e3);

    e4 = delete_max_heap(heap);
    printf("< %d >", e4.key);
    e5 = delete_max_heap(heap);
    printf("< %d >", e5.key);
    e6 = delete_max_heap(heap);
    printf("< %d >", e6.key);

    free(heap);
}

힙 정렬

• 히프 정렬: 정렬할 배열을 먼저 최소 히프로 변환 다음, 작은 원소부터 차례대로 추출하여 정렬하는 방법
• 1차원 배열로도 구현 가능

구현1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0

typedef struct HeapElementType {
    int key;
    char data;
}HeapNode;

typedef struct ArrayHeapType {
    int maxElementCount;//최대 노드 개수
    int currentElementCount;//현재 노드 개수
    HeapNode* pElement;//노드 저장을 위한 1차원 array
}ArrayMaxHeap, ArrayMinHeap;

ArrayMaxHeap* createArrayMaxHeap(int maxElementCount) {
    ArrayMaxHeap* pReturn = NULL;
    int i = 0;
    if (maxElementCount > 0) {
        pReturn = (ArrayMaxHeap*)malloc(sizeof(ArrayMaxHeap));
        if (pReturn != NULL) {
            pReturn->maxElementCount = maxElementCount;
            pReturn->currentElementCount = 0;
            pReturn->pElement = (HeapNode*)malloc(sizeof(HeapNode) * (maxElementCount + 1));
            if (pReturn->pElement == NULL) {
                printf("오류, 2번째 메모리 할당, createArrayList()\n");
                free(pReturn);
                return NULL;
            }
            memset(pReturn->pElement, 0, sizeof(HeapNode) * (maxElementCount + 1));
        }
        else {
            printf("오류, 메모리 할당, createArrayList()\n");
        }
    }
    else {
        printf("최대 원소 개수는 0보다 커야 합니다\n");
    }
    return pReturn;
}
void insertMinHeapAH(ArrayMinHeap* pHeap, HeapNode element) {
    int i = 0;
    if (pHeap != NULL) {
        if (pHeap->currentElementCount == pHeap->maxElementCount) {//히프의 크기를 초과하여 저장하는지 점검
            printf("오류, 히프가 가득찼습니다 [%d], insertMaxHeapAH()\n", pHeap->maxElementCount);
        }
        pHeap->currentElementCount++;//현재 노드 개수를 1증가
        i = pHeap->currentElementCount;//변수i는 현재 히프에서의 마지막 노드를 가르키는 위치 인덱스
        while ((i != 1) && (element.key < pHeap->pElement[i / 2].key)) {//부모 노드와 키 값 비교
            pHeap->pElement[i] = pHeap->pElement[i / 2];
            i /= 2;
        }
        pHeap->pElement[i] = element;
    }
}
HeapNode* deleteMinHeapAH(ArrayMaxHeap* pHeap) {
    HeapNode* pReturn = NULL;
    HeapNode* pTemp = NULL;
    int i = 0;
    int parent = 0, child = 0;
    if (pHeap != NULL && pHeap->currentElementCount > 0) {//현재 반환 가능한 노드가 있는지 점검
        pReturn = (HeapNode*)malloc(sizeof(HeapNode));
        if (pReturn == NULL) {//반환되는 노드에 대한 메모리 할당 및 점검
            printf("오류, 메모리 할당, deleteMaxHeapAH()\n");
            return NULL;
        }
        *pReturn = pHeap->pElement[1];//루트 노드가 반환되는 노드임. 반환되는 노드의 값으로 기존 루트 노드의 값을 대입
        i = pHeap->currentElementCount;//히프의 제일 마지막 위치 인덱스
        pTemp = &(pHeap->pElement[i]);//히프의 제일 마지막 노드를 가리킴
        pHeap->currentElementCount--;//현재 노드 개수 1개 감소

        parent = 1;//루프가 시작되는 곳은 루트 노드
        child = 2;//루트 노드의 왼쪽 자식 노드
        while (child <= pHeap->currentElementCount) {//히프의 제일 마지막 위치에 있는 노드를 만날 때까지
            if ((child < pHeap->currentElementCount) && (pHeap->pElement[child].key > pHeap->[child + 1].key)) {
                child++;//왼쪽 자식노드보다 오른쪽 자식노드의 키 값이 더 크다면, 오른쪽 자식 노드가 비교 대상이 되도록 위치 인덱스 child를 수정
            }
            if (pTemp->key < pHeap->pElement[child].key) {
                break;//히프의 제일 마지막 노드와 현재 노드의 키 값을 비교하여 만약 마지막 노드의 키 값이 현재 노드보다 크거나 같다면 루프를 빠져 나온다. 이 위치에 삽입
            }
            pHeap->pElement[parent] = pHeap->pElement[child];//현재의 노드를 부모노드의 위치로 한 칸 이동
            parent = child;//아래 레벨로 이동
            child *= 2;
        }
        pHeap->pElement[parent] = *pTemp;
    }
    return pReturn;
}
void deleteArrayMinHeap(ArrayMaxHeap* pHeap) {
    if (pHeap != NULL) {
        if (pHeap->pElement != NULL) {
            free(pHeap->pElement);
        }
        free(pHeap);
    }
}
void heapSort(int value[], int count) {
    int i = 0;
    ArrayMinHeap* pHeap = NULL;
    pHeap = createArrayMinHeap(8);
    if (pHeap != NULL) {
        for (i = 0; i < count; i++) {
            HeapNode node;
            node.key = value[i];
            insertMinHeapAH(pHeap, node);
        }
        for (i = 0; i < count; i++) {
            HeapNode* pNode = deleteMinHeapAH(pHeap);
            if (pNode != NULL) {
                value[i] = pNode->key;
                free(pNode);
            }
        }
        deleteArrayMinHeap(pHeap);
    }
}

구현2

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_ELEMENT 200
#define SIZE 8

typedef struct {
    int key;
}element;
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;
HeapType* create() {
    return (HeapType*)malloc(sizeof(HeapType));
}
void init(HeapType* h) {
    h->heap_size = 0;
}
void insert_max_heap(HeapType* h, element item) {
    int i;
    i = ++(h->heap_size);
    while ((i != 1) && (item.key > h->heap[i / 2].key)) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;
}
element delete_max_heap(HeapType* h) {
    int parent, child;
    element item, temp;
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    while (child <= h->heap_size) {
        //현재 노드의 자식노드 중 더 큰 자식노드 찾기
        if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key))
            child++;
        if (temp.key >= h->heap[child].key)
            break;
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}
void heap_sort(element a[], int n) {
    int i;
    HeapType* h;
    h = create();
    init(h);
    for (i = 0; i < n; i++) {
        insert_max_heap(h, a[i]);
    }
    for (i = (n - 1); i >= 0; i--) {
        a[i] = delete_max_heap(h);
    }
    free(h);
}
int main(void) {
    element list[SIZE] = { 23,56,11,9,56,99,27,34 };
    heap_sort(list, SIZE);
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", list[i].key);
    }
    printf("\n");
}

특징

• 최선, 평균, 최악: $O(nlogn)$
• 히프 자료구조를 이용하여 히프에 삽입, 삭제만을 통해 정렬
• 히프 생성에 필요한 추가 메모리 필요
• 안정성 유지되지 않음

14235: 크리스마스 선물

문제

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다. 이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

입력

첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000) 다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

출력

a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

예제 입력

5
0
2 3 2
0
0
0

예제 출력

-1
3
2
-1

풀이방법

산타는 아이들을 만날 때마다 현재 들고있는 가장 가치가 큰 선물 하나를 선물해준다는 문구에서 우선순위 큐를 사용해야함을 직감했다. 그래서 선물의 가치를 우선순위 큐에 입력하고 아이를 만날 때마다 top에 위치한 선물을 반환하고 삭제한다. 만약 선물이 없다면 -1을 반환한다.

코드

#include<iostream>
#include <stdlib.h>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int main() {
    int n,a,v;
    priority_queue<int> pq;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        for (int j = 0; j < a; j++) {
            scanf("%d", &v);
            pq.push(v);
        }
        if (a == 0) {
            if (pq.size() > 0) {
                printf("%d\n", pq.top());
                pq.pop();
            }
            else {
                printf("-1\n");
            }
        }
    }
}

후기

이 문제는 우선순위 큐를 사용해야한다는 것을 알았다면 쉬운 문제이다.

17503: 맥주 축제

문제

내일부터 N일 동안 대구광역시에서 맥주 축제가 열립니다! 이 축제에서는 무려 K종류의 맥주를 무료로 제공합니다. 축제 주최자는 축제에서 더 많은 참가자들이 다양한 종류의 맥주를 즐겼으면 합니다. 그래서 축제에서 참가자들은 하루에 맥주 1병만 받을 수 있고, 이전에 받았던 종류의 맥주는 다시 받을 수 없습니다. 맥주를 정말로 사랑하는 대학생 전씨는 무료 맥주 소식에 신이 났습니다. 전씨는 이 맥주 축제에 참가해 총 N일 동안 맥주 N병을 마시려 합니다. 하지만 전씨에게는 큰 고민이 있었습니다. 전씨는 맥주를 사랑하지만, 도수가 높은 맥주를 마시면 기절하는 맥주병이 있습니다. 전씨는 맥주를 마시다 기절하면 늦잠을 자 다음 날 1교시 수업에 결석해 F를 받게 될 수도 있습니다. 전씨는 고민을 해결하기 위해 천재석사 현씨과 천재박사 승씨에게 자신의 간을 강력하게 만들어달라고 부탁했습니다. 하지만 간을 강력하게 만드는 비용이 너무 비싸서, 전씨는 간을 가능한 한 조금만 강화할 계획을 세웠습니다. 우선, K종류의 맥주에 각각 '선호도'와 '도수 레벨'을 매겼습니다. 선호도는 전씨가 해당 맥주를 얼마나 좋아하는지를 나타내는 수치이고, 도수 레벨은 해당 맥주의 도수가 얼마나 강한지를 나타내는 수치입니다. 편의상 전씨는 선호도와 도수 레벨을 정수로 매겼습니다. 만약, 마시는 맥주의 도수 레벨이 전씨의 간 레벨보다 높으면 맥주병이 발병해 기절해버리고 맙니다. 또한, 전씨는 맥주병에 걸리지 않으면서도 자신이 좋아하는 맥주를 많이 마시고 싶어합니다. 따라서, 마시는 맥주 N개의 선호도 합이 M이상이 되게 하려 합니다. 거창한 계획을 세운 전, 현, 승 세 사람은 서로 머리를 맞대고 고민하다가, 스트레스를 받아 연구를 집어치고 맥주를 마시러 떠나버렸습니다. 이를 본 여러분은 세 사람을 대신해 조건을 만족하는 간 레벨의 최솟값을 출력하는 프로그램을 만들어 주려고 합니다. 세 사람을 도와주세요!

입력

첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M < 231) 과, 마실 수 있는 맥주 종류의 수 K (N ≤ K ≤ 200,000) 가 주어집니다. 다음 K개의 줄에는 1번부터 K번 맥주의 선호도 vi (0 ≤ vi ≤ 10,000) 와 도수 레벨 ci (1 ≤ ci < 231) (vi, ci는 정수) 이 공백을 사이에 두고 주어집니다. 1번부터 K번 맥주의 종류는 모두 다릅니다.

출력

첫 번째 줄에 주어진 선호도의 합 M을 채우면서 N개의 맥주를 모두 마실 수 있는 간 레벨의 최솟값을 출력합니다. 만약 아무리 레벨을 올려도 조건을 만족시킬 수 없으면 첫 번째 줄에 "-1" 하나만 출력하고 더 이상 아무것도 출력하지 않아야 합니다.

예제 입력1

3 9 5
2 5
4 6
3 3
4 3
1 4

예제 출력1

5

예제 입력2

1 100 2
99 10
99 10

예제 출려2

-1

풀이방법

맥주의 도수 레벨로 간 레벨의 최솟값을 알아낼 수 있으므로 맥주들의 도수값들을 기준으로 오름차순 정렬한다. 정렬을 한 후 최소 도수 레벨부터 시작하여 우선순위 큐에 저장한다. 우선순위 큐는 자동으로 오름차순 정렬하므로 차후에 pop했을 때 가장 작은 레벨의 선호도가 최대가 되도록 하기 위해 음수로 저장한다. 선호도는 또 다른 변수에 누적하여 합한다. 우선순위 큐의 크기가 마실 수 있는 맥주의 개수보다 커지면 우선순위 큐에서 가장 큰 값(맥주의 선호도가 가장 작은 값)을 빼준다. 그 합이 기준 선호도보다 크거나 같고 우선순위 큐의 사이즈가 마실 수 있는 맥주의 개수와 같을 때는 해당 맥주의 도수 레벨이 간 레벨이 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int main() {
    int n,k,m;
    int v, c;
    int sum = 0;
    vector<pair<int, int>> vc;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &v, &c);
        vc.push_back({ c,v });
    }
    sort(vc.begin(), vc.end());

    priority_queue<int>pq;
    for (int i = 0; i < k; i++) {
        pq.push(-vc[i].second);
        sum += vc[i].second;
        if (pq.size() > n) {
            sum += pq.top();
            pq.pop();
        }
        if (pq.size() == n && sum >= m) {
            printf("%d", vc[i].first);
            return 0;
        }
    }
    printf("-1");
}

후기

이 문제의 연관 알고리즘으로 있는 이분 탐색을 몰라 고민을 조금 한 문제이다. 근데 막상 풀고보면 이분 탐색이 쓰일 필요는 없는거 같다. 오히려 우선순위 큐를 효율적으로 잘 사용하는게 이 문제풀이의 핵심인 거 같다.

14241: 슬라임 합치기

문제

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다. 모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다. 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력1

2
3 4

예제 출력1

12

예제 입력2

3
2 2 2

예제 출력2

12

예제 입력3

3
1 2 3

예제 출력3

11

예제 입력4

3
3 1 2

예제 출력4

11

풀이방법

슬라임의 크기를 vector에 입력하여 오름차순 정렬한다. 맨 마지막에 위치한 두 슬라임의 크기가 가장 최대일 것이므로 하나를 pop하고 다음을 pop하여 두개를 더하여 vector에 다시 넣어주고 정렬해준다. pop해준 두 숫자의 곱도 점수에 더해준다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
int main() {
    int n,num;
    int sum = 0;
    vector<int> arr;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        arr.push_back(num);
    }
    while (n > 1) {
        sort(arr.begin(), arr.end());

        int x = arr.back();
        arr.pop_back();

        int y = arr.back();
        arr.pop_back();

        arr.push_back(x + y);

        n--;
        sum += x * y;
    }
    printf("%d", sum);
}

후기

처음에는 vector가 아닌 배열을 사용할려고 했는데 숫자를 삭제하고 다시 삽입하는 작업이 번거러워서 vector를 사용하였다. 또한 vector에서 마지막 값을 동시에 반환하고 삭제하는 함수가 없어 먼저 back함수를 사용하여 값을 저장하고 그 값을 pop_back을 사용하여 삭제하는 작업을 x,y에 대해 순서대로 수행해줌에 유의하자.

12018: Yonsei TOTO

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다. 성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다. 그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100) (단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

예제 입력

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

예제 출력

4

풀이방법

각 과목별로 신청한 학생들의 마일리지를 배열에 저장한 다음 내림차순 정렬을 해준다. 내림차순 정렬한 배열에서 수강가능한 마지막 번째 학생의 마일리지를 다른 배열에 따로 저장해둔다. 수강가능한 마지막 번째 학생이 가장 과목을 수강할 수 있는 가장 최소의 마일리지를 입력했기 때문이다. 최소의 마일리지를 누적하여 최대의 과목을 수강하는 이 문제 풀이의 전략이다. 다른 배열에 저장할 때 유의해야할 점은 입력가능한 마일리지의 최소가 1이라는 점이다. 새로운 배열에 모두 저장이 되면 오름차순 정렬하여 기준 마일리지를 초과하면 결과를 반환한다.

코드

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int main() {
    int n, m;
    int p, l;
    int j,i;
    int sum[101] = { 0, };
    int count = 0,ret=0;
    int arr[101][101] = { 0, };

    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%d %d", &p, &l);
        for (j = 0; j < p; j++) {
            scanf("%d", &arr[i][j]);
        }
        if (p < l)
            sum[i] = 1;
        else {
            sort(arr[i], arr[i] + p, greater<int>());
            sum[i] = arr[i][l - 1];
        }
    }

    sort(sum, sum + n, less<int>());

    for (i = 0; i < n; i++) {
        if ((count+sum[i])> m)
            break;
        count += sum[i];
        ret+=1;
    }
    printf("%d\n", ret);
}

후기

많이 어려운 문제는 아니지만 여러가지 조건에 유의해서 풀어야하는 문제이다.

15903: 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!
아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.
   이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.
   아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

   입력

   첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

   출력

   첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

   예제 입력1

   3 1 3 2 6

   예제 출력1

   16

   예제 입력2

   4 2 4 2 3 1

   예제 출력2

   19

풀이방법

먼저 배열에 입력된 값들을 (오름차순)정렬 한 후 첫 번째로 작은 값과 두 번째로 작은 값을 더하여 그 값들로 다시 첫 번째와 두 번째 값들을 덮어준다. 새로운 숫자가 또 입력됬으므로 다시 정렬해주고 덮어주는 작업을 반복해준다. 그리고 최종적으로 모든 카드의 값들을 합하여 반환한다.

코드

방법1 : C언어

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
long long* InPlaceSelectionSort(long long arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        int p = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[p]) {
                p = j;
            }
        }
        long long temp = arr[p];
        arr[p] = arr[i];
        arr[i] = temp;
    }
    long long x = arr[0], y = arr[1];
    long long sum = x + y;
    arr[0] = sum;
    arr[1] = sum;
    return arr;
}
long long card_sum(long long arr[], int m, int n) {
    long long sum = 0;
    for (int i = 0; i < m; i++) {
        arr = InPlaceSelectionSort(arr, n);
    }
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}
int main() {
    int n, m, i;
    long long arr[1001];
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }
    printf("%lld\n", card_sum(arr, m, n));
    return 0;
}

방법2 : C++언어

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int main() {
    int n, m;
    long long arr[1001];
    long long ret = 0;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }
    for (int j = 0; j < m; j++) {
        sort(arr, arr + n);
        long long tmp = arr[0] + arr[1];
        arr[0] = tmp;
        arr[1] = tmp;
    }
    for (int i = 0; i < n; i++) {
        ret += arr[i];
    }
    printf("%lld", ret);
}

후기

이 문제는 학교에서 배우는 선택정렬과 삽입정렬을 연습하기 위해 우선순위 큐 분류에서 문제를 찾다가 발견하게되었다. 내가 제시한 첫번째 코드로 하면 시간초과가 뜨긴하지만 나의 원래 취지는 선택정렬을 사용하고자 한것이므로 결과와 상관없이 개시는 해본다. 두번째 코드는 c++에서 sort함수를 사용하여 훨씬 빠르고 수월하게 정답이 나왔다.

• 더 따라갈 간선이 없을 경우 이전으로 돌아간다
  • 재귀호출 사용 - 지금까지 거쳐온 정점들을 모두 저장

    인접리스트로 표현된 그래프의 깊이 우선 탐색

    #include <iostream>
    #include <vector>
    using namespace std;
    //그래프의 인접 리스트 표현
    vector<vector<int>>adj;
    //각 정점을 방문했는지 여부
    vector<bool>visited;
    //깊이 우선 탐색
    void dfs(int here) {
    cout << "DFS visits " << here << endl;
    visited[here] = true;
    //모든 인접 정점을 순회하면서
    for (int i = 0; i < adj[here].size(); i++) {
       int there = adj[here][i];
       //아직 방문한 적이 없다면 방문한다.
       if (!visited[there])
           dfs(there);
    }
    //더이상 방문할 정점이 없으니, 재귀 호출을 종료하고 이전 정점으로 돌아간다.
    }
    void dfsAll() {
    //visited를 모두 false로 초기화한다.
    visited = vector<bool>(adj.size(), false);
    //모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
    for (int i = 0; i < adj.size(); i++) {
       if (!visited[i])
           dfs(i);
    }
    }

• dfs() : 아직 방문하지 않은 정점으로 이어지는 간선을 만날경우 재귀호출을 통해 해당 정점 방문
• dfsAll() : 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에 dfs()만으로는 모든 정점을 순서대로 발견하지 못할 수 있음.

깊이 우선 탐색 사용 예

두 정점이 서로 연결되어 있는가 확인

• 어떤 정점 u에 대해 dfs(u)를 수행하면, u에서부터 간선들을 통해 갈 수 있는 모든 정점 방문
• dfs(u)수행 후 visited[]를 참조하면 u로부터 각 정점에 갈 수 있는지 확인 가능

연결된 부분집합의 개수 세기

• component/요소: 무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 조각으로 쪼개져 있는 경우
• dfsAll()에서 dfs()를 호출하는 횟수를 세면 몇 개의 컴포넌트로 나뉘어 있는지 확인 가능

위상 정렬

• 의존성이 있는 작업들이 주어질 때, 어떤 순서롤 수행해야 하는지 계산
• 작업 B를 하기 전에 반드시 작업 A를 해야 한다 ⇔ 작업 B가 작업 A에 의존한다

-의존성 그래프

• 정점 : 작업 , 간선 : 작업 간의 의존관계 으로 표현한 방향 그래프
• 사이클이 없는 방향 그래프 (DAG)

-위상 정렬

• 그래프의 정점들을 일렬로 늘어놓고, 왼쪽에서부터 하나씩 수행하도록 정점들을 배열
• DAG의 정점들을 배열
• dfsAll()을 수행하면 dfs()가 종료할 때마다 현재 정점의 번호 기록
• dfsAll() 종료 후 기록된 순서 뒤집기
  • dfs()가 늦게 종료한 정점일수록 정렬 결과의 앞에 옴

오일러 서킷

• 오일러 서킷(Eulerian circuit) : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제

-오일러 서킷의 존재 조건

• 그래프의 모든 정점들이 짝수점(차수가 짝수인 정점) 이어야함
• 하나의 컴포넌트에 포함된 그래프

  구현

  #include <iostream>
  #include <vector>
  using namespace std;
  //그래프의 인접 행렬 표현. adj[i][j]=i와 j사이의 간선의 수
  vector<vector<int>> adj;
  //무향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷 계산
  //결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다
  void getEulerCircuit(int here, vector<int>& circuit) {
    for (int there = 0; there < adj[here].size(); there++) {
        while (adj[here][there] > 0) {
            adj[here][there]--;
            adj[there][here]--;
            getEulerCircuit(there, circuit);
        }
    }
    //재귀호출이 끝나고 반환 할 때 추가
    circuit.push_back(here);
    //경로의 끝점부터 역순으로 간선들이 추가
  }

오일러 트레일

• 오일러 트레일(Eulerian trail) : 오일러 서킷처럼 그래프의 모든 간선을 정확히 한 번씩 지나지만, 시작점과 끝점이 다른 경로

-오일러 트레일의 존재 조건

• 시작점과 끝점을 제외한 그래프의 모든 정점들은 짝수점(차수가 짝수인 정점) 이어야함
  • 시작점과 끝점은 홀수점(차수가 홀수인 정점)이어야함
  • 시작점과 끝점을 잇는 간선을 추가하여 오일러 서킷을 구한 후 그 간선을 끊으면 오일러 트레일을 얻을 수 있음

문제

아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른 것인지를 알고 싶어합니다. 일리노이 존스는 이 언어에서는 알파벳들의 순서가 영어와 서로 다를 뿐, 사전의 단어들은 사전 순서대로 배치되어 있다는 가설을 세웠습니다. 이 가설이 사실이라고 가정하고, 단어의 목록으로부터 알파벳의 순서를 찾아내려고 합니다. 예를 들어 다섯 개의 단어 gg, kia, lotte, lg, hanhwa 가 사전에 순서대로 적혀 있다고 합시다. gg가 kia보다 앞에 오려면 이 언어에서는 g가 k보다 앞에 와야 합니다. 같은 원리로 k는 l앞에, l은 h앞에 와야 한다는 것을 알 수 있지요. lotte 가 lg 보다 앞에 오려면 o가 g 보다 앞에 와야 한다는 것도 알 수 있습니다. 이들을 종합하면 다섯 개의 알파벳 o, g, k, l, h 의 상대적 순서를 알게 됩니다. 사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 사전에 포함된 단어의 수 N (1 <= N <= 1000) 이 주어집니다. 그 후 N 줄에 하나씩 사전에 포함된 단어가 순서대로 주어집니다. 각 단어는 알파벳 소문자로 구성되어 있으며, 길이는 1 이상 20 이하입니다. 중복으로 출현하는 단어는 없습니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 만약 알파벳들의 순서에 모순이 있다면 "INVALID HYPOTHESIS"를 출력하고, 모순이 없다면 26개의 소문자로 알파벳들의 순서를 출력합니다. 만약 가능한 순서가 여러 개 있다면 아무 것이나 출력해도 좋습니다.

예제 입력

3
3
ba
aa
ab
5
gg
kia
lotte
lg
hanhwa
6
dictionary
english
is
ordered
ordinary
this

예제 출력

INVALID HYPOTHESIS
ogklhabcdefijmnpqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

First Thoughts

먼저 단어를 벡터에 입력한다. 입력받은 벡터에서 단어를 양옆으로 비교하는데 두 단어가 서로 다른 알파벳을 가르킬 때까지 비교한다. 그리고 알파벳의 순서를 저장하는 벡터에서 특정 알파벳이 있는지 찾고 그를 바탕으로 새로운 알파벳을 삽입할 위치를 탐색한다.

My Code

#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
vector <string> dic;
vector <char> alphabet;
void order1() {
    int i;
    for (i = 0; i < (dic.size()-1); i++) {
        int j = 0;
        while (j<dic[i].size()&&j<dic[i+1].size()&&dic[i][j] == dic[i + 1][j])
            j++;
        if (j == dic[i].size() || j== dic[i + 1].size())
            continue;
        vector<char>::iterator iter1,iter2;
        iter1 = find(alphabet.begin(), alphabet.end(), dic[i][j]);
        iter2 = find(alphabet.begin(), alphabet.end(), dic[i + 1][j]);
        if (iter1 != alphabet.end() && iter2 == alphabet.end()) {
            ++iter1;
            alphabet.insert(iter1, dic[i + 1][j]);
        }
        else if (iter1 == alphabet.end() && iter2 != alphabet.end()) 
            alphabet.insert(iter2, dic[i][j]);
        else if (iter1 == alphabet.end() && iter2 == alphabet.end()) {
                alphabet.push_back(dic[i][j]);
                alphabet.push_back(dic[i+1][j]);
        }
        else {
            if (iter1 < iter2)
                continue;
            else {
                printf("INVALID HYPOTHESIS\n");
                return;
            }
        }
    }
    for (char a = 'a'; a <= 'z' ; a++) {
        if(find(alphabet.begin(),alphabet.end(),a)==alphabet.end())
            alphabet.push_back(a);
    }
    for (int i = 0; i < alphabet.size(); i++) {
        printf("%c", alphabet[i]);
    }
    printf("\n");
}
int main() {
    int C;
    int n;
    string word;
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> word;
            dic.push_back(word);
        }
        order1();
        dic.clear();
        alphabet.clear();
    }
}

Answer Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
vector<vector<int>> adj;
void makeGraph(const vector<string>& words) {
    adj = vector<vector<int>>(26, vector<int>(26, 0));
    for (int j = 1; j < words.size(); j++) {
        int i = j - 1;
        int len = min(words[i].size(), words[j].size());
        for (int k = 0; k < len; k++) {
            if (words[i][k] != words[j][k]) {
                int a = words[i][k] - 'a';
                int b = words[j][k] - 'a';
                adj[a][b] = 1;
                break;
            }
        }
    }
}
vector<int> seen, order;
void dfs(int here) {
    seen[here] = 1;
    for (int there = 0; there < adj.size(); there++) {
        if (adj[here][there] && !seen[there]) {
            dfs(there);
        }
    }
    order.push_back(here);
}
//adj에 주어진 그래프를 위상정렬
//그래프기 DAG가 아니라면 빈 벡터 반환
vector<int>topologicalSort() {
    int m = adj.size();
    seen = vector<int>(m, 0);
    order.clear();
    for (int i = 0; i < m; i++) {
        if (!seen[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    //만약 그래프가 DAG가 아니라면 정렬 결과에 역방향 간선이 있음
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (adj[order[j]][order[i]])
                return vector<int>();
        }
    }
    //없다면 깊이 우선 탐색에서 얻은 결과 반환
    return order;
}
void print_order(vector<int> order) {
    if (order.empty())
        printf("INVALID HYPOTHESIS\n");
    else {
        for (int i = 0; i < order.size(); i++) {
            printf("%c", order[i]+'a');
        }
        printf("\n");
    }
}
int main() {
    int C;
    int n;
    vector<string>words;
    string s;
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> s;
            words.push_back(s);
        }
        makeGraph(words);
        print_order(topologicalSort());
        words.clear();
    }
}

Difference & Faults

주제에서 완전 벗어난 풀이

항상 문제를 풀기 전에 내가 지금 어떤 내용을 공부하고 있는지 어떤 내용을 배웠는지 생각하며 풀어야한다. 안타깝게도 이번 문제에서 나는 무작정 내가 풀고 싶은대로 풀었다. 아이디어 자체는 매우 직관적이고 쉽지만 나의 풀이는 틀렸다. 정확한 반례를 찾지는 못했지만 아마 알파벳을 insert하는 부분에서 틀린 거 같다. 나는 insert하는 위치를 항상 바로 뒤나 바로 앞으로 하였는데 사실상 내가 넣는 위치보다 더 앞이거나 더 뒤일 수도 있는것이다. 그래서 나의 코드대로하면 맞는 순서를 invalid라고 출력할 수 있는 것이다.

인접행렬의 사용

해제 코드는 두 알파벳 사이의 관계를 인접행렬로 표현하였다. 그 과정에서 알파벳을 수치화시켰는데 이 과정이 답을 보면 뻔하지만 막상 내가 생각하려고 하면 힘든 거 같다. 그래서 문자와 문자 사이의 관계를 인덱스화 시켰다는 점도 눈여겨볼만하다.

위상정렬

위상정렬에 대한 개념확립과 구현에 대한 이해가 더 필요할 거 같다. 이는 "알고리즘 이론" 파트에서 참고하길 바란다.

Impressions

문자들의 관계를 인접행렬로 표현하고 이를 그래프로 표현한 것이 신기하다. 또한 깊이 우선 탐색을 이용하여 위상 정렬을 하는 것이 아직은 이해가 안가지만 이 또한 새로운 부분이었다.

Summary

위상정렬을 잘 이해하고 있는지 코드로 구현이 가능한지 확인하는 문제같다. 위상정렬을 전에 접해본 사람이라면 쉽게 풀 수 있는 문제같다. 일단 그래프를 처음 배워보는 것이니까 가벼운 마음으로 한 번 보고 복습할 때 완전히 이해가되길 바란다.

• 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문
• 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘
• 어떤 간선이 사용되었는지, 어떤 순서로 정점들이 방문되었는지 → 그래프의 구조

-탐색 방법

• 깊이 우선 탐색(depth first search: DFS)
• 너비 우선 탐색(breath first search: BFS)

깊이 우선 탐색

• 순환 호출 이용
• 명시적인 스택 사용

인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FAlSE 0
#define MAX_VERTICES 50
typedef struct GraphType {
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
void init(GraphType* g) {
    int r, c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++) {
        for (c = 0; c < MAX_VERTICES; c++) {
            g->adj_mat[r][c] = 0;
        }
    }
}
//정점 삽입
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
//간선 삽입
void insert_edge(GraphType* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
//인접 행렬로 표현된 그래프에 대한 깊이 탐색 그래프
void dfs_mat(GraphType* g, int v) {
    int w;
    visited[v] = TRUE;
    printf("정점 %d -> ", v);
    for (w = 0; w < g->n; w++) {
        if (g->adj_mat[v][w] && !visited[w])
            dfs_mat(g, w);
    }
}
int main() {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g);
    for (int i = 0; i < 4; i++)
        insert_vertex(g, i);
    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 3);

    printf("깊이 우선 탐색\n");
    dfs_mat(g, 0);
    printf("\n");
    free(g);
}

인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FAlSE 0
#define MAX_VERTICES 50

typedef struct GraphNode{
    int vertex;
    struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
    int n;
    GraphNode* adj_list[MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
void init(GraphType* g) {
    int r;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++) {
            g->adj_list[r] = NULL;
    }
}
//정점 삽입
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
//간선 삽입
void insert_edge(GraphType* g, int u, int v) {
    GraphNode* node;
    if (u >= g->n || v >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;

}
//인접 행렬로 표현된 그래프에 대한 깊이 탐색 그래프
void dfs_list(GraphType* g, int v) {
    GraphNode* w;
    visited[v] = TRUE;
    printf("정점 %d -> ", v);
    for (w = g->adj_list[v]; w ; w=w->link) {
        if (!visited[w->vertex])
            dfs_list(g, w->vertex);
    }
}
int main() {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g);
    for (int i = 0; i < 4; i++)
        insert_vertex(g, i);
    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 3);

    printf("깊이 우선 탐색\n");
    dfs_list(g, 0);
    printf("\n");
    free(g);
}

c++ 구현

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int number = 7;
int c[7];
vector<int>a[8];
void dfs(int x) {
    if (c[x])
        return;
    c[x] = true;
    cout << x << ' ';
    for (int i = 0; i < a[i].size(); i++) {
        int y = a[x][i];
        dfs(y);
    }
}

너비 우선 탐색

• 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조 필요 → 큐 사용

인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
}QueueType;
//오류 함수
void error(char* message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}
//초기화 함수
void queue_init(QueueType* q) {
    q->front = q->rear = 0;
}
//공백 상태 검출 함수
int is_empty(QueueType* q) {
    return (q->front == q->rear);
}
//포화 상태 검출 함수
int is_full(QueueType* q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
void enqueue(QueueType* q, element item) {
    if (is_full(q))
        error("큐가 포화상태입니다\n");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}
//삭제 함수
element dequeue(QueueType* q) {
    if (is_empty(q))
        error("큐가 공백상태입니다\n");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}
#define MAX_VERTICES 50
typedef struct GraphType {
    int n;//정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
//그래프 초기화
void graph_init(GraphType* g) {
    int r, c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++) {
        for (c = 0; c < MAX_VERTICES; c++) {
            g->adj_mat[r][c] = 0;
        }
    }
}
//정점 삽입 연산
void insert_vertex(GraphType* g,int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
//간선 삽입 연산
void insert_edge(GraphType* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
void bfs_mat(GraphType* g, int v) {
    int w;
    QueueType q;
    queue_init(&q);//큐 초기화
    visited[v] = TRUE;//정점 v 방문 표시
    printf("%d 방문 -> ", v);
    enqueue(&q, v);//시작 정점을 큐에 저장
    while (!is_empty(&q)) {
        v = dequeue(&q);//큐에 정점 추출
        for (w = 0; w < g->n; w++) {//인접 정점 탐색
            if (g->adj_mat[v][w] && !visited[w]) {
                visited[w] = TRUE;//방문 표시
                printf("%d 방문 -> ", w);
                enqueue(&q, w);//방문한 정점을 큐에 저장
            }
        }
    }
}
int main(void) {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    graph_init(g);
    for (int i = 0; i < 6; i++) {
        insert_vertex(g, i);
    }
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 0, 4);
    insert_edge(g, 4, 5);
    insert_edge(g, 1, 5);

    printf("너비 우선 탐색\n");
    bfs_mat(g, 0);
    printf("\n");
    free(g);
}

인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
}QueueType;
//오류 함수
void error(char* message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}
//초기화 함수
void queue_init(QueueType* q) {
    q->front = q->rear = 0;
}
//공백 상태 검출 함수
int is_empty(QueueType* q) {
    return (q->front == q->rear);
}
//포화 상태 검출 함수
int is_full(QueueType* q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
void enqueue(QueueType* q, element item) {
    if (is_full(q))
        error("큐가 포화상태입니다\n");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}
//삭제 함수
element dequeue(QueueType* q) {
    if (is_empty(q))
        error("큐가 공백상태입니다\n");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}
#define MAX_VERTICES 50
typedef struct GraphNode {
    int vertex;
    struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
    int n;
    GraphNode* adj_list[MAX_VERTICES];
}GraphType;
void graph_init(GraphType* g) {
    int v;
    g->n = 0;
    for (v = 0; v < MAX_VERTICES; v++) {
        g->adj_list[v] = NULL;
    }
}
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
void insert_edge(GraphType* g, int u, int v) {
    GraphNode* node;
    if (u >= g->n || v >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}
int visited[MAX_VERTICES];
void bfs_list(GraphType* g, int v) {
    GraphNode* w;
    QueueType q;
    queue_init(&q);//큐 초기화
    visited[v] = TRUE;//정점 v 방문 표시
    printf("%d 방문 -> ", v);
    enqueue(&q, v);//시작정점을 큐에 저장
    while (!is_empty(&q)) {
        v = dequeue(&q);//큐에 저장된 정점 선택
        for (w = g->adj_list[v]; w; w = w->link) {//인점 정점 탐색
            if (!visited[w->vertex]) {//미방문 정점 탐색
                visited[w->vertex] = TRUE;//방문 표시
                printf("%d 방문 -> ", w->vertex);
                enqueue(&q, w->vertex);//정점을 큐에 삽입 
            }
        }
    }
}
int main(void) {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    graph_init(g);
    for (int i = 0; i < 6; i++) {
        insert_vertex(g, i);
    }
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 0, 4);
    insert_edge(g, 4, 5);
    insert_edge(g, 1, 5);
    printf("너비 우선 탐색\n");
    bfs_list(g, 0);
    printf("\n");
    free(g);
}

c++ 구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void bfs(int start) {
    queue<int>q;
    q.push(start);
    c[start] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for (int i = 0; i < a[x].size(); i++) {
            int y = a[x][i];
            if (!c[y]) {
                q.push(y);
                c[y] = true;
            }
        }
    }
}

구현

#include <stdio.h>
#pragma warning(disable:4996)
#define MAX_VERTICES 50
typedef struct GraphType {
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;
//그래프 초기화
void init(GraphType* g) {
    int r, c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++) {
        for (c = 0; c < MAX_VERTICES; c++) {
            g->adj_mat[r][c]=0;
        }
    }
}
//정점 삽입 연산 
void insert_vertex(GraphType* g,int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
//간선 삽입 연산
void insert_edge(GraphType* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
//인접 행렬 출력 함수
void print_adj_mat(GraphType* g) {
    for (int i = 0; i < g->n; i++) {
        for (int j = 0; j < g->n; j++) {
            printf("%2d", g->adj_mat[i][j]);
        }
        printf("\n");
    }
}
void main() {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g);
    for (int i = 0; i < 4; i++) {
        insert_vertex(g, i);
    }
    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 3);
    print_adj_mat(g);
    free(g);
}

인접 리스트

구현

#include <stdio.h>
#pragma warning(disable:4996)
#define MAX_VERTICES 50
typedef struct GraphNode {
    int vertex;
    struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
    int n;
    GraphNode* adj_list[MAX_VERTICES];
}GraphType;
//그래프 초기화
void init(GraphType* g) {
    int v;
    g->n = 0;
    for (v = 0; v < MAX_VERTICES; v++) {
        g->adj_list[v] = NULL;
    }
}
//정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
//간선 삽입 연산, v를 u의 인접 리스트에 삽입
void insert_edge(GraphType* g, int u, int v) {
    GraphNode* node;
    if (u >= g->n || v >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];//연결리스트의 맨 처음에 삽입
    g->adj_list[u] = node;
}
void print_adj_list(GraphType* g) {
    for (int i = 0; i < g->n; i++) {
        GraphNode* p = g->adj_list[i];
        printf("정점 %d의 인접 리스트", i);
        while (p != NULL) {
            printf("-> %d", p->vertex);
            p = p->link;
        }
        printf("\n");
    }
}
int main() {
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g);
    for (int i = 0; i < 4; i++) {
        insert_vertex(g, i);
    }
    insert_edge(g, 0, 1);
    insert_edge(g, 1, 0);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 0);
    insert_edge(g, 0, 3);
    insert_edge(g, 3, 0);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 3, 2);
    print_adj_list(g);
    free(g);
}

그래프의 정의

• 정의: 그래프 G(V,E)/G=(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V(=v(G))와 이들을 연결하는 간선(edge)들의 집합 E(=E(G))로 구성된 자료구조
• 정점(vertex/node): 여러 가지 특성을 가질 수 있는 객체
• 간선(edge/link): 정점들 간의 관계

그래프의 종류

• 표현하고자하는 대상에 따라 여러가지 변형된 형태가 있음

i) 정점이나 간선에 추가적 속성을 부여한 경우

1. 방향 그래프/유향 그래프(directed graph)

   • 각 간선이 방향이라는 속성을 갖음
   • 간선에 방향성이 존재함
   • 정점 A에서 정점 B로 가는 간선 표현법 - <A,B> ≠ <B,A>

2. 무(방)향 그래프(undirected graph)

   • 간선에 방향이 없는 그래프
   • 양방향으로 갈 수 있음
   • 정점 A와 정점 B를 연결하는 간선 표현법 - (A,B) / (B,A)

+) 2-1. 연결 그래프(connected graph)

• 모든 정점쌍에 대하여 항상 경로가 존재

  2-2. 완전 그래프(complete graph)

• 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

• (정점의 수) = n , (각 정점의 차수) = n-1 , (간선의 수) = nX(n-1)/2

3. 가중치 그래프(weighted graph) / 네트워크(network)

   • 각 간선이 가중치(weight)라는 실수 속성을 갖음
   • 두 정점간의 연결 강도 나타냄

ii) 간선이나 정점의 형태에 제약을 둔 경우

1. 다중 그래프(multigraph)

   • 두 정점 사이에 두 개 이상의 간선이 있는 경우

2. 단순 그래프(simple graph)

   • 최대 한 개의 간선만 있는 그래프

3. 트리/루트 없는 트리(unrooted tree)

   • 부모 자식 관계가 없음
     • 무향 그래프
   • 간선을 통해 두 정점을 잇는 방법이 하나밖에 없음

4. 이분 그래프(bipartite graph)

   • 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재

5. 사이클 없는 방향 그래프(DAG - directed acyclic graph)

   • 두 가지 이상의 속성을 함께 가지는 경우
   • 방향 그래프
   • 한 점에서 출발해 자기자신으로 돌아오는 경로(사이클)가 존재하지 않는 경우

+) 6. 부분 그래프(subgraph)

• 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프
• 그래프 G의 부분 그래프 S
  • v(S) ⊆ V(G)
  • E(S) ⊆ E(S)

정점의 차수

• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점

-무방향 그래프

• 정점의 차수(degree) : 인접한 정점의 수
  • (모든 정점의 차수 합) = (간선 수) X 2

-방향 그래프

• 진입 차수(in-degree) : 외부에서 오는 간선의 개수
• 진출 차수(out-degree) : 외부로 향하는 간선의 개수

그래프의 경로

• 정의: 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것
• 단순 경로(simple path): 한 정점을 최대 한 번만 지나는 경로
• 사이클(cycle)/회로: 시작한 점에서 끝나는 경로
• 정점 s로부터 정점 e까지의 경로
  • 무방향 그래프 - (s,v1), (v1,v2),...,(vk,e)
  • 방향 그래프 - <s,v1>,<v1,v2>,...,<vk,e>

그래프의 사용 예

1. 철도망의 안정선 분석

• 문제: 어떤 철도망에서 한 역이 폐쇄되어 열차가 지나지 못할 경우 철도망 전체가 두 개 이상으로 쪼개질 가능성이 있는지, 있다면 어느 역이 그런 위험성을 갖고 있는지 분석

• 정점: 철도의 각 역

• 간선: 두 역 사이를 연결하는 철로

• 관련 알고리즘: 절단점 찾기 알고리즘

2. 소셜 네트워크 분석

• 문제: 소셜 네트워크를 통해 사람들 간의 지인/친밀도 관계를 파악할 수 있음. 이를 통해 한 다리 건너 알고 있는 사람은 몇 명이나 되는지, 몇 다리나 건너가야 누군가와 내가 아는 사이인지 알 수 있음

• 정점: 소셜 네트워크 사이트의 회원

• 간선: 두 회원이 서로 친구 사이인 경우 연결

• 관련 알고리즘: 그래프의 너비 우선 탐색

3. 인터넷 전송 속도 계산

• 문제: 어떤 경로의 시간당 전송 용량은 이 경로가 지나는 케이블 중 가장 작은 전송 용량을 갖는 케이블에 의해 좌우됨. 이때 두 컴퓨터 간의 전송 용량 계산

• 정점: 인터넷에 연결된 라우터와 컴퓨터

• 간선: 두 기계를 연결하는 케이블

• 관련 알고리즘: 최소 스패닝 트리 알고리즘

4. 한 붓 그리기

• 문제: 종이에서 연필을 떼지 않고 주어진 도형을 그리되, 모든 선을 한 번씩만 지날 수 있는지. 즉, 모든 간선을 한 번씩만 지나는 경로를 찾을 수 있는지.

• 정점: 선들이 만나는 점

• 간선: 점들을 연결하는 선

• 관련 알고리즘: 오일러 경로(Eulerian path), 깊이 우선 탐색

5. 외환 거래

• 문제: 외환 거래 시장은 달러, 유로, 엔, 스위스 프랑 등의 통화(currency)와 이들 간의 교환 비율로 구성됨. 1달러를 들고 유로로 바꾸고, 유로를 엔으로 바꿨다가, 다시 달러로 바꿨을 때 1달러보다 많은 돈을 가지게 되는 것을 아비트러지(arbitrage)라고 함. 환율 목록이 주어질 때 아비트러지가 존재하는지 여부

• ) 아비트러지가 있다 ⇔ 간선 가중치의 합이 음수인 사이클이 있다

• 정점: 통화

• 간선: 서로 교환 가능한 통화들 사이에 (방향이 있는) 간선

• 관련 알고리즘: 최단 거리 알고리즘

암시적 그래프 구조들

• 그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해 표현하면 쉬운 문제
• 암시적 그래프(implicit graph)

할 일 목록 정리

• 문제: 의존 관계에 있는 여러 할 일이 있을 때 이들을 한 번에 하나씩 해나갈 방법이 있는지, 있다면 어느 순서대로 하면 되는지 계산

• 관련 알고리즘: 위상 정렬(topological sorting), 깊이 우선 탐색

15-퍼즐

• 문제: 1~15 숫자 타일을 움직여 원래 있던 순서대로 정렬하는 15-퍼즐 문제

• 정점: 현재 타일의 배치

• 간선: 한 배치에서 타일을 한 번 움직여 다른 배치를 얻을 수 있을 때 두 정점 연결

• 관련 알고리즘: 최단 경론 문제

게임판 덮기

• 문제: 정사각현의 게임판(가로,세로 길이:N)을 1X2크기의 블록으로 모든 칸을 덮는 문제

• 정점: 막히지 않는 각 칸

• 간선: 상하좌우로 인접한 칸들 사이 연결

• 관련 알고리즘: 이분 그래프, 이분 매칭 그래프

회의실 배정

• 문제: N개의 팀이 회의를 하려고 하는데, 회의실이 하나뿐인 관계로 한 번에 한 팀만 사용할 수 있음. 각 팀이 회의실을 사용하고 싶은 시간을 각각 두 개씩 적어 냈을 때 모든 팀이 회의하도록 배정하는 방법 찾기.

• 관련 알고리즘: 만족성 문제(satisfiability problem), 2-SAT(두 선택지 중 하나를 선택해야 하는 문제), 강 결합성 문제

그래프의 표현 방법

• 새로운 정점이나 간선을 추가하고 삭제하는 일이 자주 발생하지 않음
• 간단하고 메모리를 적게 차지하는 방법으로 구현
• 정점: 0부터 시작하는 번호 부여, 배열에 각 정점의 정보를 저장
• 간선: 반대쪽 끝 정점의 번호 저장
• 간선의 정보를 어떤 식으로 저장하느냐에 따라 두가지로 나뉨
  • 메모리나 시간 사용 특성이 다름

1. 입접 리스트 표현

• 인접 리스트(adjacency list): 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장
• 각각의 정점에 인접한 정점들을 연결 리스트로 표현

각 정점마다 하나의 연결 리스트를 갖음

vector <list<int>> adjacent;

adjacent[i] : 정점 i와 간선을 통해 연결된 정점들의 번호 저장

#define MAX_VERTICES 50
typedef struct GraphNode{
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType{
int n;//정점의 개수
GraphNode * adj_list[MAX_VERTICES];
}GraphType;

간선이 추가적 속성을 갖고 있음

//1. 간선의 정보를 구조체로 표현
struct Edge{
int vertex;
int weight;
};
//2. 단순하게 pair 사용
pair<int,int>

2. 인접 행렬 표현

• 인접 행렬(adjacency matrix): |V| X |V| 크기의 행렬, 즉 2차원 배열을 이용해 그래프의 간선 정보를 저장

2차원 불린 값 배열

vector<vector<bool>> adjacent;

adjacent[i,j] : 정점 i에서 정점 j로 가는 간선이 있는지를 나타내는 불린 값 변수

#define MAX_VERTICES 50
typedef struct GraphType{
int n;//정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType

무방향 그래프 - 간선 삽입 시 adj[start][end]와 adj[end][start]에 1 삽입 방향 그래프 - 간선 삽입 시 adj[start][end]에만 1삽입

간선이 추가적 정보를 갖고 있음

vector<vector<int>> adjacent;
vector<vector<double>> adjacent;

두 정점 사이에 간선이 없을 경우 -1 또는 아주 큰 값 등 존재할 수 없는 값으로 지정

3. 인접 행렬과 인접 리스트 비교

-인접 리스트

• 장점: 실제 간선 수만큼의 원소 O($|V| + |E|$)의 공간만을 사용
• 단점: 정점의 번호 u,v사이의 간선이 있는지 여부를 연결리스트 adjacent[u]를 처음부터 일일이 확인해야함
• 희소 그래프(sparse graph): 간선의 수가 $|V|^2$ 에 비해 훨씬 적은 그래프 → 인접 리스트 사용

-인접 행렬

• 장점: 한 번의 배열 접근만으로 정점의 번호 u,v사이의 간서이 있는지 여부 확인 가능
• 단점: 항상 O($|V|^2$)크기의 공간을 사용함
• 밀집 그래프(dense graph): 간선의 수가 $|V|^2$ 에 비례하는 그래프 → 인접 행렬 사용

문제

한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다. 한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요. 예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.

입력 생성

입력의 크기가 큰 관계로, 이 문제에서는 수열을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.

• A[0] = 1983
• A[i] = (A[i-1] * a + b) % 20090711 a와 b는 입력에 주어지는 상수입니다. 이 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다.

  입력

  입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C줄에 각 3개의 정수로 수열의 길이 N (1 <= N <= 200,000), 그리고 수열을 생성하는 데 필요한 두 정수 a , b (0 <= a,b <= 10000) 가 주어집니다.

  출력

  각 테스트 케이스마다 한 줄에 N개의 중간값의 합을 20090711로 나눈 나머지를 출력합니다.

  예제 입력

  3 10 1 0 10 1 1 10000 1273 4936

  예제 출력

  19830 19850 2448920

First Thoughts

배열에서 중간값 구하기

무작위로 생성된 숫자를 배열에 정렬하며 삽입한다. 각 입력마다 정렬된 배열에서 중간값을 찾아 총 합을 구한다. 배열의 크기가 짝수일 때는 중간에 있는 두 수 중 더 작을 값을 중간값으로 한다.

My Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <long long> heap;
long long median(vector<long long>& heap) {
    long long m = heap.size();
    if (m % 2 == 0) {
        long long r = m / 2 - 1;
        long long l = m / 2;
        if (heap[r] < heap[l])
            return heap[r];
        else
            return heap[l];
    }
    else {
        m = m / 2;
        return heap[m];
    }
}
long long newValue(long long N,long long a, long long b) {
    long long sum = 0;
    long long start = 1983;
    for (long long i = 0; i < N; i++) {
        if (i == 0)
            heap.push_back(start);
        else {
            start = (a*start+b)%20090711;
            heap.push_back(start);
        }
        sort(heap.begin(), heap.end());
        sum += median(heap);
    }
    return sum % 20090711;
}
int main(void) {
    int C;
    int i;
    long long N,a,b;
    cin >> C;
    for (i = 0; i < C; i++) {
        cin >> N >> a >> b;
        cout << newValue(N, a, b)<< endl;
        heap.clear();
    }
}

Answer Code

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

struct RNG {
    int seed, a, b;
    RNG(int _a, int _b):a(_a),b(_b),seed(1983){}
    int next() {
        int ret = seed;
        seed = ((seed * (long long)a) + b) % 20090711;
        return ret;
    }
};
int runningMedian(int n, RNG rng) {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int ret = 0;
    //최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
    //최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다
    for (int cnt = 1; cnt <= n; cnt++) {
        if (maxHeap.size() == minHeap.size())
            maxHeap.push(rng.next());
        else
            minHeap.push(rng.next());
        if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
            int a = maxHeap.top(), b = minHeap.top();
            maxHeap.pop();
            minHeap.pop();
            maxHeap.push(b);
            minHeap.push(a);
        }
        ret = (ret + maxHeap.top()) % 20090711;
    }
    return ret;
}

int main(void) {
    int C;
    int N, a, b;
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> N >> a >> b;
        RNG rng(a, b);
        cout << runningMedian(N, rng) << endl;
    }
}

Difference & Faults

시간 초과

코드를 제출해보지 않고도 컴파일 했을 때에도 몇 초의 지연 후에 결과가 나오더라. 그래서 시간초과가 뜰 줄은 알았다. 자료형을 long long으로 바꿔보고 cin,cout을 scanf,printf로도 바꿔봤지만 속도에 크게 영향을 미치진 않더라. 그래서 결국은 내 코드의 시간적 결함을 인정하게 되었다.

부트리 2개 만들기

숫자들을 정렬했을 때 앞의 절반은 최대 힙(maxheap)에 저장하고 뒤의 절반을 최소 힙(minheap)에 저장한다. 힙의 크기가 홀수라면 최대 힙에 숫자를 하나 더 넣도록 한다. 이것을 두개의 문장으로 표현해보면 다음과 같다.

1. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 크다
2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다 위 두 문장을 염두에 두고 두개의 힙을 사용하여 숫자를 입력해간다. 그리고 중간값을 항상 최대 힙의 루트에 위치한다.

Impressions

책의 해답을 보기 전에 구글링을 해보니 runningmedian이라는 문제가 꽤나 유명한 문제라는 것을 알게 됬다. 특히 우선순위 큐와 힙에서는 대표적인 연습문제 같았다. 그래서 몇가지 유튜브 영상을 참고하였는데 모든 영상이 하나같이 똑같은 풀이더라. 책도 같은 풀이일까 싶어서 책을 보았는데 역시나 같은 풀이더라. 두 개의 힙을 사용하여 처음에는 두 개 힙의 크기에 따라 입력이 들어가는 숫자의 힙이 다르고 입력된 후 각 힙의 루트 원소의 크기를 비교하여 힙을 수정한다.

Summary

"우선순위 큐와 힙"에서는 꽤나 유명한 문제같아서 문제와 풀이 방법을 기억하고 두고두고 사용해야할 거 같다.

문제

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽입 정렬의 구현은 다음과 같습니다.

void insertionSort(vector<int>& A) {
  for(int i = 0; i < A.size(); ++i) {
    // A[0..i-1] 에 A[i] 를 끼워넣는다
    int j = i;
    while(j > 0 && A[j-1] > A[j]) {
      // 불변식 a: A[j+1..i] 의 모든 원소는 A[j] 보다 크다.
      // 불변식 b: A[0..i] 구간은 A[j] 를 제외하면 정렬되어 있다.
      swap(A[j-1], A[j]);
      --j;
    }
  }
}

삽입 정렬은 A[0..i-1] 이 정렬된 배열일 때, A[i] 를 적절한 위치를 만날 때까지 왼쪽으로 한칸씩 움직입니다. 예를 들어 A={5,1,4,3,2} 의 삽입 정렬은 다음과 같이 이루어집니다. 1부터 N까지의 자연수가 한 번씩 포함된 길이 N 인 수열 A[] 를 삽입 정렬했습니다. 원래 수열은 알 수 없지만, 그 과정에서 각 원소가 왼쪽으로 몇 칸이나 이동했는지를 알고 있습니다. 예를 들어, 위 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0,1,1,2,3} 이 됩니다. 이 때 원래 수열을 찾아내는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원 배열의 길이 N (1 <= N <= 50000) 이 주어집니다. 그 다음 줄에 N 개의 정수로 A의 각 위치에 있던 값들이 움직인 칸수가 주어집니다. A 는 1부터 N 까지의 정수를 한 번씩 포함합니다. 입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

출력

각 테스트 케이스마다 재구성한 A[] 를 한 줄에 출력합니다

예제 입력

2
5
0 1 1 2 3
4
0 1 2 3

예제 출력

5 1 4 3 2
4 3 2 1

First Thoughts

삽입 정렬의 기본 원리

일단 문제를 읽고 두가지 구문이 눈에 띄었다. "삽입 정렬", "왼쪽으로 이동". 삽입 정렬의 특성이 자기자신을 기준으로 왼쪽 부분은 정렬이 되어있고 그 정렬된 부분의 원소들과 자기 자신을 비교함으로써 적절한 위치에 삽입하는 것이다. 그렇다면 각 정수가 움직이기 위해서는 기본적으로 자기 앞에 큰 원소들이 위치해있어야한다. 이를 베이스로 코드를 작성하였다.

My Code

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int movement[50000];
typedef int KeyType;
struct Node {
    //노드에 저장된 원소
    KeyType key;
    //노드의 우선순위,노드를 루트로 하는 서브트리의 크기
    int priority, size;
    //두 자식 노드의 포인터
    Node* left, * right;
    //생성자에서 난수 우선순위를 생성하고 size와 left/right를 초기화
    Node(const KeyType& _key) :key(_key), priority(rand()), size(1), left(NULL), right(NULL) {}
    void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
    void setRight(Node* newRight) { right = newRight; calcSize(); }
    //size멤버 갱신
    void calcSize() {
        size = 1;
        if (left)
            size += left->size;
        if (right)
            size += right->size;
    }
};
typedef pair<Node*, Node*> NodePair;
NodePair split(Node* root, KeyType key) {
    //공백의 트리인경우
    if (root == NULL)
        //트리가 없음
        return NodePair(NULL, NULL);
    //root의 key가 node의 key보다 작은 경우
    if (root->key < key) {
        //root의 오른쪽 부트리에서 node의 key보다 작은 경우나 큰 경우 나누기
        NodePair rs = split(root->right, key);
        //나눈 트리 중 node의 key값보다 작은 트리(root의 key값보다는 큰 트리=>오른쪽 트리)를 현재 root의 오른쪽 트리로 설정
        root->setRight(rs.first);
        //현재 부트리는 root가 루트노드인 경우와 쪼개진 트리의 node의 key보다 큰 원소의 트리로 이루어진 두개의 부트리 반환
        return NodePair(root, rs.second);
    }
    //root의 key가 node의 key보다 큰 경우
    //root의 key보다 원소값이 작은 왼쪽 부트리를 key값과 비교하여 트리 생성
    NodePair ls = split(root->left, key);
    //나눈 트리 중 node의 key값보다 큰 트리(root의 key값보다는 작은 트리=>왼쪽 트리)를 현재 root의 왼쪽 트리로 설정
    root->setLeft(ls.second);
    //현재 부트리는 root가 루트노드인 오른쪽 트리와 쪼개진 트리의 node의 key보다 작은 원소의 트리인 왼쪽 부트리로 이루어진 두개의 부트리 반환
    return NodePair(ls.first, root);
}
Node* insert(Node* root, Node* node) {
    //공백의 트리라면 새로운 노드만 반환
    if (root == NULL)
        return node;
    //root의 우선순위보다 node의 우선순위가 높은 경우
    if (root->priority < node->priority) {
        //왼쪽,오른쪽 트리 생성
        NodePair splitted = split(root, node->key);
        //node를 루트로 하고 node보다 작은 원소들이 모인 왼쪽 부트리와
        node->setLeft(splitted.first);
        //node보다 큰 원소들이 모인 오른쪽 부트리를 node에 잇는다
        node->setRight(splitted.second);
        //이어진 node를 루트로 반환
        return node;
    }
    //root의 우선순위보다 node의 우선순위가 작은 경우
    //root의 왼쪽,오른쪽 부트리의 루트노드와 비교하며 진행
    //node의 key가 root의 key보다 작은 경우
    else if (node->key < root->key) {
        //왼쪽 부트리로 이동
        root->setLeft(insert(root->left, node));
    }
    //node의 key가 root의 key보다 큰 경우
    else {
        //오른쪽 부트리로 이동
        root->setRight(insert(root->right, node));
    }
    //현재 root반환
    return root;
}
Node* kth(Node* root, int k) {
    //왼쪽 서브트리의 크기 계산
    int leftSize = 0;
    if (root->left != NULL)
        leftSize = root->left->size;
    //k가 왼쪽 서브트리 내부에 있을 경우
    if (k <= leftSize)
        //왼쪽 서브트리로 들어가 순회
        return kth(root->left, k);
    //왼쪽 트리의 사이즈와 현재 루트까지 합쳐서 k개
    if (k == leftSize + 1)
        //현재 root값 반환
        return root;
    //k가 오른쪽 서브트리에 있을 때
    return kth(root->right, k - leftSize - 1);
}
Node* merge(Node* a, Node* b) {
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;
    if (a->priority < b->priority) {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(a->right, b));
    return a;
}
Node* erase(Node* root, KeyType key) {
    if (root == NULL)
        return root;
    if (root->key == key) {
        Node* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if (key < root->key) {
        root->setLeft(erase(root->left, key));
    }
    else {
        root->setRight(erase(root->right, key));
    }
    return root;
}

void reverse_insert(int N) {
    int original[50000];
    Node* root=NULL;
    for (int i = 1; i <= N; i++) {
        root = insert(root, new Node(i));
    }
    for (int i = N - 1; i >= 0; i--) {
        int l = movement[i];
        original[i] = kth(root, i + 1 - l)->key;
        root = erase(root, original[i]);
    }
    for (int i = 0; i < N; i++) {
        cout << original[i] << ' ';
    }
}

int main(void) {
    int C;
    int N;
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> N;
        for (int j = 0; j < N; j++) {
            cin >> movement[j];
        }
        reverse_insert(N);
        memset(movement, 0, sizeof(int)*N);
    }
}

Answer Code

//my_code
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef int KeyType;
struct Node {
    //노드에 저장된 원소
    KeyType key;
    //노드의 우선순위,노드를 루트로 하는 서브트리의 크기
    int priority, size;
    //두 자식 노드의 포인터
    Node* left, * right;
    //생성자에서 난수 우선순위를 생성하고 size와 left/right를 초기화
    Node(const KeyType& _key) :key(_key), priority(rand()), size(1), left(NULL), right(NULL) {}
    void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
    void setRight(Node* newRight) { right = newRight; calcSize(); }
    //size멤버 갱신
    void calcSize() {
        size = 1;
        if (left)
            size += left->size;
        if (right)
            size += right->size;
    }
};
typedef pair<Node*, Node*> NodePair;
NodePair split(Node* root, KeyType key) {
    //공백의 트리인경우
    if (root == NULL)
        //트리가 없음
        return NodePair(NULL, NULL);
    //root의 key가 node의 key보다 작은 경우
    if (root->key < key) {
        //root의 오른쪽 부트리에서 node의 key보다 작은 경우나 큰 경우 나누기
        NodePair rs = split(root->right, key);
        //나눈 트리 중 node의 key값보다 작은 트리(root의 key값보다는 큰 트리=>오른쪽 트리)를 현재 root의 오른쪽 트리로 설정
        root->setRight(rs.first);
        //현재 부트리는 root가 루트노드인 경우와 쪼개진 트리의 node의 key보다 큰 원소의 트리로 이루어진 두개의 부트리 반환
        return NodePair(root, rs.second);
    }
    //root의 key가 node의 key보다 큰 경우
    //root의 key보다 원소값이 작은 왼쪽 부트리를 key값과 비교하여 트리 생성
    NodePair ls = split(root->left, key);
    //나눈 트리 중 node의 key값보다 큰 트리(root의 key값보다는 작은 트리=>왼쪽 트리)를 현재 root의 왼쪽 트리로 설정
    root->setLeft(ls.second);
    //현재 부트리는 root가 루트노드인 오른쪽 트리와 쪼개진 트리의 node의 key보다 작은 원소의 트리인 왼쪽 부트리로 이루어진 두개의 부트리 반환
    return NodePair(ls.first, root);
}
Node* insert(Node* root, Node* node) {
    //공백의 트리라면 새로운 노드만 반환
    if (root == NULL)
        return node;
    //root의 우선순위보다 node의 우선순위가 높은 경우
    if (root->priority < node->priority) {
        //왼쪽,오른쪽 트리 생성
        NodePair splitted = split(root, node->key);
        //node를 루트로 하고 node보다 작은 원소들이 모인 왼쪽 부트리와
        node->setLeft(splitted.first);
        //node보다 큰 원소들이 모인 오른쪽 부트리를 node에 잇는다
        node->setRight(splitted.second);
        //이어진 node를 루트로 반환
        return node;
    }
    //root의 우선순위보다 node의 우선순위가 작은 경우
    //root의 왼쪽,오른쪽 부트리의 루트노드와 비교하며 진행
    //node의 key가 root의 key보다 작은 경우
    else if (node->key < root->key) {
        //왼쪽 부트리로 이동
        root->setLeft(insert(root->left, node));
    }
    //node의 key가 root의 key보다 큰 경우
    else {
        //오른쪽 부트리로 이동
        root->setRight(insert(root->right, node));
    }
    //현재 root반환
    return root;
}
Node* kth(Node* root, int k) {
    //왼쪽 서브트리의 크기 계산
    int leftSize = 0;
    if (root->left != NULL)
        leftSize = root->left->size;
    //k가 왼쪽 서브트리 내부에 있을 경우
    if (k <= leftSize)
        //왼쪽 서브트리로 들어가 순회
        return kth(root->left, k);
    //왼쪽 트리의 사이즈와 현재 루트까지 합쳐서 k개
    if (k == leftSize + 1)
        //현재 root값 반환
        return root;
    //k가 오른쪽 서브트리에 있을 때
    return kth(root->right, k - leftSize - 1);
}
Node* merge(Node* a, Node* b) {
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;
    if (a->priority < b->priority) {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(a->right, b));
    return a;
}
Node* erase(Node* root, KeyType key) {
    if (root == NULL)
        return root;
    if (root->key == key) {
        Node* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if (key < root->key) {
        root->setLeft(erase(root->left, key));
    }
    else {
        root->setRight(erase(root->right, key));
    }
    return root;
}
int n, shifted[50000];
int A[50000];
void solve() {
    Node* candidates = NULL;
    for (int i = 0; i < n; i++) {
        candidates = insert(candidates, new Node(i + 1));
    }
    for (int i = n - 1; i >= 0; i--) {
        int larger = shifted[i];
        Node* k = kth(candidates, i + 1 - larger);
        A[i] = k->key;
        candidates = erase(candidates, k->key);
    }
}
int main() {
    int C;
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> shifted[j];
        }
        solve();
        for(int i=0;i<n;i++){
            cout << A[i] << ' ';
        }
        cout << endl;
        memset(shifted, 0, sizeof(int) * n);
        memset(A, 0, sizeof(int) * n);
    }
}

Difference & Faults

이번 코드는 difference & faults보다는 similarity 가 더 보이므로 이 부분은 따로 작성하지 않겠다.

Impressions

트립

이 문제의 가장 핵심부는 트립의 구현이라고 말하고 싶다. 물론 삽입의 원리를 충분히 이해하고 있어야 코드를 응용할 수 있었을 것이다. 하지만 무엇보다 트립을 코드로 구현하고 삭제나 삽입의 구현이 가장 핵심부인 거 같다. 트립 부분을 공부하면서 처음에는 이해가 안가서 삽입 부분만 3번을 읽었다. 그래서 일단 코드를 따라 작성해보고 각 코드별로 주석을 달면서 공부하니까 훨씬 수월하게 이해할 수 있었다. 무작정 따라하는 것을 선호하진 않지만 배움에 있어서는 무작정 따라해보는 것도 좋은 방법인 거 같다.

Summary

시험공부를 할 때마다 드는 생각이 있다. "이게 나올까?", "이거 공부해야되나?". 이번에 트립을 공부할 때나 알고리즘 이론 정리를 할 때 역시 "이걸 알아야할까?","이게 의미가 있을까?"이다. 근데 이 문제를 보고 내가 공부하는 것에 다시 확신을 얻었다. 앞으로 얼마 남지 않은 진도를 충실히 완주했으면 좋겠다.

c++표준라이브러리

c++에서 제공하는 다양한 라이브러리를 설명해놓은 microsoft의 공식 사이트이다. 위의 사이트를 통해 필요로하는 라이브러리를 찾아보고 라이브러리 내 다양한 함수들을 익혀보도록 하자.

iomanip의 fixed,setprecision의 사용

부동소수점 값의 전체 자릿수를 설정한다. fixed가 없는 경우 정수부와 소수부 모두 포함하여 자릿수를 설정한다. fixed가 있는 경우 소수부분만의 자릿수를 설정한다. 또한 버림이 아닌 반올림으로 자릿수를 설정한다.

T5 setprecision(streamsize Prec);

• Prec: 부동 소수점 값의 전체 자릿수

2. 입력

1. cin

• iostream 에 존재
• 표준 입력 버퍼에서 개행문자를 제외한 값을 가져옴
• 공백, 개행 무시
• 개행 키보드 버퍼에 남겨둠

2. cin.get()

• iostream에 존재
• 표준 입력 버퍼에서 문자를 하나만 가져옴
• 공백, 개행 포함
• 문자만 입력 받음

3. cin.getline()

• iostream에 존재
• 종결 문자를 NULL로 바꿈, 종결 문자 생략 시 엔터로 간주
• 최대 입력 가능 문자수보다 많은 문자를 입력한 경우 n 번째 문자부터 NULL로 취급
• 공백, 개행 입력 받음
• 문자열만 입력받음

std::cin.getline(char str[], int size)

• char str[] : 문자열을 저장할 char 배열명
• int size: 저장할 문자의 최대 개수

4. getline()

• string에 존재
• 공백, 개행 입력 받음
• 문자열 입력받음

std::getline(std c,string str, char deliminator)

• std c : 파일입력을 받을지 표준입력을 받을지
• string str : 문자열을 저장할 string형 변수명
• char deliminator : 입력받은 문자들 중 어떤 문자까지만 저장할지 결정 (default값:'\n')

3. 자료형 범위

각 자료형별 범위이다. 변수 선언 시 범위를 확인하고 그에 대응되는 자료형을 사용하자.

5. 입력의 형태가 정해져있을 때(발상의 전환)

c++은 c언어와 달리 입력의 형태를 정해놓고 입력을 받을 수 없는 듯했다. 예를 들어 c언어에서 h:m:s의 형태로 입력을 받고자 한다면 scanf("%d:%d:%d",&h,&m,&s)로 입력받을 수 있지만 c++에서는 정해진 형태의 입력에 대해서 따로 방법이 없다. 그래서 :와 같은 부분을 tmp라는 별도의 변수에 저장한다. 그러면 cin>>h>>tmp>>m>>tmp>>s 로 입력을 받을 수 있다.

6. cout.width,cout.fill

7. 진수 표현

2,8,16,10진수 더 많은 형태로 숫자를 표현하고 싶다면 위의 링크를 참고하면 좋을 거 같다.

1. 10진수

cout<<dex<<...

• 접두사 없음

2. 8진수

cout<<oct<<...

• 접두사 0출력

3. 16진수

cout<<hex<<...

• 접두사 0X 출력

• 참고

  cout<<uppercase<<...

  16진수 대문자를 출력

  cout<<nouppercase<<...

  16진수 소문자를 출력

8. p진수 -> q진수로 표현

입력 받을 때 해당 진수의 flag를 설정하고 입력받고 출력하고자 하는 진수의 flag를 사용하여 출력한다.

ex) 8진수에서 10진수로 표현

#include <iostream>
using namespace std;

int main(void) {
    int a;
    cin >> oct >>a;
    cout << dec << a;
}

(참고) 영문자에서 10진수로 변환

영문자에서 10진수로 변환할 때도 위와 비슷하게 하면 된다.

#include <iostream>
using namespace std;
int main(void) {
    char a;
    cin >> a;
    cout << (int) a;
}

9. 비트 연산자

10. 16진수 곱하기

1082 : [기초-종합] 16진수 구구단? 8번의 p진수로 입력받아 q진수로 표현하는 문제의 풀이방식과 비슷하다. 입력이 16진수로 입력되므로 hex flag를 사용하고 출력할 때 역시 hex flag를 다시 선언해준다. 자세한 문제는 위 링크에서 풀어보길 바란다.

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int a;
    cin >> hex>>a;
    for (int i = 1; i <16; i++) {
        cout <<uppercase<< hex<<a << '*' << uppercase << hex << i << '=';
        cout << hex << a * i<<endl;
    }
}

11. endl과 '\n'의 시간차이

문제를 푸는 과정에서 endl과 '\n'에 속도차이가 있다는 것을 알게되었다. endl함수는 개행만 해주는 것이 아니라 flush함수를 겸하기 때문에 내부 버퍼를 비워주는 역할도 함께 수행하여 매우 느리다고 한다. c++에서는 endl뿐만 아니라 몇몇 입출력 스타일에서 속도차이가 발생하는 부분이 있다고한다. 그래서 되도록이면 c스타일의 입출력을 사용하도록 하자.

12. 함께 문제 푸는 날 주기성

1092 : [기초-종합] 함께 문제 푸는 날(설명) 어떤 사람이 d일 간격으로 어떤 일을 한다고 가정하자. 그러면 n번째 날 그 일을 하는지 안하는지 알 수 있는 방법은 n을 d로 나눠봄으로써 n일이 d의 배수이면(n%d==0)그 일을 하고 그렇지 않다면(n%d!=0)그 일을 하지 않는다. 위 문제에서는 이러한 주기성을 가지는 사람이 3명이 있는데 그 사람들이 함께 어떤 일을 행하는 날을 찾는것이다. 즉, 모든 사람의 주기로 특정한 날을 나눴을때 모두 나머지가 0이 되는 날(최소공배수)를 구하면되는 것이다. 이를 역으로 하면 어느 한 명이라도 나머지가 0이 아닌 날이 나오면 그 다음날로 넘어간다. 더 자세한 문제설명은 위 링크를 참고하기 바란다.

#include <iostream>
using namespace std;
int main() {
    int a, b, c;
    int day=1;
    cin >> a >> b >> c;
    while (day % a != 0 || day % b != 0 || day % c != 0) {
        day++;
    }
    cout << day << endl;
}

13. 성실한 개미 문제

1099 : [기초-2차원배열] 성실한 개미 기초 100제의 가장 까다로운 문제였다. 이 문제를 봤을 때 가장 먼저 떠오른 것은 stack의 사용과 재귀함수였다. stack을 떠올린 이유는 학교에서 좌표 사이를 움직이는 쥐의 움직임을 출력하는 문제를 푼 기억이 있어서이다. 아쉽게도 나의 코드는 stack을 사용하지 않고 재귀함수만을 사용하였다. 그런데 만약 stack을 사용하였다면 개미가 움직일 수 있는 방향의 좌표를 모두 stack에 저장하며 해당 좌표가 1이면 전 좌표로 돌아가고 그렇지 않다면 먹이를 만날 때까지 재귀적으로 진행하였을 것이다. 아래의 코드도 stack을 이용하지 않았을뿐 개미의 움직임을 재귀적으로 표현하였다. 그런데 여기서 까다로웠던 부분은 오른쪽으로 갈지 아래로 갈지에 대한 판단이었다. 문제에 정확히 설명되어있지 않은 부분 중에 하나가 개미는 우선적으로 오른쪽으로 진행한다는 것이다. 그래서 오른쪽에 장애물이 없다면 오른쪽으로 이동하고 그렇지 않다면 아래로 진행하는 방식으로 재귀함수를 구현하였다. 기초 100제의 가장 마지막 문제이고 재귀함수를 제대로 경험할 수 있는 좋은 문제인 거 같다. 위에 링크를 통해 한 번 풀어보길 권장한다.

#include <iostream>
using namespace std;
int ar[10][10];
int solve(int x, int y) {
    if (ar[x][y] == 2) {
        ar[x][y] = 9;
        return 0;
    }
    else if (ar[x][y])
        return 0;
    else {
        if (ar[x][y + 1] != 1)
            solve(x, y + 1);
        else if(ar[x+1][y]!=1)
            solve(x + 1, y);
        ar[x][y] = 9;
    }
}
int main() {
    int i, j;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            cin >> ar[i][j];//0:갈 수 있는 곳, 1: 벽 또는 장애물, 2:먹이
        }
    }
    solve(1,1);
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            cout << ar[i][j] << ' ';//0:갈 수 있는 곳, 1: 벽 또는 장애물, 2:먹이
        }
        cout << "\n";
    }
}