정환주의 IT Devlog

최솟값 L, 최대값 R이 주어지고, 그 뒤로 들어오는 정수들에 대해서 향후 더 숫자를 더 입력 받았을 때, [L, R] 사이에 들어갈 가능성이 있는지 확인하는 문제 예를 들어 L = 331, R = 365 라고 했을 때, 새로 들어온 정수 Q = 3이라고 하면 숫자의 추가 입력으로 333 등의 수로 변할 수 있고, 이는 L, R 사이에 존재하는 값이니 참이다. (O 출력) 반대로 Q = 2인 경우, 어떠한 추가적인 입력이 들어와도 331 ~ 365 사이의 값으로 변화할 수 없다. 문제 자체의 난이도가 높기 보다는, 문제의 경우를 생각하는데 오랜 시간이 걸렸다. 1. L, R의 자리수가 같은 경우 예제 input으로도 주어져 빠르게 구할 수 있었다. 주어진 수 q와 L, R의 자리수를 맞춰서 비교해서 그 ..

https://www.acmicpc.net/problem/24729 24729번: 심각한 계단 중독입니다 병철이는 다이어트를 위해 매일 계단을 오른다. 너무 많은 계단을 오르다 보니, 주변의 모든 사물이 계단형이 아니면 불편함을 느끼게 되었다! 그러다 보니 알고리즘 문제를 풀 때도 이런 문제 www.acmicpc.net - 계단식 수열에 관한 문제 - 문제에서 제시하는 조건을 만족하기 위해서는 1. 가장 낮은 계단과 가장 높은 계단 모두 이동 가능해야한다. (min ~ max 사이의 수가 1개씩은 존재해야함) 2. 수열의 시작과 끝은 절댓값 1 차이를 만족해야 한다. => start -> min -> max -> end 또는 start -> max -> min -> end 여기서 end = start +..

https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제 농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 대표적인 DFS문제인 암호 만들기를 오랜만에 다시 풀어봤다. 정석적인 암호 만들기 문제로 현재 원소를 넣고 다음 원소로 향하는 것, 넣지 않고 다음 원소로 향하는 것 2가지 선택지를 가지고 DFS를 진행하면 문제를 해결할 수 있다. 주석으로 자세하게 설명하는 습관을 만들어보려고 노력중.. PS. cout

https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력 첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263..

https://www.acmicpc.net/problem/11997 11997번: Load Balancing (Silver) Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par www.acmicpc.net 일단 문제 설명이 영문으로 되어있어서 다들 많이 풀지도 않고, 인기 없는 문제. 신촌 알고리즘 캠프..

https://www.acmicpc.net/problem/2370 2370번: 시장 선거 포스터 첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l

https://www.acmicpc.net/problem/8903 8903번: 장비 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다 www.acmicpc.net 신촌 알고리즘 중급반 연습문제.. 고민을 거듭하다가 결국 모르겠어서 구글에 검색해서 다른 사람의 풀이를 보고 접근했다. 문제가 너무 길어서 간단히 요약하면, 5개 부문에서 각각 별개의 능력치를 모두 지닌 장비들이 입력으로 주어지고, 입력으로 주어진 K의 개수만큼 착용할 수 있다. 또, 장비를 여러 개 착용하면 장비들의 능력치가 합연산으로 적용되는 게 아니라, 각 능력치..

https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net N이 최대 100,000 => 0. O(NlogN)까지는 줄여야? WC를 통과하지 않을까 무엇을 기준으로 수열을 나누는 것의 기준을 잡을수 있을까? 1. 모든 index 검사 2. 이전까지의 합 (4개 수열중에서 맨 앞부분의 합으로 나머지 결정) 1번 케이스의 경우, O(n^3) 2번 케이스의 경우, (모든 수열의 합) / 4 = 4개로 나눠진 수열의 합 을 이용하..

https://www.acmicpc.net/problem/5375 5375번: 공책 구매 첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어지며, 아래와 같은 형식으로 이루어져 있다. 첫째 줄에 사려고 하는 공책의 개수 N과 쇼핑몰의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100, www.acmicpc.net 민혁이는 공책을 N개 사려고 한다. 민혁이는 온라인 쇼핑몰 M개에서 파는 공책의 가격을 모두 조사해놓았다. i번째 쇼핑몰에서 파는 공책의 가격은 하나당 pi원이고, 총 si개가 준비되어 있다. 또, 배송비는 oi원이다. 민혁이는 si개를 넘게 주문할 수 없으며, 몇 개를 주문하더라도 배송비는 1번만 내면 된다. 공책 N개를 사는 비용의 최솟값을 구하는 프로그램을 ..