목록2024/09 (11)
tlov
네이버 쇼핑이나 지메일을 들어가 보면 이러한 페이지 목록들을 확인할 수 있다. 이러한 기능을 구현하는 기법을 페이징이라고 한다. 정확하게 말하면 전체 데이터에서 사용자가 요청한 일부 데이터를 원하는 정렬 방식으로 보여주는 것이다. 페이징이 없으면 우리는 대용량의 데이터를 모두 받아서 하나의 웹 페이지에 다 표현해야 한다. 네이버 쇼핑에서 모니터를 검색하면 약 500만 개의 모니터 구매처가 나오는데 이를 하나의 웹 페이지 모두 불러온다면 웹 페이지를 불러오는 시간도 늘어날뿐더러 그만큼 네트워크 트래픽도 증가한다. 또한, 많은 양의 모니터를 보여주다 보니 스크롤 길이도 상당할 것이다. 그렇기에 우리는 페이징 기법으로 웹 페이지에 전체 데이터 중 일부만을 가져와 사용자에게 보여주는 것이다. 기본적으로 페이징 ..
문제를 잘 읽으면서 봄, 여름, 가을, 겨울을 하나씩 구현해보면 구현 자체는 쉽다. 이 문제에서 가장 어려운 점은 0.3초라는 시간제한을 뚫기위해 어떻게든 시간을 줄여야 한다는 점이다. 그래서 다음에 이러한 구현 문제를 풀 때 도움도 될겸 문제를 풀면서 찾은 시간을 줄이는 방법들을 정리해보는 것이다. 처음에 코드는 이렇게 구성했다.for (int year = 0; year () { @Override public int compare(tree o1, tree o2) { return o1.old - o2.old; } }); // spring ArrayDeque stk = new ArrayDeque(); for (tree t..
개인적인 공부를 위해 쓴글이므로 이해가 안될 수도 있습니다. 처음에 문제를 보고 DP 배열을 3차원으로 정의했다. DP[c][n][m] 이렇게 정의하면, c가 0일 때 경우의 수를 먼저 구해놓고, c가 1일 경우 DFS로 계속 탐색하다가 오락실을 만나면 다음 호출부터는 c를 0으로 만들어 [0][y][x]를 탐색하는데, 만약 dp[0][y][x]가 이미 갔던 곳이면 해당 값을 리턴하고 아니면 지속적으로 탐색하도록 하는 방법을 생각했다. 지금까지는 논리적으로 문제가 없어보인다. 하지만, c가 2가 되면은 반례가 보인다. 문제에서 주어지는 예제로 한번 생각해보자.3 3 22 23 2 그럼 c가 1일 때 해당하는 경우의 수는 3개이다.(1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (..
문제: boj.kr/2293 날짜: 09/22 (일)성공여부: X 1, 2, 5원 동전을 갖고 10원을 만든다고 하면 1원만 써서 만드는 경우의 수, 1원과 2원을 써서 만드는 경우의 수, 1원 2원 5원을 모두 사용해서 만드는 경우의 수로 나눌 수 있다. 1원을 먼저 써서 만드는 경우의 수를 구해놓고 2원을 써서 만드는 경우의 수를 더하면 1원과 2원으로 10원을 만드는 경우의 수를 찾을 수 있지 않을까? 그럼 중복은 어떻게 제거하냐? 1원으로만 2원부터 10원까지 만든 경우의 수가 있는 상황에서 2원을 무조건 투입한다고 생각해보자. 그럼, 2원으로 2원을 만들기 위해 2원 하나만 사용할 수 있다. 1+1, 2 2가지가 있는 경우이므로 원래 1+1 경우의 수에 2로 만든 경우의 수 = 2가 된다. 3원..
참고: 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시간씩 팀원들과 모의 면접을 진행하였..