live the life you love

우선순위 큐 사용자 정의 비교함수 작성 우선순위 큐에 넣어서 비교해야할 요소가 3개 이상 있을 경우, 연산자 오버라이딩을 해야 한다. 이 때, 중요한 것은 단순히 리턴타입이 단순히 bool 인 함수를 만드는 것이 아닌 연산자 오버라이딩이다. struct INFO{ int y; int x; int z; }; struct cmp{ bool operator()(INFO a, INFO b){ if(a.y == b.y){ if(a.x == b.x){ return a.z b.x; // x는 오름차순 } return a.y < b.y; // y는 내림차순 } }; int main() { priority_queuepq; pq.push({1,2,3}); pq.p..

쿠키 : 유저 아이디 자동완성 쇼핑몰에서 로그인 안한 채로 장바구니담기 사용자의 편의를 위함 조작되어도 큰 문제가 없는 정보 세션 : 서버(관리자) 사용자의 민감한 정보, 조작되면 안되는 정보 세션에 담긴 정보가 많으면 서버 부하가 걸릴 수 있음 서버에서 만든다. 쿠키안에 세션 ID를 넣어서 클라이언트에게 Response 한다. 결국 세션도 쿠키를 사용하는 것이다. timeout을 업데이트 세션을 RAM DB에 저장해둔다. 사용자가 다시 로그인을 하면 쿠키와 세션 정보를 같이 서버에 보낸다. 내부 DB로 세션정보를 확인 트래픽이 많아지면 로드밸런서가 사용된다. 3개의 웹서버가 동작한다고 가정했을 때, 1번 서버에서 세션 ID를 발급받았는데, 이 세션 ID를 가진 사용자를 로드밸런서가 2번 서버로 보낸다면..

www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전의 문제 두 용액(paris-in-the-rain.tistory.com/59)에서는 절댓값 대소 비교로 문제를 풀었다. 두 문제의 차이는 정렬 여부인데, 두 용액 문제는 정렬이 안되어 있고, 이 문제는 정렬이 되어있다. 이 문제는 투포인터를 활용했다. 포인터의 시작점을 맨 처음 인덱스(p1), 맨 끝 인덱스(p2)로 두었다. 해당 인덱스의 숫자를 더하여 값을 확인한다. 두 숫자를 더해서 0에 가까운 값..

programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 해시 자료구조를 사용하는 문제였다. 해시의 특성상 key값을 기준으로 오름차순 정렬이 되는게 기본인데, 문제에서 요구하는 대로 정렬을 하기 위해서는 정렬 함수를 따로 만들어줘야 한다. 문제에서 제시하는 노래를 수록하는 기준은 다음과 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 ..

www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현사항만 잘 지키면 되는 전형적인 시뮬레이션 문제였다. 손님을 태우러 택시가 가는 것과, 손님을 태우고 목적지로 가는 것은 같은 방식으로 구현을 할 수 있으므로 flag 변수를 통해 1개의 함수로 처리했다. 문제해결 현재 손님의 위치, 목적지를 입력받고 각각 다른 배열에 저장한다. 비교함수를 만들어 문제의 조건을 처리한다. 가장 가까운 승객 / 행 번호 작은 승객 / 열..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 조건을 잘 읽고 그대로 구현하면 되는 문제이다. 구현 자체는 쉬운데, 문제를 제대로 안읽어서 놓친 조건과 문제에서 정보를 안준 것이 하나 있어서 좀 오래 걸렸다. 문제 조건을 요약하면 아래와 같다. 아기 상어의 이동 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음 나머지 칸은 모두 지나갈 수 있다. 물고기 먹기 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 처음에는 산성, 알칼리 용액을 나눠서 계산하다 보니 계속 틀려서 블로그를 참고하여 풀었다. 투 포인터를 활용해서 풀려고 했는데, 풀고나니 이 문제는 절댓값을 활용해서 푸는 것이 더 효율적이라고 생각한다. 기존 접근 방식(오답) 산성 용액과 알칼리 용액을 나눠서 저장 후 정렬한다 알칼리 용액만 있는 경우, 산성 용액만 있는 경우 각 배열의 첫번째, 두번째 원소의 값이 최솟값이므로..

www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다. 8번의 시도 끝에 풀었다. 문제 해결 문제를 읽어보면 다음과 같은 조건이 있다. 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다. 2 Key Value : 해당 Key로 검색된 데이터를 Va..

www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보� www.acmicpc.net 그렇게 어려운 문제는 아니었는데 복잡하게 생각을 해서 그런가 헤매다가 다른 블로그의 글을 보고 푼 문제다. 문제는 단순하다. 각 크레인 마다 1개의 박스를 옮길 수 있고 무게 제한이 있다. 한 번 옮길 때 마다 크레인이 옮길 수 있는 최대 무게의 상자를 옮겨주면 된다. 문제 해결 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인을 비교한다. 박스 값이 크레인 보다 크면 절대로 옮길 수..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 숨바꼭질 3의 경우는 1,2번 문제와 달리 순간이동을 하는데 걸리는 시간이 0초다. 이것을 잘 해결 하는 것이 매우 중요하다. 이 문제는 우선순위 큐(priority queue)를 활용하는 방법과 기본적인 큐를 활용해서 푸는 방법이 있다. 순간이동을 하는데 걸리는 시간이 0초이므로, 0초에 순간이동 하는 것을 큐에 먼저 삽입을 해줘야 한다. 우선순위 큐는 최대힙으로 구성되..