목록전체 글 (43)
tlov
참고: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 동전 n가지를 무한히 쓸 수 있다? == dp를 왼쪽부터 누적동전 n가지를 1개만 쓸 수 있다? == dp를 오른쪽부터 누적. 0 1 2 3 4 5 6 7 81원으로 얘네들을 만든다.1 2 3 4 5 6 7 8개가 필요.2원으로 만든다.테이블로 표현하자. dp0123456781원0123456782원0112... 빨간 글씨부터 갱신이 되는 부분이다. 즉, 점화식이 min(dp[i], dp[i-2] + 1);이다. 번외) n가지를 1개만 쓸 수 있다면?for (int i = 0; i = tmp; j--) { dp[j] = Math.min(dp[j], dp[j - tmp] + 1); }} 1, 2, 5로 5원을 만든다고 하면 테이블이 ..
문제: boj.kr/2240날짜: 09/20 (금)성공여부: X [02:20:01] 자두 나무에서 떨어지는 자두를 최대 W만큼 움직여 최대한 많은 자두를 먹는 문제이다. 완전 탐색자두 나무는 각각 2개의 위치에 있고, 시간 별로 둘 중 하나의 나무에서 자두가 떨어진다. 가장 간단하게 생각해볼 수 있는 방법은 역시 완전 탐색이다. 여기서 주어지는 변수를 생각해보면 시간, 이동 횟수, 위치가 있다. 자두가 처음에 1 위치에서 시작하니까 해당 위치를 기준으로 이동 횟수를 소모하지 않고 제자리에 있느냐 혹은 이동 횟수를 소모해서 1 위치로 이동하느냐 두 가지 경우의 수가 있다. 그럼 다음과 같이 두 번의 호출이 필요함을 예상할 수 있다.go(t + 1, w, 0);go(t + 1, w-1, 1); 하나의 위치에..
문제: boj.kr/2098날짜: 09/16 (월)성공여부: X 외판원 순회(TSP)는 n개의 도시가 있고 각 도시를 이어주는 길과 각 길에 대한 비용이 있을 때 외판원이 모든 도시를 돌아 다시 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. DP의 대표적인 문제임은 알고있었으나, 결국 어떻게 푸는지 몰라 실패했다. 완전 탐색가장 먼저 생각해볼 수 있는 알고리즘이다. N이 16이다. 모든 도시가 서로 이어져있다고 가정하고 한 도시 중 하나를 골라 출발하여 그 도시를 제외하고 나머지 도시를 고르고 또 나머지 도시를 고르고 ... 이를 반복하여 총 16개 도시를 전부 돌고 다시 처음 도시로 돌아오는 경우의 수는16C1 * 15C1 * 14C1 * ... * 1C1 * 1C1(처음 도시로 돌아감) = ..
최근에 약 5주(8/16 ~ 9/13) 동안 jscode 모의면접으로 학습하는 운영체제 스터디에 참여했다. 취준을 본격적으로 시작하기에 앞서 3학년때 배웠던 운영체제를 제대로 한번 학습해 놓고 취준을 시작하면 추후에 면접을 준비할 때 좀 수월할 거 같아서 '명품 운영체제' 책을 구입했었는데, 막상 혼자 공부하려고 하니 당장 운영체제에 대한 중요도가 낮다고 생각되어 생각보다 진도가 안 나갔다. 그런 와중에 친구한테서 이런 스터디가 있다는 얘기를 들었고 면접도 한번 경험해보고 운영체제도 공부할 좋은 기회라 생각해서 신청하게 되었다. 활동 내용스터디는 총 5주동안 매주마다 모의 면접 예상 질문 리스트를 확인하고 금요일까지 해당 내용 범위를 공부한 뒤 금요일 오후 8시에 2시간씩 팀원들과 모의 면접을 진행하였..
JWT 토큰을 이용해 로그인 기능을 구현하기 앞서 구글링을 통하여 해당 방법을 이해하기 위해 글을 써봅니다. 인증과 인가인증(Authentication)사용자가 누구인지 확인하는 과정. (ex. 로그인) 인가(Authorization)사용자에 대해 자원 접근 권한같은 것을 허락하는 것. (ex. 카페 등급별 게시물) HTTPHTTP는 비연결성 및 무상태성이라는 특징을 가지는 프로토콜이다. 즉, 요청을 처리하고 난 후에는 요청을 한 클라이언트의 어떠한 정보도 남기지 않는다. 이러한 특징 덕분에 서버는 많은 클라이언트와의 연결을 유지하지 않아 서버의 자원도 아끼고 부담도 적다. 그러나, 연결을 유지하지 않기 때문에 방금 전 요청한 클라이언트가 다시 요청을 보내도 이전에 요청한 클라이언트인지 구분하지 못한다..
문제: boj.kr/2565날짜: 09/11 (수)성공여부: X [00:52:17] 전깃줄이 교차하지 않도록 최소의 전깃줄을 제거하고 그 개수를 출력하는 문제이다. 가장 먼저 생각해볼 수 있는 알고리즘은 완전탐색이다. 모든 전깃줄을 1개, 2개, 3개, ..., n개까지 제거하면서 최소의 개수를 구하는 것이다. 전깃줄의 개수가 최대 100개이니까 이 방법은 전깃줄을 고르는데에만 100C1 + 100C2 + 100C3 + ... + 100C100만큼의 시간이 걸린다. 가장 큰 경우의 수인 100C50가 약 1 * 10^29이므로 이 방법은 안된다. 그럼 교차하는 수가 많은 전깃줄 위주로 없애는 방법을 생각할 수 있다. 위의 예제를 가장 많은 전깃줄을 교차하는 순으로 정렬하면, 1 83 94 1... 이러..
문제: boj.kr/1561 날짜: 9월 8일 (일) 성공여부: X [01:30:34] 이분탐색 문제이다. N이 20억이고 M이 1만이기 때문에 0분에 아이들을 M개의 놀이기구에 태우고 1분마다 한 명씩 태울 수 있는 곳에 태워서 모든 경우의 수를 찾는건 시간초과이다. 그럼 이를 효율적으로 찾는 방법을 생각해야 하는데, 이때 시간을 이용해 이분탐색을 하면 모두를 태우는 최적의 시간을 약 31번만에 더 빠르게 찾을 수 있다는 것까지는 생각했다. 하지만, 이 매개변수를 찾는 방법과 찾아서 활용하는 방법을 생각하지 못해서 해설을 봤다. 22 5 1 2 3 4 5 22명을 태우는 상황이라면 22명이 모두 타는 최적의 시간을 찾는다. 이 시간을 찾는 방법은 0분에 M(5)명을 일단 태우고 0~30*n까지 이분탐색..
문제: boj.kr/2156날짜: 08/30 (금)성공여부: X n = 1 or 2일 때는 무조건 1을 먹고 1, 2를 먹는게 최대값이다. 그럼 진짜 로직의 시작은 n = 3일 때부터이다. n이 3일 때부터 보면 3가지의 경우의 수로 나뉜다. n을 먹지않고 이전(n-1)까지 먹은 것을 선택하거나, n-2까지의 먹은 것을 선택하고 n을 먹거나, n-3까지의 먹은 것을 선택하고 n-1, n의 와인을 먹는 것이다. 이를 식으로 나타내면 Math.max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n]) 문제가 계단 오르기 문제와 유사해서 dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n] 식으로만 생각했는데, 꼭..