Microsoft Azure Cognitive Face API를 이용하여 Instagram 이미지 분석하기

Microsoft Azure Cognitive Face API를 이용하여 Instagram의 이미지를 분석하는 작은 프로젝트를 해봤습니다. 언어는 Python을 사용합니다.

목차

  1. Instagram 사진 다운받기
  2. Face API 등록
  3. 코드 작성

1. Instagram 사진 다운받기

먼저 Instagram의 이미지를 다운받기 위해 Instagram Scraper를 다운받아야합니다.

  • github 링크 : https://github.com/rarcega/instagram-scraper
    • 설치 방법

      $ pip install instagram-scraper

    • 피드명을 @feed, 인스타그램 id를 @id, password를 @pw라고 했을 때 다음 명령어를 입력하면 사진을 다운로드 받을 수 있습니다.

      $ instagram-scraper @feed -u @id -p @pw

2. Face API 등록

Face key를 받기 위해 Face API에 들어가서 계정을 등록합니다. 기간 한정 무료로 이용할 수 있습니다.

계정 등록을 하면 Face Key를 얻어올 수 있습니다.

3. 코드 작성

  • 아래 코드들은 @feed 부분과 path 부분을 각자 상황에 맞게 수정해야 돌아간다.
  • 필요한 모듈과 Face key, face url 지정
import requests, os, json, time
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import pprint
from PIL import Image
face_key = # '2번에서 얻어온 Face Key'
face_url = 'https://westcentralus.api.cognitive.microsoft.com/face/v1.0/detect'
headers    = {
    'Ocp-Apim-Subscription-Key': face_key,
    'Content-Type': 'application/octet-stream'
}

params = {
    'returnFaceId': 'true',
    'returnFaceLandmarks': 'true',
    'returnFaceAttributes': 'age,gender,headPose,smile,facialHair,glasses,' +
    'emotion,hair,makeup,occlusion,accessories,blur,exposure,noise',
    'recognitionModel': 'recognition_02',
    'returnRecognitionModel': 'true'
}

def face_api(filename):
    with open(filename, "rb") as f:
        body = f.read()
    try:
        response = requests.post(face_url, headers=headers, params=params, data=body)
        results = response.json()
    except Exception as e:
        print(e)
        results = None
    return results

image_list = os.listdir(#'@feed')
save_path = './save/'
# 숨김파일 제거
image_list = [photo_name for photo_name in apple_image_list if not photo_name.startswith('.')]

with open(save_path + "result.jsonl", 'a') as f:
    for image in image_list:
        if image.endswith('jpg'):
            photo = #'./@feed/' + image
            results = face_api(photo)
            photo_dict = {}
            photo_dict[image] = results
            f.write(json.dumps(photo_dict) + '\n')
            time.sleep(3) # 무료로 이용할 땐 3초에 1번씩 요청할 수 있기 때문에 sleep이 필요하다.
  • 이제 작성된 jsonl 파일을 가지고 평균 얼굴의 갯수와 감정의 갯수를 구하는 예제를 풀 수 있다.
face_results = []
with open(save_path + "result.jsonl", 'r') as f:
    for line in f:
        face_results.append(json.loads(line))

face_count = []
for result in face_results:
    face_count.append(len(list(result.values())[0]))

anger, contempt, disgust, fear, happiness, neutral, sadness, surprise = [], [], [], [], [], [], [], []
for result in face_results:
    faces = list(result.values())[0]
    if len(faces) != 0:
        for face in faces:
            anger.append(face['faceAttributes']['emotion']['anger'])
            contempt.append(face['faceAttributes']['emotion']['contempt'])
            disgust.append(face['faceAttributes']['emotion']['disgust'])
            fear.append(face['faceAttributes']['emotion']['fear'])
            happiness.append(face['faceAttributes']['emotion']['happiness'])
            neutral.append(face['faceAttributes']['emotion']['neutral'])
            sadness.append(face['faceAttributes']['emotion']['sadness'])
            surprise.append(face['faceAttributes']['emotion']['surprise'])

print("평균 얼굴 개수 : " + str(np.mean(face_count)))
print("anger : " + str(np.mean(anger)))
print("contempt : " + str(np.mean(contempt)))
print("disgust : " + str(np.mean(disgust)))
print("fear : " + str(np.mean(fear)))
print("happiness : " + str(np.mean(happiness)))
print("neutral : " + str(np.mean(neutral)))
print("sadness : " + str(np.mean(sadness)))
print("surprise : " + str(np.mean(surprise)))
  • plt를 이용하여 pie 그래프로 나타낼 수도 있다.
emotion = ['anger', 'contempt', 'disgust', 'fear', 'hapiness', 'neutral', 'sadness', 'surprise']
popuratity = [np.mean(anger), np.mean(contempt), np.mean(disgust), np.mean(fear), np.mean(happiness), np.mean(neutral),
             np.mean(sadness), np.mean(surprise)]
colors = ['blue', 'orange', 'green', 'red', 'violet', 'brown', 'gold', 'yellowgreen'] 
explode = (0, 0, 0, 0, 0, 0, 0, 0)  

plt.figure(figsize=(12, 12))
plt.pie(popuratity, explode=explode, labels=emotion, textprops={'fontsize': 15}, colors=colors, autopct='%1.1f%%', shadow=True)
print("@Apple emotion")
plt.show()
  • 위 코드의 결과

Image

네트워크 프로그래밍 과제 1

  • 랜덤으로 10000줄의 무작위 데이터를 만들어야한다.
  • [줄번호] 데이터 형식으로 만든다. 데이터 크기는 50바이트로 정한다.
  • IncludeNumber=True이면 숫자 포함한 데이터를 생성하고 False면 알파벳만 포함한다.
import random

ASCII_number_start = 48
ASCII_number_end = 57
ASCII_AlphabetUpper_start = 65
ASCII_AlphabetUpper_end = 90
ASCII_AlphabetLower_start = 97
ASCII_AlphabetLower_end = 122
  • 파일 생성 갯수
  • 확장자
  • Line 수
  • 한 Line당 길이
  • 데이터에 숫자 포함 여부
HowManyFile = 3
Extension = '.txt'
HowManyLine = 10000
OneLineLenghth = 50
IncludeNumber = False
if IncludeNumber :
    randArg = 3
else :
    randArg = 2
fileNames = []
for i in range(HowManyFile) :
    fileNames.append("input_random_"+str(i+1) + Extension)
for fileName in fileNames :
    with  open(fileName, 'w') as file :
        for i in range(HowManyLine):
            inputLine = "[" + str(i+1) + "] "
            for line in range(OneLineLenghth) : 
                case = random.randint(1, randArg)
                if case == 1:
                    inputLine += chr(random.randint(ASCII_AlphabetUpper_start, ASCII_AlphabetUpper_end))
                if case == 2:                    
                    inputLine += chr(random.randint(ASCII_AlphabetLower_start, ASCII_AlphabetLower_end))
                if case == 3:
                    inputLine += chr(random.randint(ASCII_number_start, ASCII_number_end))
            inputLine += '\n'
            file.write(inputLine)

이 페이지를 번역했습니다.

당신도 개발의 희생자가 될 수 있다.

by Jon Evans

개발자들에게:

3가지 기기 제품군에서 사용되는 8가지 프로그래밍 언어에만 능숙해서 불안한가요?
또 다른 JavaScript framework에 대한 노출이 당신을 두렵게 만드나요?
어떤 클라우드 플랫폼이 적절할지 몰라서 pet project를 연기 해본적이 있나요?

당신은 또한 Developaralysis로 고통받을 것입니다.

Be afraid. There is no cure.

오늘날 개발자들이 이용할 수 있는 선택사항들은 터무니없다. We're choking on a cornucopia. 지난 몇년동안 저는 다양한 SQL / key-value / document datastores (MySQL, PostgreSQL, MongoDB, BigTable, Redis, Memcached, etc.)를 기반으로 Java, Objective-C, C, C++, Python, Ruby, JavaScript, PHP를 작성해서 돈을 받았다. 하지만 저는 만족하지 않습니다. 저는 Erlang, Clojure, Rust, Go, C#, Scala, Haskell, Julia, Scheme, Swift 또는 OCaml으로 아무것도 하지 않은 것에 대해 죄책감을 느낍니다.

저는 Developaralysis의 희생자입니다. (Developaralysis: 소프트웨어 산업이 너무 빨리 발전해서 아무도 따라갈 수 없다는 암울한 느낌)

거의 모든 언어를 사용하고 다양한 framework와 toolkit 및 library를 사용할 수 있도록 해야합니다. 머리가 터질 정도로. 오늘날 JavaScript framework와 library 확장에 대한 제대로된 평가를 완료하는데 몇달이 걸 릴 것입니다. 당신은 Ruby gem이 얼마나 있는지 압니까? 아니면 iOS framework는요? NewSQL / NoSQL datastores는요? 그리고 심지어 Hadoop vs Spark vs Google Dataflow 또는 Avro vs Thrift vs protocol buffer ... 도 있다.

적어도 모바일에서는 Andorid, iOS로 축소되었지만, Xamarin 또는 PhoneGap, Sencha와 같은 식으로 크로스 플랫폼 HTML과 같은 crossover 대안을 숨기지만, 백엔드를 배치하는 위치와 방법을 파악해야한다. Heroku, Amazon Web Services, Google App Engine, Google Compute Engine 및 Parse에 배포된 시스템에서 작업했다. 실제로 OpenStack, Force.com, Azure, AppFog, 실제로 제가 사용해본적 없는 수많은 AWS 서비스에 대해 거의 알지 못한다고 느끼게한다.

오늘날 개발자들은 사용 가능한 옵션이 너무 많아서, Tool의 목록을 관리하기 위해서 Bundler, Bower, CocoaPods, Pip 등과 같은 다른 Tools를 사용하고 있다. 그런 다음 다른 Tools를 사용하기 시작한다.

슬픈 사실은 오늘날 개발자들이 사용할 수 있는 언어, Tools, framework 및 플랫폼이 엄청난게 많다는 것이다. 물론 아무도 이것을 인정하고 싶어하지만 진실은 우리 모두가 Developaralysis에 고통받고 있다는 것이다.

정보에 입각한 결정을 내리는데 필요한 정보를 모으는 것 조차도 비생산적이다. 프로젝트에 착수하기 전에 실제로 모든 가능성을 분석하고 그 결과로 얻은 학습 곡선을 올린다면 PHP와 Swift를 사용하여 10대 청소년이 시장에 맞을 수 있게 된다.

하지만 다른 한편으로는 Swift와 PHP에 정착하면 Paul Graham이 Lisp에서 했던 방식으로 당신은 어떤 닌자 C# / Haskell 프로그래머가 주위에 링을 돌고 있는 공포에 떨 수 있습니다.

기술은 선택할때, 당신은 다른 사람이 했던 것을 무시해야합니다. 가장 일을 잘 수행할 것을 고려해야합니다. 사실 우리는 비밀스런 무기를 가지고 있었습니다. 우리는 누군가가 생각한 것보다 빠르게 소프트웨어를 개발할 수 있었습니다. 우리는 이상한 AI 언어로 우리의 소프트웨어를 괄호로 가득 찬 기괴한 구문으로 작성했습니다.

따라서, Developaralysis. 학습 곡선을 포기하지 않고 지금 이동할 수 있기 때문에 우리가 이미 알고 있는 것을 선택합니까? 누군가의 다른 사람이 그것을 더 잘, 더 빨리 다룬다는 공포에 살고 있다. 우리의 기술이 내년에 쓸모 없어지고 경쟁력이 떨어집니까? 우리가 배우는 것을 좋아하고 더 나은 도구가 더 재미있고 큰 경쟁 우위를 가지고 있기 때문에 상당한 시간, 노력을 희생해서 지식을 늘립니까?

정렬 알고리즘의 실행시간 비교

  • Exchange sort, Merge sort, Quick sort 알고리즘을 구현하기.

  • 각각의 정렬 방법에서 key를 비교한 횟수와 실행시간을 측정하여 비교한다. 측정에는 clock 함수를 쓴다.

  • Exchange sort와 Quick sort의 비교는 key의 갯수가 다른 3가지 오름차순으로 정렬된 데이터를 생성해여 비교한다.

  • Merge sort와 Quick sort의 비교는 key의 갯수가 다른 3가지 경우에 대해 각각 5개의 임의의 데이터를 생성하여 평균값으로 비교한다.

  • key의 갯수는 실행시간이 충분한 유효숫자를 가질 수 있도록 각자 정한다.

  • 측정된 key의 비교횟수와 실행시간이 정렬 알고리즘들의 이론적 시간 복잡도와 일치하는지 분석한다.

  • 입력 형식
    input.txt, 처음은 오름차순 데이터, 그 다음은 임의의 데이터가 입력된다.

  • 출력 형식

    Image

  • Exchange Sort : for문을 중첩하여 선택된 인덱스의 키와 나머지 키를 비교하여 선택된 키보다 작으면 앞으로 가게 한다.(인접한 원소끼리 비교하여 작은 게 앞으로 오게 한다.) 시간 복잡도가 O(N^2)이다.

  • Merge Sort : 정렬되지 않은 배열을 반으로 나눈다. 길이가 1이 될 때 까지 나눈 후, 나눈 것을 다시 합친다. 합칠 때 작은 원소 순서대로 오게 한다. 시간 복잡도가 O(NlogN)이다.

  • Quick Sort : 한 원소를 pivot으로 잡는다. 배열의 맨 왼쪽 원소를 left, 오른쪽 인덱스를 right라고 하고, left부터 오른쪽으로 옮겨가며 pivot보다 큰 값이 나올때까지, right부터 왼쪽으로 옮겨가며 pivot보다 작은 값이 나올때까지 이동한다. 두 원소를 교환한다. left가 right보다 오른쪽에 있으면 다시 왼쪽 오른쪽으로 나눠진 배열을 다시 퀵 정렬한다. 시간 복잡도가 최악의 경우에 O(N^2), 평균 O(NlogN)이 나온다.

Exchange Sort와 Quick Sort의 비교 (오름차순으로 정렬된 데이터)

  • N값(key의 개수)에 10000, 20000, 40000을 넣어 수행한다.
    Image

  • Exchange sort의 경우 이론적 시간 복잡도가 O(N^2) 이므로 N이 2배 늘어날때마다 시간이 4배 늘어날 것으로 예상이 된다.

    N=10000 일때 0.09375, N=20000일 때 0.359375, N=40000일 때 1.515625가 걸렸다.

    0.09375 : 0.359375 = 1 : 3.83333 이므로 거의 1:4 이고, 0.09375 : 1.515625= 1:16.1666667 이므로 거의 1:16이다.

    0.359375 : 1.515625= 1 : 4.217391 로 거의 1:4이다.

    clock의 오차를 감안하면 exchange sort의 시간 복잡도가 O(N^2)인 것을 알 수 있다. 이론적 시간 복잡도와 일치한다.

    key 값의 비교 횟수도 역시 49995000: 199990000 : 799980000 = 1 : 4 : 16의 꼴을 띈다.

  • Quick Sort는 정렬된 데이터가 들어갔을 때 최악의 경우로 O(N^2)이 걸린다.

    그러므로 N값이 2배 늘어날때마다 시간이 4배 늘어날 것으로 예상이 된다.

    N=10000일 때 0.078125, N=20000일 때 0.328125, N=40000일 때 1.3125가 걸렸다.

    0.078125 : 0.328125 = 1 : 4.2 로 거의 1:4 이고, 0.078125 : 1.3125 = 1 : 16.8 로 거의 1:16이다.

    0.328125 : 1.3125 = 1 : 4이다.

    clock의 오차를 감안하면 Quick Sort는 정렬된 데이터가 들어갔을 때 최악으로 O(N^2)이 걸린다는 것을 알 수 있다.

    key 값의 비교 횟수도 역시 49995000: 199990000 : 799980000 = 1 : 4 : 16의 꼴을 띈다.

    (N)^2: (2N)^2 : (4N)^2 = 1 : 4 : 16

Merge Sort와 Quick Sort의 비교 (무작위 데이터, 5번 수행 후 평균값)

  • N값(key의 개수)이 1000000, 2000000, 4000000을 넣어 수행한다.
    Image

  • Merge Sort의 경우 이론적 시간 복잡도가 O(NlogN)이다. N값이 2배 늘어날 때 마다 약 2.~배 정도 늘어날 것으로 예상이 된다.

    N=1000000일 때 0.23125, N=2000000일 때 0.48125, N=4000000일 때 0.95625가 걸렸다.

    0.23125 : 0.48125 = 1 : 2.081081, 0.23125 : 0.95625 = 1 : 4.135135, 0.48125 : 0.95625 = 1 : 1.987013 으로, clock의 오차를 감안하면 예상된 시간 복잡도와 비슷하다.

    key 값의 비교 횟수는 19951424 : 41902848 : 87805696 = 1 : 2.1 : 4.4 로 2배 보다 약간 더 늘어났다.

  • Quick Sort의 경우 평균적으로 O(NlogN)의 시간 복잡도를 가진다. N값이 2배 늘어날때마다 2.~배 늘어날 것으로 예상이 된다.

    N=1000000일 때 0.031250, N=2000000일 때 0.065625, N=4000000일 때 0.131250가 걸렸다.

    0.031250 : 0.065625 = 1 : 2.1, 0.065625 : 0.131250 = 1 : 2, 0.031250 : 0.13125 = 1 : 4.2 이므로 clock의 오차와 평균을 구할 때 5번 밖에 수행하지 않아 오차가 클 수 있다는 점을 감안하면 예상된 시간 복잡도와 일치한다.

    key 값의 비교 횟수는 4088134 : 8475511 : 17790888 = 1 : 2.07319 : 4.351835로 N값이 2배 늘어날 때마다 2배보다 약간 더 늘어났다.

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <vector>
using namespace std;
char ex[] = "Exchange Sort";  // 13
char qu[] = "Quick Sort";     // 10
char me[] = "Merge Sort";     // 10
char kc[] = "Key Compares";   // 12
char et[] = "Exe.Time";       // 8
char sp[] = "             ";  // 13

unsigned long long key_compare; // 비교횟수 count
unsigned long long result[2][3];  // 1번 key_compare 저장
unsigned long long result2[2][3];  // 2번 key_compare 저장
double ti[2][3];   // 1번 시간 저장
double ti2[2][3];   // 2번 시간 저장

int in[3];         // 1번 N 값 저장
int in2[3];         // 2번 N 값 저장

void init() { key_compare = 0; }
void exchange_sort(unsigned long long * v, int size);
void merge(unsigned long long * v, int low, int mid, int high);
void mergesort(unsigned long long * v, int low, int high);
void quick_sort(unsigned long long *v, int left, int right);

int main() {
    int n;
    ifstream ifs("input.txt");

    // 1번
    // Exchange Sort, Quick Sort 비교, 오름차순 정렬
    for (int i = 0; i < 3; i++) {
        ifs >> n;
        in[i] = n;

        unsigned long long * ev = new unsigned long long[n];
        unsigned long long * qv = new unsigned long long[n];
        for (int j = 0; j < n; j++) {
            ev[j] = qv[j] = j;
        }
        // Exchange Sort
        init(); // key_compare 초기화
        clock_t t = clock();
        exchange_sort(ev, n);
        t = clock() - t; // 시간 저장
        unsigned long long es_key = key_compare;
        double es_time = (double)(t) / CLOCKS_PER_SEC;
        // Quick Sort
        init(); // key compare 초기화
        t = clock();
        quick_sort(qv, 0, n - 1);
        t = clock() - t; // 시간 저장
        unsigned long long qs_key = key_compare;
        double qs_time = (double)(t) / CLOCKS_PER_SEC;

        result[0][i] = es_key;
        result[1][i] = qs_key;
        ti[0][i] = es_time;
        ti[1][i] = qs_time;

        delete ev, qv;
    }

    // 2번
    // Merge Sort, Quick Sort 비교, 랜덤
    srand((unsigned int)time(0));
    for (int i = 0; i < 3; i++) {
        ifs >> n;
        in2[i] = n; // case N 저장

        unsigned long long * mv = new unsigned long long[n+1];
        unsigned long long * qv = new unsigned long long[n+1];

        unsigned long long kc_ms = 0;     // key compares of merge
        unsigned long long kc_qs = 0;     // key compares of quick
        double et_ms = 0;  // ex.time of merge
        double et_qs = 0;  // ex.time of quick

        // Random Number
        for (int k = 0; k < 5; k++) {
            for (int j = 0; j < n; j++) {
                unsigned long long push_num = (unsigned long long)rand() % RAND_MAX;
                mv[j] = qv[j] = push_num;
            }

            // mergesort
            init();  // key_compare 초기화
            clock_t t = clock();
            mergesort(mv, 0, n - 1);  // 실행
            t = clock() - t;
            kc_ms += key_compare;
            et_ms += (double)(t) / CLOCKS_PER_SEC;  // 경과 시간 저장

            // quicksort
            init();  // key_compare 초기화
            t = clock();
            quick_sort(qv, 0, n - 1);  // 실행
            t = clock() - t;
            kc_qs = key_compare;
            et_qs = (double)(t) / CLOCKS_PER_SEC;  // 경과 시간 저장


        }

        kc_ms /= 5;
        kc_qs /= 5;
        et_ms /= 5.0;
        et_qs /= 5.0;

        result2[0][i] = kc_ms;
        result2[1][i] = kc_qs;
        ti2[0][i] = et_ms;
        ti2[1][i] = et_qs;

        delete mv, qv;
    }
    //                                    N = Case1    N = Case 2    N = Case 3
    printf("%-14s\t %14s\t N=%-10d\t N=%-10d\t N=%-10d\n", sp, sp, in[0], in[1], in[2]);
    // Exchange Sort    Key Compares
    //                    Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", ex, kc, result[0][0], result[0][1], result[0][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti[0][0], ti[0][1], ti[0][2]);
    // Quick Sort    Key Compares
    //                Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", qu, kc, result[1][0], result[1][1], result[1][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti[1][0], ti[1][1], ti[1][2]);
    printf("\n\n");

    //                                    N = Case1    N = Case 2    N = Case 3
    printf("%-14s\t %14s\t N=%-10d\t N=%-10d\t N=%-10d\n", sp, sp, in2[0], in2[1], in2[2]);
    // Merge Sort    Key Compares
    //                    Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", me, kc, result2[0][0], result2[0][1], result2[0][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti2[0][0], ti2[0][1], ti2[0][2]);
    // Quick Sort    Key Compares
    //                Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", qu, kc, result2[1][0],    result2[1][1], result2[1][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti2[1][0],    ti2[1][1], ti2[1][2]);
}

void exchange_sort(unsigned long long * v, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            key_compare++;
            if (v[i] > v[j]) {
                unsigned long long temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }
}

void merge(unsigned long long * v, int low, int mid, int high) {
    int i, j, k;
    i = low;      // 왼쪽 시작
    j = mid + 1;  // 오른쪽 시작
    k = low;      // 결과 배열 인덱스
    unsigned long long *temp = new unsigned long long[high + 1];
    while (i <= mid && j <= high) {
        if (v[i] < v[j]) {
            key_compare++;
            temp[k] = v[i];
            i++;
        }
        else {
            key_compare++;
            temp[k] = v[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        key_compare++;
        temp[k] = v[i];
        i++;
        k++;
    }

    while (j <= high) {
        key_compare++;
        temp[k] = v[j];
        j++;
        k++;
    }
    for (int i = low; i <= high; i++) {
        v[i] = temp[i];
    }
    delete temp;
}
void mergesort(unsigned long long * v, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergesort(v, low, mid);
        mergesort(v, mid + 1, high);
        merge(v, low, mid, high);
    }
}

void quick_sort(unsigned long long * v, int left, int right) {
    int i = left, j = right;
    unsigned long long pivot = v[left];
    do {
        while (v[i] < pivot) {
            key_compare++;
            i++;
        }
        while (v[j] > pivot) {
            key_compare++;
            j--;
        }
        if (i <= j) {
            if (v[i] > v[j]) {
                unsigned long long temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
            i++;
            j--;
        }
    } while (i <= j);
    if (left < j) {
        quick_sort(v, left, j);
    }
    if (i < right) {
        quick_sort(v, i, right);
    }
}

이진트리에서 노드의 수가 가장 많은 레벨 찾기

  • 조건
    1. 루트의 레벨은 1로 한다
    2. 자식의 레벨은 부모의 레벨 + 1이다.
    3. 이진트리에서 같은 레벨에 있는 노드는 같은 행에 위치한다.

노드의 수가 가장 많은 레벨을 출력하는 프로그램을 작성하시오.

  • 입력 형식
    입력 파일의 이름은 input.txt이다. 여러개의 테스트 데이터가 입력될 수 있다. 첫째 줄에는 테스트 데이터의 개수가 입력된다. 둘째 줄에는 첫번째 데이터의 노드의 개수를 나타내는 정수 N(1≤N≤1,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지로 주어진다. 자식이 없는 경우에는 자식노드의 번호가 -1로 주어진다. 루트 노드의 번호는 1이다. 그 다음 줄부터 나머지 데이터가 같은방식으로 주어진다.

  • Test Case

    • 입력
      2
      19
      1 2 3
      2 4 5
      3 6 7
      4 8 -1
      5 9 10
      6 11 12
      7 13 -1
      8 -1 -1
      9 14 15
      10 -1 -1
      11 16 -1
      12 -1 -1
      13 17 -1
      14 -1 -1
      15 18 -1
      16 -1 -1
      17 -1 19
      18 -1 -1
      19 -1 -1
      3
      1 2 3
      2 -1 -1
      3 -1 -1
    • 출력
      4
      2

데이터 노드의 개수가 1과 1000 사이의 정수이기 때문에 전역변수 tree[1001][2]로 잡는다([2]는 왼쪽, 오른쪽 자식).

트리의 노드 별로 레벨을 저장하기 위해 level[1001]을 잡는다. cnt[1001]은 각 레벨의 노드 개수를 저장한다.

테스트 데이터의 개수를 입력 받는다.

여러 번의 테스트를 하므로 tree, level, cnt 배열을 0으로 초기화한다.

노드 1의 레벨을 1로 초기화한다. 노드의 개수를 입력 받는다.

node의 개수만큼 for문을 반복한다.

for문에서는 parent, child1, child2 (부모, 왼쪽 자식, 오른쪽 자식)을 입력 받고 tree에 넣는다.

만약 child1, child2가 -1이 아니면 level[child1], level[child2]를 level[parent]+1 값을 넣는다.

현재 트리의 깊이를 저장하기 위한 max_level을 선언하고 0으로 초기화한다.

node 개수만큼 for문을 반복한다. 노드가 i 레벨일때마다 cnt[i]를 1씩 올린다.

level[i]이 max_level보다 높아지면 max_level에 level[i]를 넣는다.(각 레벨별 노드 개수를 cnt에 저장한다.)

max_level만큼 for문을 반복한다. cnt를 순회하면서 가장 큰 값을 result에 저장한다.

result를 출력하고 다시 반복한다.

이 알고리즘의 시간 복잡도는 한 테스트 케이스당 O(n)이다.(n: 노드의 개수)

#include <fstream>
#include <iostream>
using namespace std;
int tree[1001][2];  // 트리
int level[1001];    // 노드의 레벨
int cnt[1001];      // 각 레벨의 노드 갯수
int main() {
    int n;
    ifstream ifs("input.txt");
    ifs >> n;                              // 테스트 케이스의 개수 입력 받기
    while (n--) {                          // n번 반복
        for (int i = 0; i <= 1001; i++) {  // 0으로 초기화
            tree[i][0] = 0;
            tree[i][1] = 0;
            level[i] = 0;
            cnt[i] = 0;
        }
        level[1] = 1;  // 루트의 레벨은 1
        int node;
        ifs >> node;                      // 노드의 개수 입력 받기
        for (int i = 0; i < node; i++) {  // 노드 개수만큼 반복
            // 부모와 왼쪽, 오른쪽 자식을 입력 받는다.
            int parent, child1, child2;
            ifs >> parent >> child1 >> child2;
            // -1이 아니면 부모의 레벨+1을 자식 레벨에 넣는다.
            if (child1 != -1) {
                tree[parent][0] = child1;
                level[child1] = level[parent] + 1;
            } else {  // -1이면 empty에 1을 추가한다.
                tree[parent][0] = child1;
            }
            // -1이 아니면 부모의 레벨+1을 자식 레벨에 넣는다.
            if (child2 != -1) {
                tree[parent][1] = child2;
                level[child2] = level[parent] + 1;
            } else {  // -1이면 empty에 1을 추가한다.
                tree[parent][1] = child2;
            }
        }
        int max_level = 0;  // 현재 트리가 몇 레벨까지 있는지 저장.
        // 각 레벨별 노드 갯수를 cnt에 저장한다.
        for (int i = 1; i <= node; i++) {
            cnt[level[i]]++;
            if (max_level < level[i]) max_level = level[i];
        }
        int result = 0;
        // 노드가 가장 많은 레벨을 찾는다. 그 때의 레벨을 result에 저장.
        for (int i = 1; i <= max_level; i++) {
            if (result < cnt[i]) {
                result = i;
            }
        }
        // 노드가 가장 많은 레벨을 출력한다.
        cout << result << '\n';
    }
}

코드는 참고만 해주세요.

+ Recent posts