leetcode.com/problems/median-of-two-sorted-arrays/ Median of Two Sorted Arrays - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 분류 Queue 2. 풀이 두 int 배열의 평균이 아니라 중앙값을 구하는 문제이다. 두 배열을 합친 크기가 최대 2,000 밖에 안 되기 때문에 그냥 한 배열에 넣고 정렬한 뒤 중앙값 구해도 풀 수 있다. (...) 나는 두 우선순위 큐를 이용한 방법으로 해결했다. ..
알고리즘
programmers.co.kr/learn/courses/30/lessons/72412 = ${score} 정말 쉽다. DB를 쓸 수 있다면 5분도 걸리지 않을 문제이다. 하지만 코드로만 구현해야 하는 제약조건에서 "-" 으로 주어지는 dont care 조건을 어떻게 구현해야 할까를 고민해야 한다. 데이터는 List[LANGUAGE][POSITION][LEVEL][FOOD]에 넣는다. 인덱스를 순서대로 기입함에 주의한다. dont care를 찾아내기 위한 가장 쉬운 답은 dont care 데이터까지 함께 삽입해버리는 것이다. 예를 들어 [java backend junior chicken 300]이라는 데이터를 받았다고 한다면, java, backend, junior, chicken (원본) java, b..
링크 programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 1. 분류 백트래킹 2. 풀이 음식점은 손님이 최소 2번 이상 주문한 단품 메뉴 중 가장 많이 주문한 단품 메뉴를 골라서 코스 요리를 새로 만들고자 한다. 입력으로 1번 ~ n번 손님이 주문한 메뉴 목록, 코스 요리로 구성할 단품 메뉴의 개수가 주어지고, 출력은 새로 구성한 코스요리 목록을 내보내야 한다. 제한사항을 먼저 살펴보자. 최대 크기가 전부 10의 자리로, 꽤 작..
https://www.acmicpc.net/problem/1949 1. 분류 Tree Dynamic Programming 2. 풀이 Tree DP라고 불리는 유형의 문제이다. 문제의 3가지 조건에 맞춰 DP 배열을 업데이트 해주자. 풀이 전략은 다음과 같다. - DP 테이블 정의 - DFS로 노드 탐색 - 부모 노드 방문 중 자식 노드에서 얻을 수 있는 최고의 점수를 업데이트 1. DFS로 각 노드를 계속 타고 내려간다. 1) 각 노드에 방문할 때마다 일반 마을/우수 마을의 기본값을 설정한다. - dp[isGood][idx]로 정의한다. - isGood = 0이면 일반, 1이면 우수마을이다. - 일반 마을이면 값은 0, 우수 마을의 경우 해당 마을의 인구 수로 초기화한다. 2) 자식 노드를 탐색한다. -..
https://github.com/dhmin5693/Algorithms dhmin5693/Algorithms Contribute to dhmin5693/Algorithms development by creating an account on GitHub. github.com 목표는 하루에 한 문제 풀이 작성한 소스 코드를 다시 찾아보기 어려워서 개설하고 관리했더니 훨씬 보기 좋은 것 같다.
https://www.acmicpc.net/problem/7576 1. 분류 BFS 2. 풀이 모든 토마토를 익힐 때까지 며칠이나 걸릴지를 구하는 문제. 익은 토마토는 주변 상하좌우의 토마토를 익혀버린다. 좀비도 아니고...; 큐에 넣은 인접 토마토들이 다 빠져나온 순간을 하루가 지난 것으로 설정하였다. 3. 소스코드 #include #include using namespace std; int map[1000][1000]; const int dy[4] = { -1, 0, 1, 0 }; const int dx[4] = { 0, 1, 0, -1 }; int main() { int m, n, day = 0; bool isPossible = false, isFull = true; queue q; scanf("%..
1. 분류Prefix 2. 풀이 두 점 (x1, y1), (x2, y2)으로 그릴 수 있는 직사각형의 범위 내에 있는 모든 수의 합을 구하는 문제이다. 가장 간단하게 풀 수 있는 방법은 역시나 이중 반복문으로 수를 일일이 더하는 방법일 것이다. 아쉽게도 그 방법은 사용하지 못한다. 합을 구해야 하는 갯수 M개, 행과 열의 개수 N개이므로 최악의 경우를 생각해본다면 시간복잡도는 O(M * N^2) => 100,000 * 1,024 * 1,024 = 1,048,576,000 무조건 시간초과를 유발할 것이다. 조금 다르게 생각해보자. 예제 입력에서 첫 번째 출력은 (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)를 더하는 것이다. 입력을 받는 동시에 미리 더해본다면? 표의 각..
1. 소개 프로그래밍 문제에 가장 자주 출현하는 디자인 패러다임이다. 메모리를 희생하여 속도를 얻는 가장 대표적인 방식이기도 하다. 이름이 굉장히 거창하지만 사실 의미는 없고 단순히 멋있어서 지은 것이라고... 종만북(프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략)에서는 DP의 특성 상 동적 프로그래밍보다는 동적 계획법이 더 알맞은 번역이라고 소개하고 있다. 2. 풀이법 분할 정복과 접근방식이 유사하다. 주어진 문제를 더 작은 문제들로 나누고 각 조각들의 답을 도출해내기 때문이다. 단, DP에서는 단 한 번만 계산하고 그 결과를 다시 재활용하여 속도를 향상시킨다는 점에서 다르다. 가장 쉽게 생각해볼 수 있는 사례로 이항계수가 있다. BOJ 이항 계수 2 링크위키백과(파스칼의 삼각형) 위키백과의 공식..
