Browse Author: sungjin

[알고리즘]알고리즘 설계의 다섯가지 접근법

코딩인터뷰 완전분석 (게일 라크만 맥도웰 지음 ) 을 공부하면서 작성하는 글입니다.

알고리즘 문제를 풀기위한 설계는 5가지의 접근법이 있다.

  1.  예증
    일반적 규칙을 유도해내서 문제를 해결한다.
    ex) 거리, 시간 그리고 속도에 관한 문제 해결
  2. 패턴매칭
    기존의 문제와 유사한 문제를 떠올리고 그 문제의 해답(가령 알고리즘)을 수정해서 적용한다.
  3. 단순화와 일반화
    자료형이나 데이터 양과 같은 제약조건을 변경해서 문제를 단순화 해본다.
    단순화 된 버전의 문제를 해결한다면 최종적으로 일반화해서 찾은 알고리즘을 복잡한 형태로 다듬어 간다.
  4. 초기사례로부터의 확장
    초기사례(n=1)에 대해 문제를 푼다. 후에 n=2에 대한 문제를 풀어보고 n=3를 풀어본다.
    이후 N-1을 안다면 N을 어떻게 찾을 수 있을지 고민해보고 규칙을 찾아 문제를 해결한다.
  5. 자료구조 브레인스토밍
    일련의 자료구조를 차례대로 적용해보고 적절한 알고리즘을 찾아나가는 방법이다.
    연결리스트? 이진트리? 힙? 처럼 여러 자료구조를 이해하고 적응시킬 수 있는 능력이 중요하다.

이렇게 5가지 접근법으로 문제를 풀어나가 보자. 물론 기본적인 자료구조에 대한 이해는 반드시 필요하다.

출처 : 코딩인터뷰완전분석

2급수표

코딩인터뷰 완전 분석이라는 책을 보면 2급수표를 먼저 외우라고 요구한다.

2의 10승 까지야 보통은 외우고 있을 테지만..

그 후에 2의 16이 64K이고 2의 20승이 1MB 이며 2의 30승이 1GB 이라는 점은 외워두자

x 2^x 근사값 메모리 요구량(Bytes)
7 128
8 256
10 1,024 1,000(천) 1K
16 65,536 64K
20 1,048,576 1,000,000(백만) 1MB
30 1,073,741,824 1,000,000,000(십억) 1GB
32 4,294,967,296 4GB
40 1,099,511,627,776 1,000,000,000,000(조) 1TB

 

 

*출처 : https://github.com/loustler/data-structure-algorithm/wiki/2%EA%B8%89%EC%88%98%ED%91%9C(Power-of-2)

[20170708]근황

지난 3월부터 신입사원으로 취준을 준비하면서 정말 쉽지 않은 시간들을 보냈다.

자기소개서를 작성하고 결과를 기다리며 취업 카페나 채용사이트를 수없이 드나들며 결과를 노심초사하며 기다렸다. 인적성 날짜가 나오면서 쉴새 없이 기출 문제들을 풀어보며 점수를 올렸고 시험당일에는 마치 수능날같은 마음가짐으로 시험에 임했다. 면접은 쉬운가? 면접관들은 내가 준비한 갑옷들을 한겹한겹 벗겨나가며 나를 벌거숭이처럼 만들었다.

긴 채용 프로세스가 끝나고 마침내 나는 회사와 내가 서로 마음이 맞는 곳을 찾을 수 있었다. 이제 다시 신입으로 시작한다. 프로답게 잘하자. 나의 각오다.

그리고 진심으로 대한민국 취업준비생 모두 화이팅 !

[Java]Java 8

Java 8은 2014년 발표된 Java의 Version 8 이다.

Java 5 이후로 Version  6, 7 도 있었지만 Version 8이 중요한 이유는 언어 자체에 변화가 있었던 버전업이기 때문이다. 그래서 Java에 대한 지식을 누군가가 물어본다면 Java 8에 대한 점은 기존의 자바 언어와 별개의 언어처럼 물어보는 경우도 있다. 그만큼 Java 8은 새로운 세상이다.

가장 큰 특징은 Lambda, Map , Filter 같은 함수형 언어의 여러 개념이 도입한 것이다.

함수형 언어에 대한 이야기는 http://kwangshin.pe.kr/blog/2013/01/21/번역-함수형-프로그래밍functional-programming-기초 에서 확인할 수 있다.

함수형 언어의 특징을 이해하면 왜 Java 8이 함수형 언어의 개념을 도입했는지 이해할 수 있다. 프로세서의 성능이 높아짐에 따라 소프트웨어는 그것을 활용할 수 있는 방향으로 발전해나가야 하기 때문이다.

[20170305]근황

작년 이맘때즘이다. 한국을 떠나 홍콩으로 이사했고 한참 우울한 홍콩 날씨 속에서 일자리를 찾고 있었다.

그리고 1년이 지난 지금, 홍콩을 다시 방문했다.

아침에 일어나 구룡공원 수영장에서 수영을 하고 215X를 타고 KwunTong으로 출근해서 아침을 먹고,  챠챠틴을 찾아 점심을 먹고, 다시 퇴근하는 지난 1년간의 삶을 다시 한번 살아봤다.

좁은 사무실에서 개발자 4명이 서로 둘러 앉아 영어인지 중국어인지 한국말인지 혹은 필리핀어인지 알 수 없는 언어들로 대화를 하고 살아가는 것. 가끔 침사추이로 또는 센트럴로 나가 맥주 한잔 하는 것. 그것이 내가 지냈던 홍콩 생활이였다.

그러나 이제, 홍콩 계좌도 닫고 휴대폰 계약도 종료시키고 옥토퍼스 카드의 잔금도 모두 다 사용했다. 이젠 한국에 적응해야지.

내가 지냈던 홍콩에서의 삶이 마치 20대 초반 보냈던 군생활처럼 인생의 안주가 되기를 바란다. 그래서 이제 내 앞에 놓은 건조하고 답답한 일상들 속에서 언제든 꺼내 마실 수 있는 탄산수 같은 시원함이 되기를 바란다.

페이스북을 보다가 어느 청년의 이야기를 보았다. 카이스트를 졸업하고, 자발적 백수로 지낸다는 그 청년의 이야기는 20대 초반 내가 호주에서 선택 할 수 있었던 갈림길을 떠올리게 하였다. 그때 나는 모아둔 돈으로 세계여행을 다니느냐 어학연수를 가느냐 선택할 수 있었다. 나의 선택은 어학연수 였고, 페이스북 청년의 선택은 여행 이였겠지. 세계여행을 다니며 수많은 경험을 했다는 그를 보면서, 그 여행의 끝에는 뭐가 있는지 나중에 나에게 알려달라고 이야기 하고 싶다.

내 여행은 다시 시작 될 수 있을까.

publish/subscribe model

구글의 GCM(이전엔 FCM으로 불렸음)을 사용면서 GCM이 가진 많은 기능 중 Topic 메세지를 사용할 케이스가 있었다.  Topic 메세지는 publish/subscribe model에 기반을 둔 push service인데, 그 과정은 아래와 같다.

서버 혹은 메세지를 보내는 주체가 메세지를 publish 하면 메세지의 발송 성공 여부는 확인하지 않는다. 그냥 publish 할 뿐이다. 한편, 해당 토픽에 대해 subscribe를 한 subscriber들은 메세지가 publish 되면 해당 메세지를 수신 할 수 있게 된다. 결국 publish/subscribe 모델에서는 publisher와 subscriber들은 서로를 알필요가 없다. 각자의 역활(메세지를 publish/메세지를 수신)만을 수행하면 되는 모델인 것이다.

publish/subscribe 모델이 작동하기 위해서는 publish 된 메세지가 해당 토픽을 선택한 subscriber에게 메세지가 발송 되도록 중간에서 브로커 역활을 하는 모듈이 존재한다.

이렇게 publish/subscribe 모델 기반의 시스템의 경우 publisher와 subscriber 간에 낮은 결합도를 가진 시스템을 구축 할 수 있으며 이를 통해 시스템 확장성에 있어 큰 장점을 가질 수 있게 된다.

그러나, 메세지 전송에 대한 정확한 피드백을 받기가 어렵고 악의적인 메세지가 publish 되었을때 브로커가 그것을 필터링하는데 어려움이 존재한다.

 

참고: http://blog.naver.com/PostView.nhn?blogId=hisukdory&logNo=50109265674 , https://developers.google.com/cloud-messaging/topic-messaging

 

 

 

2월달 목표-개발

http://d2.naver.com/helloworld/206816 글에서 The Architecture of Open Source Applications 을 소개하고 있다. 

해당 글은 Scalable Web Architecture and Distributed Systems 번역 해놓은 훌륭한 포스트지만, Aosabook의 다른 글들도 공부해야 겠다는 생각에 목표를 적어본다.

  1. git – http://aosabook.org/en/git.html
  2. nginx – http://aosabook.org/en/nginx.html

두개의 포스트를 읽고 정리하는 글을 블로그에 남겨보자.

역시 영어를 잘해야.. ㅠ

[디자인패턴]Factory 패턴

팩토리라는 단어처럼 인스턴스를 생성해주는 팩토리(sub class)가 존재하고 새로운 객체를 원할 경우 팩토리를 통해 생성하는 패턴.

Spring 프레임워크에서 자주 사용되는 패턴으로 캡슐화 , 유연성 , 느슨한 관계의 장점을 가질 수 있다.

팩토리 패턴의 경우 팩토리 라는 단어를 통해 직관적으로 이해하기 쉬우며 실제로 코드를 보면 쉽게 이해할 수 있는 패턴이다.

참고 : https://blog.seotory.com/post/2016/08/java-factory-pattern

[디자인패턴]visitor 패턴

조금 이해하는게 쉽지는 않다.(재귀 관계적 사고가 필요함)

천천히 봐보자.

먼저 위키피디아에 따르면 visitor 패턴(방문자 패턴)은 알고리즘(동작)을 객체 구조에서 분리시키기 위한 패턴이다. 이렇게 분리 하면 구조의 변화 없이 새로운 동작을 추가시킬 수 있다는 장점을 가지게 된다.(…… 이걸보고 이해가 안되는건 나만인가)

visitor 패턴은 컴포지트 패턴과 관련이 있다.(위키피디아에서는 같이 보기로 컴포지트 패턴 링크 제공)

가령, Car 라는 객체가 있다면 visitor 패턴에서는 Car는 Wheel 과 Handle을 가진 구조체(객체구조)가 된다. 이때 Visitor는 car객체내의 Wheel과 Handle 의 가격을 확인하는 알고리즘(동작)을 가지게 되는데(해당 알고리즘은 visit 메소드로 구현) 후에 Wheel의 마모 정도를 확인하는 알고리즘을 추가하고 싶다면 visitor를 추가하는 식으로 알고리즘을 추가할 수 있다.

이렇게 작동하는 것이 visitor패턴의 알고리즘과 객체구조 분리라고 이해.

[디자인패턴]prototype pattern

프로토타입 패턴은 프로토타입(원형)을 만들어 놓고 그것을 clone 하여 사용 하는 방법이다.

new 를 사용하여 객체를 생성 하는것이 비용이 크거나 , 기존의 객체와 비슷하지만 일부만 변경된 객체를 사용하는 경우 사용할 수 있다.

가령, 그랜져와 K7 라는 객체가 필요한데 사실 둘은 공통의 플랫폼을 사용하기 때문에 car라는 프로토타입(원형)을 만들어 놓고 그랜져와 k7이라는 객체가 필요할 때마다 프로토타입을 clone 하여 사용하면 car라는 객체를 초기화 할때 필요한 비용(필드 값을 설정하는등)을 줄 일 수 있다.

이때 원형을 구현하고 복제된 객체를 던져주는 부분은 팩토리 패턴과 함께 사용 될 수 있으며, 구현에 있어 싱글톤 패턴을 사용 할 수 있다.

프로토타입 패턴을 활용한 프로그래밍을 프로토타입 프로그래밍이라고 부를 수 있는데, 이는 클래스 기반 프로그래밍에서 상속을 이용해 객체간의 관계를 설정하는 것과 다르게 프로토타입(원형)을 기반으로 객체를 사용 하는 프로그래밍 기법이다.

Java에서는 Cloneable 인터페이스를 구현하여 프로토타입 패턴을 구현할 수 있다.

참고 : https://ko.wikipedia.org/wiki/%ED%94%84%EB%A1%9C%ED%86%A0%ED%83%80%EC%9E%85_%ED%8C%A8%ED%84%B4