전체 글

핑계지만 한동안 프로젝트를 진행한다고 알고리즘 문제를 풀지 못하였다. 아무래도 처음 진행해보는 프로젝트이다 보니 하루에 어느 정도 해야지라는 양을 가늠하지 못하고, 시간이 있을 때마다 프로젝트에 몰두한다고 나의 다른 스케줄을 잘 진행하지 못한 것 같다. 앞으로 프로젝트를 할 때는 프로젝트도 중요하지만 시간 배분을 조금 더 유동적으로 해봐야겠다. 문제 얘기를 해보자면 이번에 푼 문제는 Watering the Fields이다. 문제가 영어버전 밖에 없지만, 다행히 문제 길이도 길지 않고, 문제에서 하는 얘기도 딱 보이기 때문에 영어가 약한 나에게도 해석상에 큰 문제는 없었다. 문제 줄거리는 농부가 물을 받아놓기 위해 파이프를 연결해놓아야 한다는 내용이지만, 결국에는 문제에서 모든 파이프의 좌표가 주어지고, ..

TMDB API를 활용한 데이터 기반 영화 추천 사이트 개발 싸피 1학기 과정을 마치면서 1학기 동안 함께 공부했던 팀원들과 팀장 및 Client Server 담당자로 영화 추천 사이트를 개발하게 되었다. 프로젝트를 시작하면서 팀원들과 의견을 취합하는 과정에서 우리가 가장 먼저 했던 일은 우리가 할 수 있는 것과 현실적(경제적)으로 불가능한 일을 구분해 나가는 것이었다. 이 과정을 거치면서 우리의 주 목적인 영화 추천을 어떻게 효과적으로 할 수 있을지 고민해보았다. 그리고, UX를 향상하는 기능을 집중 목표로, 영화 추천 / 게시판을 개발하기 위해 노력했다. 현재 인기있는 OTT사이트들 (OTT사이트는 우리 프로젝트와는 달리 스트리밍 기능까지 있다는 차이점이 있음)을 참고했을 때, 우리 팀이 집중 한 공..

오랜만에 백준을 풀었고, 오랜만에 시간 초과 늪에 빠졌다. 최대한 시간을 줄여 파이썬까지 통과해보고 싶었지만 아직 내실력에서는 Pypy통과가 최선이었다. 문제를 간략히 설명하자면, 존이 N개의 동영상 중 N-1개의 동영상 쌍을 만들어서 유사도를 구해놓았다. 동영상 쌍을 만들 때 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 만들었을 때, Q개의 질문(v번의 동영상과 유사도가 k이상인 동영상의 개수)의 답을 구하는 문제이다. 문제에서 가장 큰 힌트부분은 한 동영상에서 한 동영상으로 가는 경로가 반드시 하나인 점. 즉, 방향이 존재하지 않고 사이클이 없는 그래프인 트리구조로 만들 수 있다는 점이다. 나는 위 점에서 힌트를 얻어 딕셔너리를 활용하여 트리를 만들었고, 이를 이용한 BFS탐색..

사실 이 문제는 어렵지는 않지만, 제한사항과 문제 카테고리가 없었으면 좀 헤매었을 것 같다. 왜냐하면 완전 탐색 문제만 보면 DP문제가 아닌가? 하는 겁이 나기 때문이다. 하지만, 위에 말한것 처럼 제한사항에서 주어지는 숫자 개수가 20개 이하인걸 확인한다면, 쉽게 풀 수 있을 것이다. 이문제는 숫자들의 배열과 타겟넘버가 주어질 때, 숫자들의 배열의 합과 차로 타깃 넘버를 만들 수 있는 방법의 개수를 묻는 문제이다. 더하거나 뺄 수 있다는 부분에서 부분집합(itertools)를 활용하기에는 조금 어려움이 있을 것 같아 나는 완전 검색(DFS) 방식으로 문제를 풀었다. 원하는 타겟넘버가 되는 조건을 종료 조건으로 그전까지는 배열을 진행하면서 합과 차를 각각 구해보는 전형적인 완전 탐색 풀이법을 사용해 보았..