전체 글

해설남자와 여자의 수가 n명으로 일치하고, 서로의 선호도를 리스트로 받기 때문에 gale-shapley 알고리즘으로 풀이할 수 있다.코드import sysinput = sys.stdin.readlinet = int(input())def stable_marriage(men_preferences, women_preferences): n = len(men_preferences) free_men = list(range(n)) women_partners = [None] * n men_next_proposal = [0] * n men_partners = [None] * n women_rankings = [] for wp in women_preferences: ..

안정 결혼 문제를 푸는 알고리즘을 구현하는 것이다. 안정 결혼 문제(Stable Marriage Problem)은 예전부터 제시됐던 문제이다. 남자와 여자가 각각 n명으로 같은 수의 집합이 주어지고, 서로 원하는 상대방에 대한 선호도를 리스트로 가지고 있다. 이를 해결하기 위한 도전은 안정 매칭(Stable Matching)을 모두 구현해야 한다. 안정 매칭이란 일대일로 남자와 여자를 매칭하는데, f ∈ F가 현재 파트너보다 m ∈ M을 선호하고 m이 현재 파트너보다 f를 선호하는 쌍(m, f)이 없는 경우 매칭을 안정적이라고 합니다. 다른 안정된 결혼 B가 없는 경우, 어떤 남성이든 A에 배정된 여성보다 더 선호하는 여성과 짝을 이루는 안정된 결혼 A를 남성 최적이라고 합니다. 선호하는 남성과 여성의 ..

개발을 처음 시작하며 프레임워크에 대해서 공부했을 때에는 단순히 어떻게 코드를 작성해야 데이터를 보내고 받을 수 있는 지에 대해서만 고민하기 시작했다. 점점 다양한 API를 만들어가고 다양한 사람들과 협업하면서 RESTful한 아키텍처를 지키려고 노력하게 되었다. 대부분의 레퍼런스가 모두 이 RESTful 원칙을 지켜서 API를 만든다. 그래서 별 생각 없이 은연중에 따라 RESTful을 지켜 개발하곤 한다. 오늘은 이러한 RESTful이 뭔지 자세히 정리해보려고 한다. 본론API란?먼저 API는 Application Programming Interface의 약자이다. 이 API라는 것을 통해서 어플리케이션의 데이터를 주고받을 수 있다는 것이다. 그렇게 생각하면 이 API라고 하는 것의 범위가 굉장히 넓..

개발자라면 자신이 그동안 만들었던 서비스들을 보여줄 수 있는 포트폴리오가 있으면 좋을 것이다. 특히 개발자라면 웹을 통해서 자신의 포트폴리오를 보여주는 것이 하나의 재미인 것 같다. 웹 개발을 모르는 사람이 개인 포트폴리오 사이트를 보면 엄청나다고 생각하는 경우도 꽤 있지만 사실 개발자의 입장에서는 그렇게 어려운 일이 아니다. 직접 포트폴리오 사이트를 만들 수도 있고, 다양한 방법으로 호스팅 할 수도 있는 것이다. 이번 포스팅에서는 간단하게 포트폴리오 웹사이트를 만드는 방법을 서술할 예정이다. 이 포스팅의 핵심 포인트는 개발을 전혀 모르는 사람이더라도 쉽게 웹사이트를 만들 수 있게 설명했다. 준비물로는 도메인 네임과 웹사이트 템플릿을 구매할 약간의 크레딧과 깃허브 계정이 필요하다. 본론먼저, 다음과 같은..

git이란 무엇일까? git의 역사부터 github란 뭔지에 대해서까지 포스팅할 예정이다. 이번 포스팅은 개발을 입문하는 사람에게 초점이 맞춰줘 있다.  본론git의 역사git의 역사를 이야기하면 리눅스의 이야기도 빼놓을 수 없다. 깃이라고 하는 VSC(버전 관리 시스템)은 리눅스와 함께 개발되었다. Linux 커널은 굉장히 규모가 큰 오픈소스 프로젝트다. 이 커널 프로젝트는 당연히 오랫동안 진행되었는데, 1991-2002년 사이에는 Patch와 단순 압축 파일로만 관리했다. 2002년에 드디어 Linux 커널은 BitKeeper라고 불리는 상용 DVCS(분산 버전 관리 시스템)를 사용하기 시작했다. 하지만 2005년에 커뮤니티가 만드는 Linux 커널과 이익을 추구하는 회사가 개발한 BitKeeper..

평소에 백준 사이트에서 PS 문제를 푸는 것을 좋아한다. 알고리즘을 공부하는 것 자체만으로도 재미있고, 코딩 테스트를 언제든 준비할 수 있게끔 녹슬지 않게 실력을 가꾸기 위해서이다. 직접 백준 문제를 풀면서 파이썬을 통해 백준 문제를 풀 때 알아두면 좋은 것들을 정리하려고 한다. 이번 포스팅에서 다루는 것은 파이썬으로 백준 문제를 풀 때에 꼭 알아두어야 맞왜틀( 맞았는데 왜 틀리지 )을 방지할 수 있을만한 내용들이다. 본론시간복잡도 계산알고리즘을 푼다라고 하면 가장 기본적인 것은 시간복잡도 계산이다. 알고리즘에는 다양한 것들이 있지만, 우리가 기본적으로 사용하는 알고리즘의 시간 복잡도를 알고 있다고 가정하자. ( 예를 들어 이진 탐색의 시간 복잡도가 O(logN)이라는 것을 알고 있다 ) 그리고 다음 문..

필자는 토이 프로젝트를 진행하는 것을 굉장히 좋아한다. 대부분의 토이 프로젝트에서 자주 구현하는 것 중 하나가 크롤러이다. 정보가 넘쳐흐르는 웹 세상에서 원하는 정보를 끌어와 가공하여 다양한 서비스를 제공할 수 있다는 점이 굉장히 흥미로웠기 때문에 많은 토이 프로젝트에서 크롤러를 구현하곤 했다. 크롤러를 만드는 데 node를 쓰기도 하고, python을 쓰기도 하고, Spring과 Kotlin 환경에서 스크래퍼를 구현해보기도 하는 등 거의 모든 프로젝트에 크롤러가 들어가는 것 같다. 이렇게 토이 프로젝트로 크롤러를 이것저것 만들다, 때는 작년 여름 시대생 앱 프로덕트에 쓰일 스크래퍼를 만들게 되었다. 단순히 스크래퍼 하나만을 만드는 것이 아니라 사용자들에게 다양한 서비스를 제공하는 애플리케이션의 유틸리티..

Write once, run anywhere - 한 번 쓰면, 어디서든 실행된다.  위 문구는 자바를 대표하는 문구이다. 백엔드 개발자라면 누구나 한 번쯤은 접하게 되는 자바. 나 또한 피해 갈 수 없었는데, 시대생팀에서 서버를 개발하는 일을 맡게 되었을 때 나를 제외한 다른 팀원들이 스프링을 사용하기를 원했기 때문에 어쩔 수 없이 스프링으로 개발하게 된 적이 있었다. 뿐만 아니라, GDSC UOS 팀에서는 node를 사용하는 나를 제외한 모든 개발자들이 스프링을 사용하기 때문에 데일리 스크럼에서 자바와 관련된 이야기들이 오고 갔다. ex) 스프링 3.x 버전대에서 스웨거가 잘 안 되는 것 같다 -> 그 버전에서는 스웨거 오류가 있어서 swagger-ui 라이브러리를 써보실래요? 등.. 예전부터 자바를..