신입사원 프로젝트로 간만에 안드로이드 개발을 하게됐습니다. 서버와 통신하기위해 Square에서 만든 Retrofit 라이브러리를 사용했는데, 기존에 사용하던 버전(1.x)과 변경된 부분이 많아 새롭게 사용법을 알아보고자 합니다.
Retrofit 테스트는 API 테스트 사이트를 통해서 Fake data를 가져오는 실습을 해보겠습니다. 해당 글의 대부분은 Retrofit 2.0 Example을 참고했습니다.

Retrofit2

Retrofit 의외에 다른 라이브러리도 있지만, Retrofit을 사용하기로 한 이유는 성능과 간단한 구현방법 때문입니다. 아래 보시는것과 같이 응답속도가 매우 빠른것으로 나와있습니다. 더 자세한 비교는 Android Async HTTP Clients: Volley vs Retrofit에서 볼 수 있습니다.

Retrofit2는 기본적으로 OkHttp를 네트워킹 계층으로 활용하며 그 위에 구축됩니다.

Retrofit은 자동적으로 JSON 응답을 사전에 정의된 POJO를 통해 직렬화 할 수 있습니다. JSON을 직렬화 하기 위해서는 먼저 Gson converter가 필요합니다. **build.gradle**에 다음의 dependencies를 추가합니다.

1
2
3

compile 'com.squareup.retrofit2:retrofit:2.3.0'
compile 'com.google.code.gson:gson:2.8.0'
compile 'com.squareup.retrofit2:converter-gson:2.1.0'

OkHttp는 이미 Retrofit2 모듈의 종속성에 포함되어 있어, 별도의 OkHttp 설정이 필요하다면 다음과 같이 Retrofit2에서 OkHttp 종속성을 제외해야 합니다.

1
2
3
4
5
6
7
8

compile('com.squareup.retrofit2:retrofit:2.3.0') {
    exclude module: 'okhttp'
}
compile 'com.google.code.gson:gson:2.8.0'
compile 'com.squareup.retrofit2:converter-gson:2.1.0'
compile 'com.squareup.okhttp3:okhttp:3.9.1'
compile 'com.squareup.okhttp3:logging-interceptor:3.9.1'
// logging-interceptor는 반환된 모든 응답에 대해 로그 문자열을 생성합니다.

네트워크 사용을 위해서 **AndroidManifest.xml**에서 Internet Permission을 추가합니다.

1
2
3

<manifest xmlns:android="http://schemas.android.com/apk/res/android">
    <uses-permission android:name="android.permission.INTERNET" />
</manifest>

OkHttp Interceptors

**Interceptor**는 OkHttp에 있는 강력한 메커니즘으로 호출을 모니터, 재 작성 및 재 시도를 할 수 있습니다. Interceptor는 크게 두 가지 카테고리로 분류할 수 있습니다.

• Application Interceptors : Application Interceptor를 등록하려면 OkHttpClient.Builder에서 addInterceptor()를 호출해야 합니다.
• Network Interceptors : Network Interceptor를 등록하려면 addInterceptor() 대신 addNetworkInterceptor()를 추가해야 합니다.

Retrofit Interface 설정

APIClient.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package com.journaldev.retrofitintro;

import okhttp3.OkHttpClient;
import okhttp3.logging.HttpLoggingInterceptor;
import retrofit2.Retrofit;
import retrofit2.converter.gson.GsonConverterFactory;

class APIClient {

    private static Retrofit retrofit = null;

    static Retrofit getClient() {
        HttpLoggingInterceptor interceptor = new HttpLoggingInterceptor();
        interceptor.setLevel(HttpLoggingInterceptor.Level.BODY);
        OkHttpClient client = new OkHttpClient.Builder().addInterceptor(interceptor).build();

        retrofit = new Retrofit.Builder()
                .baseUrl("https://reqres.in/")
                .addConverterFactory(GsonConverterFactory.create())
                .client(client)
                .build();

        return retrofit;
    }
}

getClient() 메서드는 Retrofit 인터페이스를 설정할 때마다 호출됩니다. Retrofit은 **@GET, @POST, @PUT, @DELETE, @PATCH or @HEAD**와 같은 annotation을 통해 HTTP method를 이용합니다.

APIInterface.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package com.journaldev.retrofitintro;

import com.journaldev.retrofitintro.pojo.MultipleResource;
import com.journaldev.retrofitintro.pojo.User;
import com.journaldev.retrofitintro.pojo.UserList;

import retrofit2.Call;
import retrofit2.http.Body;
import retrofit2.http.Field;
import retrofit2.http.FormUrlEncoded;
import retrofit2.http.GET;
import retrofit2.http.POST;
import retrofit2.http.Query;

interface APIInterface {

    @GET("api/unknown")
    Call<MultipleResource> doGetListResources();

    @POST("api/users")
    Call<User> createUser(@Body User user);

    @GET("api/users?")
    Call<UserList> doGetUserList(@Query("page") String page);

    @FormUrlEncoded
    @POST("api/users?")
    Call<UserList> doCreateUserWithField(@Field("name") String name, @Field("job") String job);
}

위의 클래스에서 Annotation을 통해 테스트 HTTP request를 작성했습니다. 해당 API로 이곳을 통해 테스트 할 것입니다.

@GET("api/unknown")은 doGetListResources()를 호출합니다.
doGetListResources()은 메서드 이름입니다. MultipleResource.java는 응답 객체의 Model POJO 클래스로서 Response parameter를 각각의 변수에 매핑하는 데 사용됩니다. 이러한 POJO 클래스는 메소드 리턴 유형으로 동작합니다.

MultipleResources.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package com.journaldev.retrofitintro.pojo;

import com.google.gson.annotations.SerializedName;

import java.util.ArrayList;
import java.util.List;

public class MultipleResource {

    @SerializedName("page")
    public Integer page;
    @SerializedName("per_page")
    public Integer perPage;
    @SerializedName("total")
    public Integer total;
    @SerializedName("total_pages")
    public Integer totalPages;
    @SerializedName("data")
    public List<Datum> data = null;

    public class Datum {

        @SerializedName("id")
        public Integer id;
        @SerializedName("name")
        public String name;
        @SerializedName("year")
        public Integer year;
        @SerializedName("pantone_value")
        public String pantoneValue;

    }
}

@SerializedName 어노테이션은 JSON 응답에서 각각의 필드를 구분하기 위해 사용합니다.

# Tip) jsonschema2pojo 에서 json 응답의 구조를 바탕으로 해당 응답에 대한 POJO 클래스를 쉽게 만들 수 있습니다.

POJO 클래스는 Retrofit Call 클래스로 래핑됩니다. (JSONArray는 POJO 클래스의 객체 목록으로 직렬화됩니다.)

Method Parameters : 메서드 내에서 전달할 수 있는 다양한 매개 변수 옵션이 있습니다.

• @Body - request body로 Java 객체를 전달합니다.
• @Url - 동적인 URL이 필요할때 사용합니다.
• @Query - 쿼리를 추가할 수 있으며, 쿼리를 URL 인코딩하려면 다음과 같이 작성합니다.
  @Query(value = “auth_token”,encoded = true) String auth_token
• @Field - POST에서만 동작하며 form-urlencoded로 데이터를 전송합니다. 이 메소드에는 @FormUrlEncoded 어노테이션이 추가되어야 합니다.

Android Retrofit 예제 프로젝트 구조

pojo 패키지는 APIInterface.java 클래스에 정의된 각각의 API 요청 응답에 대한 4가지 모델 클래스를 정의하고 있습니다.

User.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

package com.journaldev.retrofitintro.pojo;

import com.google.gson.annotations.SerializedName;

public class User {

    @SerializedName("name")
    public String name;
    @SerializedName("job")
    public String job;
    @SerializedName("id")
    public String id;
    @SerializedName("createdAt")
    public String createdAt;

    public User(String name, String job) {
        this.name = name;
        this.job = job;
    }
}

위 클래스는 createUser() 메서드에 대한 응답을 위해 사용합니다.

UserList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package com.journaldev.retrofitintro.pojo;

import com.google.gson.annotations.SerializedName;

import java.util.ArrayList;
import java.util.List;

public class UserList {

    @SerializedName("page")
    public Integer page;
    @SerializedName("per_page")
    public Integer perPage;
    @SerializedName("total")
    public Integer total;
    @SerializedName("total_pages")
    public Integer totalPages;
    @SerializedName("data")
    public List<Datum> data = new ArrayList();

    public class Datum {

        @SerializedName("id")
        public Integer id;
        @SerializedName("first_name")
        public String first_name;
        @SerializedName("last_name")
        public String last_name;
        @SerializedName("avatar")
        public String avatar;

    }
}

CreateUserResponse.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

package com.journaldev.retrofitintro.pojo;

import com.google.gson.annotations.SerializedName;

public class CreateUserResponse {

    @SerializedName("name")
    public String name;
    @SerializedName("job")
    public String job;
    @SerializedName("id")
    public String id;
    @SerializedName("createdAt")
    public String createdAt;
}

MainActivity.java

**MainActivity.java**는 Interface 클래스에 정의된 각각의 API를 호출하고 그 결과를 Toast와 TextView를 통해 표시하고 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

package com.journaldev.retrofitintro;

import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.TextView;
import android.widget.Toast;

import com.journaldev.retrofitintro.pojo.CreateUserResponse;
import com.journaldev.retrofitintro.pojo.MultipleResource;
import com.journaldev.retrofitintro.pojo.User;
import com.journaldev.retrofitintro.pojo.UserList;

import java.util.List;

import retrofit2.Call;
import retrofit2.Callback;
import retrofit2.Response;

public class MainActivity extends AppCompatActivity {

    TextView responseText;
    APIInterface apiInterface;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        responseText = (TextView) findViewById(R.id.responseText);
        apiInterface = APIClient.getClient().create(APIInterface.class);


        /**
         GET List Resources
         **/
        Call<MultipleResource> call = apiInterface.doGetListResources();
        call.enqueue(new Callback<MultipleResource>() {
            @Override
            public void onResponse(Call<MultipleResource> call, Response<MultipleResource> response) {


                Log.d("TAG",response.code()+"");

                String displayResponse = "";

                MultipleResource resource = response.body();
                Integer text = resource.page;
                Integer total = resource.total;
                Integer totalPages = resource.totalPages;
                List<MultipleResource.Datum> datumList = resource.data;

                displayResponse += text + " Page\n" + total + " Total\n" + totalPages + " Total Pages\n";

                for (MultipleResource.Datum datum : datumList) {
                    displayResponse += datum.id + " " + datum.name + " " + datum.pantoneValue + " " + datum.year + "\n";
                }

                responseText.setText(displayResponse);

            }

            @Override
            public void onFailure(Call<MultipleResource> call, Throwable t) {
                call.cancel();
            }
        });

        /**
         Create new user
         **/
        User user = new User("morpheus", "leader");
        Call<User> call1 = apiInterface.createUser(user);
        call1.enqueue(new Callback<User>() {
            @Override
            public void onResponse(Call<User> call, Response<User> response) {
                User user1 = response.body();

                Toast.makeText(getApplicationContext(), user1.name + " " + user1.job + " " + user1.id + " " + user1.createdAt, Toast.LENGTH_SHORT).show();

            }

            @Override
            public void onFailure(Call<User> call, Throwable t) {
                call.cancel();
            }
        });

        /**
         GET List Users
         **/
        Call<UserList> call2 = apiInterface.doGetUserList("2");
        call2.enqueue(new Callback<UserList>() {
            @Override
            public void onResponse(Call<UserList> call, Response<UserList> response) {

                UserList userList = response.body();
                Integer text = userList.page;
                Integer total = userList.total;
                Integer totalPages = userList.totalPages;
                List<UserList.Datum> datumList = userList.data;
                Toast.makeText(getApplicationContext(), text + " page\n" + total + " total\n" + totalPages + " totalPages\n", Toast.LENGTH_SHORT).show();

                for (UserList.Datum datum : datumList) {
                    Toast.makeText(getApplicationContext(), "id : " + datum.id + " name: " + datum.first_name + " " + datum.last_name + " avatar: " + datum.avatar, Toast.LENGTH_SHORT).show();
                }


            }

            @Override
            public void onFailure(Call<UserList> call, Throwable t) {
                call.cancel();
            }
        });


        /**
         POST name and job Url encoded.
         **/
        Call<UserList> call3 = apiInterface.doCreateUserWithField("morpheus","leader");
        call3.enqueue(new Callback<UserList>() {
            @Override
            public void onResponse(Call<UserList> call, Response<UserList> response) {
                UserList userList = response.body();
                Integer text = userList.page;
                Integer total = userList.total;
                Integer totalPages = userList.totalPages;
                List<UserList.Datum> datumList = userList.data;
                Toast.makeText(getApplicationContext(), text + " page\n" + total + " total\n" + totalPages + " totalPages\n", Toast.LENGTH_SHORT).show();

                for (UserList.Datum datum : datumList) {
                    Toast.makeText(getApplicationContext(), "id : " + datum.id + " name: " + datum.first_name + " " + datum.last_name + " avatar: " + datum.avatar, Toast.LENGTH_SHORT).show();
                }

            }

            @Override
            public void onFailure(Call<UserList> call, Throwable t) {
                call.cancel();
            }
        });

    }
}

apiInterface = APIClient.getClient().create(APIInterface.class);는 APIClient를 인스턴스화 하기위해 사용됩니다.
API 응답에 Model 클래스를 매핑하기 위해서는 다음과 같이 사용합니다.
MultipleResource resource = response.body();

이제 앱을 실행하면 각 API를 호출하고 이에 따라 토스트 메시지를 표시합니다.

참고

• Volley vs Retrofit
• OkHttp Example

안드로이드에서 <네이버 아이디로 로그인> 기능을 구현하며 OAuth 2.0에 대해 알아보고, 라이브러리를 적용하는 방법에 대해 알아보겠습니다.

OAuth 2.0

OAuth는 **인증(Authentication)과 허가(Authorization)**을 위한 표준 프로토콜로, 사용자가 Facebook이나 트위터 같은 인터넷 서비스의 기능을 다른 애플리케이션(데스크톱, 웹, 모바일 등)에서도 사용할 수 있게 한 것입니다.

Facebook이나 트위터의 기능을 이용하기 위해 사용자가 반드시 Facebook이나 트위터에 로그인해야 하는 것이 아니라, 별도의 인증 절차를 거치면 다른 서비스에서 Facebook과 트위터의 기능을 이용할 수 있게 됩니다. 이런 방식은 Facebook이나 트위터 같은 서비스 제공자뿐만 아니라 사용자와 여러 인터넷 서비스 업체 모두에 이익이 되는 생태계를 구축하는데 기여했습니다.
이 방식에서 사용하는 **인증 절차가 OAuth**입니다.

OAuth를 이용하면 이 인증을 공유하는 애플리케이션끼리는 별도의 인증이 필요없습니다. 따라서 여러 애플리케이션을 통합하여 사용하는 것이 가능하게 됩니다.

OAuth 2.0은 authorization(허가, 승인)을 위한 산업 표준 프로토콜입니다. OAuth 2.0 전에 OAuth 1.0이 만들어져 사용되었지만 웹, 데스크탑, 모바일 등의 어플리케이션의 authorization flow(권한 흐름)을 보다 단순화 하는데 초점이 맞춰졌습니다.
(OAuth 1.0에서는 Acess Token을 받으면 계속 사용이 가능했습니다. 그러나 OAuth 2.0에서는 보안 강화를 위해 Access Token의 Life-time을 지정할 수 있게됐고, Life-time이 만료되면 Refresh Token을 통해 Access Token을 재발급을 받아야 합니다.)

주의사항

로그인과 OAuth는 반드시 분리해서 이해해야 합니다. 아래의 예시를 통해 그 이유를 생각해봅시다.

사원증을 이용해 출입할 수 있는 회사를 생각해 보자. 그런데 외부 손님이 그 회사에 방문할 일이 있다. 회사 사원이 건물에 출입하는 것이 로그인이라면 OAuth는 방문증을 수령한 후 회사에 출입하는 것에 비유할 수 있다. 방문증이란 사전에 정해진 곳만 다닐 수 있도록 하는 것이니, ‘방문증’을 가진 사람이 출입할 수 있는 곳과 ‘사원증’을 가진 사람이 출입할 수 있는 곳은 다르다. 역시 직접 서비스에 로그인한 사용자와 OAuth를 이용해 권한을 인증받은 사용자는 할 수 있는 일이 다르다.

구성요소

• 사용자(Resource Owner) : Service Provider에 계정을 가지고 있으면서, Client를 이용하려는 사용자
• 소비자(Client) : OAuth 인증을 사용해 Service Provider의 기능을 사용하려는 애플리케이션이나 웹 서비스
• API 서버(Resource Server) : OAuth를 사용하는 Open API를 제공하는 서비스
• 권한 (Authroization Server) : OAuth 인증 서버
• 접근 토큰(Access Token) : 인증 후 Client가 Resource Server의 자원에 접근하기 위한 키를 포함한 값
• 갱신 토큰(Refresh Token) : 유효기간이 지난 Access Token을 갱신하기 위해 사용되는 값

인증과정

네이버 아이디로 로그인

<네이버 아이디로 로그인>은 OAuth 2.0 기반의 사용자 인증 기능을 제공해 네이버가 아닌 다른 서비스에서 네이버의 사용자 인증 기능을 이용할 수 있게 하는 서비스입니다. 별도의 아이디나 비밀번호를 기억할 필요 없이 네이버 아이디로 간편하고 안전하게 서비스에 로그인할 수 있어, 가입이 귀찮거나 가입한 계정이 생각나지 않아 서비스를 이탈하는 사용자를 잡을 수 있습니다.

<네이버 아이디로 로그인>을 통해 로그인하는 기본 절차는 다음과 같습니다.

1. 로그인 (네이버 앱이 설치되어 있다면 네이버 앱의 간편 로그인 기능으로 로그인, 네이버 앱이 설치되지 않았다면 애플리케이션에서 인앱 브라우저가 실행되고 네이버 로그인 화면으로 이동한다.)
2. 사용자가 네이버 아이디로 로그인하면 사용자 정보에 동의하는 화면으로 이동한다.
3. 사용자가 정보 제공에 동의하면 콜백 URL로 애플리케이션에 접근 토큰(access token)이 발급된다. 발급받은 접근 토큰을 이용해 OAuth 2.0을 지원하는 네이버의 오픈 API를 사용하거나 사용자의 정보를 얻어 올 수 있다.

특징

네이버 아이디로 로그인한 사용자의 이름, 메일 주소, 별명, 프로필 사진, 생일, 연령대, 성별 등을 API로 간단하게 조회할 수 있습니다.

적용 칠자

1. 애플리케이션 등록
   네이버 아이디로 로그인을 적용하기 위해 애플리케이션을 등록하고 클라이언트 아이디와 클라이언트 시크릿 키를 발급받는다.
2. 애플리케이션 개발
   네이버 아이디로 로그인을 이용하기 위한 정보를 확인하고 등록한 환경에 맞는 개발가이드를 참고해 애플리케이션을 개발한다.
   - Android 튜토리얼 참고
3. 서비스 적용
   개발을 완료하면 서비스에 네이버 아이디로 로그인을 적용한다.

결과

8월을 마지막으로 1년 2개월의 스타트업 생활을 마치고, 이번 하반기 신입 채용과정을 거쳐 3곳에 합격했습니다. 퇴사 후 부랴부랴 취업준비를 시작했는데, 이번 포스팅에서는 취업준비를 하며 어떤 식으로 전공 지식과 직무 면접을 준비했는지 다뤄보겠습니다!

자료구조와 알고리즘

제일 먼저 준비했던 과목은 자료구조와 알고리즘이었습니다. 제 경우 자료구조와 알고리즘이 다른 전공에 비해 많이 부족해서 가장 먼저 공부를 시작했습니다.
대부분 기업이 서류 통과 후 바로 온라인 코딩 테스트 과정이 있기 때문에, 처음부터 차근차근 이론을 공부하고 문제를 푸는것은 시간상 불가능하다고 생각했습니다. 그래서 코드플러스 - SW 역량 테스트 대비 강의를 통해 자주 출제되는 알고리즘들의 유형을 빠르게 익히고 비슷한 문제를 풀어보는 연습을 했습니다.

저는 대표적인 유형의 알고리즘 같은 경우는 코드를 외울 정도로 자주 봤습니다. 사람마다 다르겠지만 제 경우에는 어느정도 문제의 틀이나 해법을 외워두니 비슷한 유형의 문제는 빠르게 풀 수 있었습니다. 처음 코딩 테스트를 준비하시는 분이라면 저처럼 대표적인 유형의 해법 정도는 외워두는게 도움이 많이 될 것 같다고 생각합니다. (당연히 이해를 바탕으로 외워야 합니다.)

자료구조와 알고리즘의 경우 온라인 코딩 테스트를 통과하더라도 다음 절차인 (직무)면접에서도 빠지지 않고 등장하는 과목입니다. 저도 온라인 코딩 테스트를 통과한 후에는 방향을 바꿔서 문제를 많이 풀기보다는 자료구조의 공부에 조금 더 초점을 맞췄습니다. 이 과정에서는 부경대학교 권오흠 교수님 - 알고리즘 강의가 큰 도움이 됐습니다.

운영체제

운영체제의 경우 학부생 때 가장 재밌게 공부했던 과목중 하나이다 보니 어느정도 자신있었습니다. 이화여자대학교 반효경 교수님 - 운영체제 강의를 듣고 운영 체제와 정보기술의 원리 책을 통해서 복습하며 빠르게 개념을 다잡았습니다.

운영체제 과목의 경우 학부생 때 공부했을 때와는 다른 느낌이었습니다. 특히 스레드와 프로세스, 경쟁 상태 부분은 제가 주로 사용하는 Node.js의 특징을 이해하는데 큰 도움이 되었습니다. 단순히 개념공부로 끝나는 것이 아닌 실제 이러한 개념이 어떤 환경에서 어떻게 사용되고 있는지 그리고 그로 인해 어떠한 장단점이 있는지를 연관지어 생각해볼 수 있었습니다.

데이터베이스

데이터베이스는 아키텍처 구성(다중화), 트랜잭션과 동시성 제어에 중점을 맞춰 공부했습니다. 당연히 기본적인 개념은 숙지하였고, 제가 했던 프로젝트라던가 어떤 서비스를 구축함에 있어 어떻게 아키텍처를 구성해야 하는지 고민해본것이 면접에 가서 도움이 많이 되었습니다.
위와 같은 내용을 공부함에 있어 데이터베이스 첫걸음이라는 책이 큰 도움이 되었습니다.

그 외 전산학

저는 Tech Interview For Beginner를 통해서 위의 전공들 뿐만 아니라 그 외 과목들에서 필요한 부분을 공부했습니다. 예비 개발자들의 기술 면접 준비를 위한 자료를 정리해놓은 Repository로서 신입 개발자로 취업을 준비하시는 분이라면 많은 도움을 받으실 수 있을 것입니다.

나만의 강점

제가 이번 하반기에 3곳에 최종합격 할 수 있었던 저만의 강점을 생각해 본다면 크게 두가지인것 같습니다.
첫 번째로 개인 블로그와, 개인 프로젝트입니다. 저는 면접을 보며 개발에 대한 애착 혹은 자기 자기계발에 관련된 질문에는 항상 블로그와 개인 프로젝트를 통해 어필했습니다. 어떤 행동이나 습관으로 끝나는 것이 아닌 그로인한 결과물을 갖고 어필을 했던것이 큰 도움이 되었습니다.
두 번째는 서비스를 직접 개발하고 운영해보았다는 점입니다. 1년 2개월 동안 스타트업에서 동료들과 함께 서비스를 기획하고 개발하고 운영했던 경험이 가장 큰 도움이 되었습니다. 단순히 학교 과제나 동아리 활동에서 결과물을 내는 것이 아니라, 실제 사용자에게 서비스를 하기 위한 개발은 여러가지 면에서 차이가 있다고 느꼈습니다. 그런 면에서 항상 고민하고 선배 개발자 분과 이야기를 자주 나눴습니다. 제가 생각하고 고민한 방법에 대해 말씀드리고 그로 인해 다시 생길 수 있는 문제점을 생각해보고 개선해 나가는… 이런 과정들이 면접에 가서 가장 큰 도움이 되었습니다. 실제 면접에 가도 면접관 분들은 지원자가 했던 프로젝트에 대해 물어보시면서 추가적으로 어떤 문제점을 추가로 주고, 이를 면접자가 자신의 전산지식을 바탕으로 해결해가는 과정을 많이 보시는것 같습니다.

마지막으로 드리고싶은 말씀

간혹 제 주변 친구들 혹은 지인들이 물어봅니다. 신입 개발자로 취업하기 위해서는 어떤것을 준비해야 하는지, 내가 지금 프로젝트를 더 해야하는지, 영어 점수를 더 올려야 하는지…
저는 먼저, 꼭 기본적인 전산학에 대한 공부부터 하시기를 추천드립니다. 결국에는 내가 프로젝트를 하고 그 프로젝트를 자소서에 적더라도, 면접에 가서는 면접관님들은 프로젝트로부터 기본적인 전산학에 관련된 내용을 요구합니다. 그렇기 때문에 꼭 기본적인 전산학 공부를 탄탄히 하시길 바랍니다. 그 후에는 자신이 했던 프로젝트로부터 관련된 전산학 내용을 꼭 정리해보셨으면 좋겠습니다. (예를 들어, Node.js를 사용했다면 Node.js의 특징인 비동기 방식에 대해 운영체제 관점에서 설명할 수 있어야 합니다.)
이 부분만 잘 되었다면 면접에서 어려운 질문을 받더라도, 면접관님과 대화를 하면서 문제에 접근하고 조금씩은 풀어갈 수 있는 능력이 생길거라고 생각합니다.

(주)두다지 서버개발자 양성 교육 프로그램

두다지의 **서버개발자 양성 교육 프로그램**은 제가 스타트업에 있을때 많은 도움을 받았던 선배 개발자분께서 기획하고 진행하시는 프로그램입니다. 프로그램을 운영하고 계시는 홍석환 멘토님은 제가 대학생일때 멘토 멘티로 만나 스타트업에서의 생활, 그리고 취업을 준비하면서도 계속해서 많은 도움을 주셨습니다.
스스로 다시 한 번 전산학 내용을 정리할 수 있는 시간을 가지며 기본을 탄탄히 하고, 학생때는 단순히 학점만을 위해 공부하며 키워온 제 전산학 지식을 쌓아왔다면 실제 실무에서는 어떻게 사용되는지, 필요로 하는지 다양한 경험을 통해 체감할 수 있게 해주셨습니다.
제가 과거에 멘티로서 선배 개발자분께 배웠던 과정은 교육 과정에서 확인해 볼 수 있습니다. 교육 과정의 더 자세한 내용과 과정을 수료한 멘티들의 후기도 이곳에서 확인할 수 있습니다.
제가 생각하는 신입개발자에게 필요한 것은 단순히 전산지식을 얼마나 많이 아느냐가 아니라, 내가 앞으로 개발하면서 그동안 공부 했던 전산지식을 바탕으로 얼마나 잘 이해하며 활용할 수 있는지 그 능력이 필요하다고 생각합니다. 두다지 교육 프로그램은 그 능력을 키울 수 있도록 방향을 잡아줄 것입니다. 관심이 있으신분은 주저하지 마시고 꼭 연락을 드려보세요!

우선순위 큐 (Priority queue) 란?

큐는 여러개의 데이터를 넣을 수 있는 자료구조 입니다. 데이터가 넣고 뺄때는 First In First Out(FIFO) 구조를 가집니다.

우선순위 큐는 이러한 큐의 한종류로써 최대 우선순위 큐와 최소 우선순위 큐로 나뉩니다.

최대 우선순위 큐

최대 우선순위 큐는 다음의 두가지 연산을 지원하는 자료구조 입니다. (최소 우선순위 큐는 EXTRACT-MAX 대신 EXTRACT-MIN을 지원하는 자료구조입니다.)

1. INSERT(x) : 새로운 원소 x를 삽입
2. EXTRACT_MAX() : 최대값을 삭제하고 반환

MAX HEAP을 이용해서 최대 우선순위 큐를 구현할 수 있습니다.

INSERT

위의 그림은 MAX HEAP의 형태로 저장되어 있는 우선순위 큐 입니다. 현재 heap은

1. complete binary tree
2. max heap property
   조건을 만족하기 때문에 이를 유지하면서 INSERT 연산을 하기 위해서는 고려할 사항들이 있습니다.

INSERT는 새로운 노드를 추가해야하는데 complete binary tree 를 만족하기 위해서는 가장 마지막 레벨의 leaf에 추가 될 수 밖에 없습니다. 그리고 새로운 노드가 추가된 후 max heap property를 만족하기 위해서는 max-heapify 연산이 필요합니다.
INSERT의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9

MAX-HEAP-INSERT(A, key){
    heap_size = heap_size + 1;
    A[heap_size] = key;
    i = heap_size;
    while(i > 1 and A[PARENT(i)] < A[i]){
        exchange A[i] and A[PARENT(i)];
        i = PARENT(i);
    }
}

위의 코드에서 A는 heap의 사이즈를 1증가 시키고, 그 자리에 새로운 key값을 넣습니다. i는 새로 추가된 노드의 인덱스입니다.
그 후 while 문에서 i > 1 (root 노드가 아니라는 의미) 이며, A[PARENT(i)] < A[i] (부모 노드에 저장된 값보다 크다는 의미) 라면 부모 노드와 값을 교환합니다.

즉, 루트 노드가 될 때까지 혹은 자신의 부모 노드보다 작을 때 까지 계속해서 교환연산을 진행합니다. 따라서 시간 복잡도는 트리의 높이에 비례하게 되고, heap은 complete binary tree이므로 O(nlogn)입니다.

EXTRACT_MAX

위의 그림은 EXTRACT_MAX 과정을 나타내고 있습니다. heap은 complete binary tree 성질을 유지하기 위해서 아무 노드나 삭제하는 것이 아니라 마지막 노드를 삭제하게 됩니다. 이때 루트 노드와 마지막 노드의 자리를 변경해 마지막 노드를 삭제 후 max-heapify를 통해 다시 max heap property를 만족하도록 만들 수 있습니다.
HEAP-EXTRACT-MAX의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9

HEAP-EXTRACT-MAX(A){
    if heap-size[A] < 1
        then error "heap underflow"
    max <- A[1]
    A[1] <- A[heap-size[A]]
    heap-size[A] <- heap-size[A] - 1
    MAX-HEAPIFY(A, 1)
    return max
}

C++로 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void max_heap_insert(int a[], int size, int key) {
    int i, tmp;

    size = size + 1;
    a[size] = key;

    i = size;
    while (i > 1 && a[i / 2] < a[i]) {
        tmp = a[i / 2];
        a[i / 2] = a[i];
        a[i] = tmp;
        i = i / 2;
    }
}

int heap_extract_max(int a[], int size) {
    if (size < 1) {
        cout << "heap underflow\n";
        return -1;
    }

    int max = a[1];
    a[1] = a[size];
    max_heapify(a, size-1, 1);
    return max;
}

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님

저번 포스팅에서는 힙(Heap)과 max-heapify에 대해 알아보았습니다. 이번 포스팅에서는 직접 1차원 배열을 heap 구조로 변경한 후 힙 정렬을 해보겠습니다.

1차원 배열을 힙(Heap) 으로 만들기

먼저 의사 코드는 다음과 같습니다.

1
2
3
4

BUILD-MAX-HEAP
    heap-size[A]<-length[A]
    for i <- |length[A]/2| downto 1
        do MAX-HEAPIFY(A,i)

i가 A 배열의 길이 / 2 부터 시작하는 이유는 리프 노드에서는 max-heapify 과정이 필요 없기 때문입니다.

힙을 만드는데의 시간 복잡도는 다음과 같습니다.
MAX-HEAPIFY 연산의 시간 복잡도는 log(n) 입니다. 그런데 for 문이 n/2 돌기 때문에 n/2*log(n)이며 빅 오로 표기하면 O(n*log(n))이 됩니다.
이는 루트 노드만 고려하여 상당히 러프하게 계산한 것이기 때문에, 정확하게 계산한다면 시간 복잡도는 **O(n)**이 됩니다.

힙 정렬(Heap sort) 하기

힙 정렬은 다음과 같은 순서로 실행됩니다.

1. 주어진 데이터를 힙으로 만든다
2. 힙에서 최대값(루트 노드)을 가장 마지막 값과 바꾼다.
3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 마지막 값은 힙의 일부가 아닌것으로 간주한다.
4. 루트 노드에 대해서 HEAPIFY(1)한다.
5. 2~4번을 반복한다.

데이터를 힙으로 만들면 인덱스 1의 값이 가장 최대값 이므로 마지막 값과 바꿉니다.
그리고 마지막값은 정렬된 값으로 간주하고 더 이상 신경쓰지 않아도 됩니다.
그렇게 줄여나간다면 결국 정렬된 상태의 배열이 완성됩니다.

힙 정렬의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6

HEAPSORT(A)
    BUILD-MAX-HEAP(A)             // O(n)
    for i <-heap-size downto 2 do // n-1 times
        exchange A[1] <-> A[i]    // O(1)
        heap_size <- heap_size -1 // O(1)
        MAX-HEAPIFY(A,1)          // O(log(n))

총 시간 복잡도는 **nlogn**이 됩니다.

C++로 힙 정렬 구현하기

다음과 같이 C++로 힙 정렬을 구현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
#include <stdlib.h>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void max_heapify(int a[], int size, int idx) {
    int left = idx * 2;
    int right = (idx * 2) + 1;
    int largest = idx;
    int tmp = 0;

    // 왼쪽 자식 노드와 비교
    if (left < size && a[left] > a[largest]) {
        largest = left;
    }

    // 오른쪽 자식 노드와 비교
    if (right < size && a[right] > a[largest]) {
        largest = right;
    }

    // 부모 노드보다 자식 노드가 큰 경우 교환
    if (largest != idx) {
        tmp = a[largest];
        a[largest] = a[idx];
        a[idx] = tmp;
        // 재귀 호출
        max_heapify(a, size, largest);
    }
}

void build_max_heap(int a[], int size) {
    for (int i = size / 2; i > 0; i--) {
        max_heapify(a, size, i);
    }
}

void heap_sort(int a[], int size) {
    int tmp = 0;

    build_max_heap(a, size);
    for (int count = size - 1; count > 0; count--) {
        // 루트 노드를 가장 마지막 노드와 교환
        tmp = a[count];
        a[count] = a[1];
        a[1] = tmp;
        // 힙 구조 유지
        max_heapify(a, count, 1);
    }
}

int main() {
    int a[ITEM_SIZE] = { 0, }; // 루트 노드는 1번 인덱스 부터 시작
    for (int i = 1; i < ITEM_SIZE; i++) {
        a[i] = (rand() % (ITEM_SIZE * 10)) + 1;
    }

    print_arr(a, ITEM_SIZE);
    heap_sort(a, ITEM_SIZE);
    print_arr(a, ITEM_SIZE);
    return 0;
}

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는 정렬 알고리즘입니다.

힙 정렬의 특징은 다음과 같습니다.
1.최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.
2.힙 정렬은 알고리즘을 구현하는데 추가적인 배열이 필요하지 않다.
3.이진 힙(바이너리 힙) 자료구조를 사용한다.

먼저 힙 정렬을 구현하기 전에, 힙 이라는 자료구조에 대해 알아보겠습니다.

힙(Heap) 이란?

힙(Heap)은

1. complete binary tree(완전 이진 트리) 이면서
2. heap property를 만족해야 합니다.

위의 그림에서는 **full binary tree(포화 이진 트리)**와 **complete binary tree(완전 이진 트리)**에 대해 설명하고 있습니다.

binary tree(이진 트리)란 한 노드가 최대 2개의 자식 노드를 가지는 트리 입니다. 따라서, 위의 2개 트리는 모두 이진 트리입니다. 이진 트리는 이진 탐색 트리(BST)와 이진 힙(Binary Heap)의 구현에 흔히 사용됩니다.

full binary tree(포화 이진 트리)란 이진 트리중에 모든 레벨의 노드 들이 꽉 차있는 형태를 말합니다.

complete binary tee(완전 이진 트리)는 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽 부터 연속된 몇개의 노드가 비어있을 수 있는 트리를 말합니다. 따라서 포화 이진 트리는 완전 이진 트리이기도 합니다.

위의 2번째 조건에서 heap property를 만족해야 한다고 했습니다. 이 heap property는 2개의 조건으로 나누어집니다.

1. max heap property - 부모 노드는 자식 노드보다 데이터가 크거나 같다.
2. min heap property - 부모 노드는 자식 노드보다 데이터가 크거나 작다.

max와 min 모두 대칭적 관계이므로 모든 알고리즘에 적용되나 상황에 따라서 간단하게 사용할 수 있는 것을 씁니다. 여기서는 max-heap property를 다루겠습니다.

(a)의 3개 트리는 모두 heap 입니다. (완전 이진 트리이면서 heap property를 만족합니다.)
(b)의 3개 트리는 heap이 아닙니다. (완전 이진 트리이지만, (max)heap property를 만족하지 않습니다.)
(c)의 2개 트리도 heap이 아닙니다. (완전 이진 트리를 만족하지 않습니다.)

위의 (a), (b), (c)는 모두 다 heap입니다.
(a), (b), (c)는 동일한 데이터를 갖고 있는 서로 다른 heap입니다. 즉, 여러가지 모양의 heap이 존재할 수 있는 것입니다.

Heap은 1차원 배열을 사용해 표현할 수 있습니다. 같은 레벨에서 왼쪽부터 배열로 저장하면 1차원 배열이 됩니다. 일반적인 트리에서는 부모 자식간의 관계를 식을 통해 표현할 수 없지만 Heap은 complete binary tree이므로 배열의 인덱스만으로 부모와 자식의 관계를 표현할 수 있습니다. 루트 노드가 배열의 1번 인덱스부터 시작한다면 다음과 같은 표현식을 사용할 수 있습니다.

• 루트 노드 : A[1]
• A[i]의 부모 노드 : A[i/2]
• A[i]의 왼쪽 자식 노드 : A[2i]
• A[i]의 오른쪽 자식 노드 : A[2i+1]

따라서 Heap은 1차원 배열을 통해 표현이 가능하기 때문에 불필요하게 트리 자료구조를 따로 만들어 사용해 구현할 필요가 없습니다.

Max-heapify 란?

지금부터는 어떤 1차원 배열의 데이터가 있을 때 이 1차원 배열을 Heap으로 변환하는 과정에 대해 알아보겠습니다. (이번 포스팅에서는 max heap만을 다루기로 했으므로 max heap을 만드는 방법에 대해 알아보겠습니다.)
일반 1차원 배열은 max-heapify라는 연산 과정을 통해 max heap으로 만들수 있습니다.

max-heapify 연산을 하기 위한 전제조건을 위의 그림에서 보여주고 있습니다.

1. 트리의 전체 모양은 complete binary tree이다.
2. 왼쪽 서브 트리(subtree)는 그 자체로 heap이다.
3. 오른쪽 서브 트리(subtree)는 그 자체로 heap이다.

여기서 유일하게 루트 노드만이 heap property를 만족하지 않을때, max-heapify 연산을 통해 heap property를 만족하게 만들 수 있습니다.

위의 그림에서 루트 노드는 자신의 자식 노드중에 더 큰값과 자리를 교체 합니다. 그 후 교체된 노드에서 다시 max-heapify 연산을 통해 max-heap property를 만족할 때까지 반복합니다.

결국 max-heapify는 동일한 과정을 반복하고 있기 때문에 **recursion(재귀)**로 구현이 가능합니다.

1
2
3
4
5
6
7
8
9

MAX-HEAPIFY(A, i){
    if there is no child of A[i]
        return;
    k <- index of the biggest child of i;
    if A[i]>=A[k]
        return;
    exchange A[i] and A[k];
    MAX-HEAPIFY(A, k);
}

첫번째 조건은 base case로서, 자식 노드가 없다면 가장 아래의 레벨에 위치한 리프노드이기 때문에 종료합니다. 만약 자식 노드가 있다면 큰 자식 노드의 인덱스를 k로 지정합니다. 그 후 부모 노드와 값을 비교해 부모 노드가 크다면 max-heapify 과정을 종료하고, 자식 노드의 값이 크다면 부모 노드와 값을 교환한 후 다시 max-heapify를 재귀 호출 합니다.

1
2
3
4
5
6
7
8
9

MAX-HEAPIFY(A, i){
    while A[i] has a child do
        k<- index of the biggest child of i;
        if A[i]>= A[k];
            return;
        exchange A[i] and A[k];
        i=k;
    end
}

같은 함수를 iterate하게 구현한 코드입니다. 주요 함수의 동작 원리는 같습니다.

max-heapify의 시간 복잡도는 루트 노드로부터 마지막 레벨까지 비교, 교환 연산을 하므로 트리의 높이보다 많은 시간이 필요하지 않습니다. 따라서 시간 복잡도는 높이에 의해서 결정되며, O(h)입니다.
일반적인 이진트리가 아닌 complete binary tree이므로 노드의 개수를 n이라 하면, **시간 복잡도는 O(logn)**이 됩니다.

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님