매일을 설렘으로

문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicp..

문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} ..

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다..

백준 2470번 두 용액 문제를 접근하는데 이진탐색으로 못 풀고 투 포인터라는 방법으로 풀었다. 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 나의 풀이 선형탐색으로는 O(N^2)으로 시간초과가 될 것이니, 이분탐색이나 투포인터라는 알리고즘?으로 풀어야한다. 절대값이 0에 가까운 두 값의 조합을 찾기 위해서 두 조합의 합이 음수이면 왼쪽 원소의 절대값이 너무 크다를 의미하고, 양수라면, 오른쪽 원소의 절대값이 너무 크기 때문에 그에 맞게 두 원소의 idx값을 조절하면 된다...

백준 1920 수찾기를 선형탐색과 이진탐색으로 풀면서 들었던 의문이다. Sort한 후, 이진탐색(binary search)를 할 경우 선형탐색(Linear search) 대비 느려질거라 생각했지만? 실제론 더 빠른 결과를 얻었다. 왜 그럴까? 선형탐색 (Linear search)은 배열의 맨 앞 원소부터 맨 끝 원소까지 탐색하기에 시간 복잡도는 O(N)이다. 이 때, 최상/평균/최악의 case가 있는데, 알고리즘 성능을 얘기하기 위해선 최악의 case로 계산한다. 참고 블로그: https://hahasof.tistory.com/5 이진탐색은 정렬되어있는 배열 중간값과 비교해서 탐색해나가서 시간 복잡도는 O(logN)이 된다. 처음에 입력된 갯수를 N 이라하면, 첫 시행 후에는 반이 버려져서 , 두 번째 ..

백준 2468번 문제를 풀다보니 2D 리스트를 아래와 같이 선언을 해주고 특정 위치에만 값을 주었는데 알수없는 에러가 발생했다. 알고보니 아래와 같이 list를 선언해주면 list의 얇은 복사가 되기에 원소값을 변경해주면 다른 행의 리스트도 동일하게 변경된다. 리스트 자료구조에 대해서 알아봐야겠다. 1. 파이썬은 리스트를 저장할 때 값 자체가 아니라, 값이 위치한 메모리 주소(reference)를 저장합니다. : a = [0, 1, 2] 라는 리스트를 선언하면 a에는 리스트의 주소를 저장한다. 그리고 리스트 내 a[0], a[1]에도 그 숫자객체 가 저장된 주소를 저장한다. 1. 얇은 복사 (shallow copy) list_b = list_a list_b = list_a[:] 둘다 모두 얇은 복사 개념..