코딩스토리

https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 요약 - 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. - 모든 직원은 민식이의 직접 또는 간접적인 부하이다. (루트 = 민식) - 1분에 한 사람씩에게만 뉴스를 전파할 수 있음 - 모든 직원이 뉴스를 접하게 되는 최소 시간을 구하라 해결 처음에는 자식 노드가 많은 직원부터 소식을 전파하면 되지 않을까 생각해봤는데 조금만 더 고민해보면 당연히 그렇지 않다는 것을..

https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 해당 문제는 2021 KAKAO BLIND RECRUITMENT 1차 코딩 테스트에 출제된 문제입니다. 문제를 다 읽었을 때 들었던 느낌은 "카카오스럽다" 였습니다. 지금까지 카카오 코테 기출을 보면 문자열 문제가 1~3번에 무조건 출제되는 경향이 있는데 이 문제 역시 문자열 관련 문제였습니다. 문자열의 최대 길이가 10이기 때문에 각 문자열에서 나올 수 있는 모..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 Min, Max Segment Tree를 사용한 문제이다. Min, Max Segment Tree란 각 범위의 최소값과 최대값을 가지고 있는 세그먼트 트리를 말한다. 두 개의 세그먼트 트리를 만들 수도 있지만 코드가 길어질 것 같아서 pair를 사용해 하나의 트리로 만들었다. 구현은 일반적인 세그트리와 비슷하다. 세그트리 자체를 이해했다면 이 코드 역시 ..

배낭 알고리즘 배낭 알고리즘은 크게 2가지로 나뉜다. 1) 분할 가능 배낭 문제 (Fractional Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼개서 담을 수 있을 때 2) 0 - 1 배낭 문제 (0 - 1 Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼갤 수 없을 때 1번 경우는 보통 그리디 알고리즘으로 해결한다. 뭐.. 풀어보진 않았지만 가치가 높은 물건을 최대한 많이 쪼개서 넣으면 되겠죠? 문제는 2번 경우이다. 사실 0 - 1 배낭 문제는 NP - Complete 문제에 속한다. 알린이라도 NP-Complete는 한 번쯤은 들어봤을 것이다. 내 기억에 NP-Complete 문제 중 하나라도 다항 시간 안에 해결할 수 있다면 모든 NP 문제를 다항 시간에 해결..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 카드게임의 규칙은 아래와 같다 1. N개의 서로 다른 빨간색 카드 중 M개를 고른다 2. N개의 서로 다른 파란색 카드 중 빨간색 카드의 번호와 같은 카드 M개를 고른다 3. 철수는 빨간색 카드, 민수는 파란색 카드를 가짐 4. 둘은 각각 카드를 한 장씩 내고 번호가 큰 사람이 이김 이 동작을 k번 실행하며 더 많이 이긴 사람이 승리 + ..