맞았습니다!!

파댕이컵 B: 여중생 파댕이와 공부를

2023.12.18·

PS/BOJ

시간 제한 메모리 제한 1초 1024MB 문제 여중생 파댕이는 할 것이 너무 많고 공부가 어려워 정신이 없다. 오늘도 여중생 파댕이는 선생님으로부터 덧셈 문제 풀기라는 끔찍한 과제를 받았다. 파댕이는 어찌어찌 과제를 다 하는 데는 성공했지만, 과제를 채점하는 일이 매우 귀찮았다. 그래서 파댕이는 과제를 읽고 자동으로 채점해 주는 프로그램을 개발하려 한다. 파댕이를 도와주자! 이하의 문단들은 문제의 요구 조건을 자세히 기술한 것이다. 직관적인 설명을 원한다면 입력 예시와 출력 예시를 참고하라. 파댕이의 과제가 적힌 종이는 크기 3N × 8M의 행렬로 나타낼 수 있다. 종이 위에는 여러 개의 문제가 적혀 있는데, 하나의 문제가 차지하는 공간은 세로 3, 가로 8이다. 이 문제들이 세로로 N개, 가로로 M개씩..

파댕이컵 A: 유치원생 파댕이 돌보기

2023.12.18·

PS/BOJ

시간 제한 메모리 제한 1초 1024MB 문제 유치원생 파댕이는 아직 어리기 때문에 단것을 매우 좋아한다. 또한, 파댕이는 사탕을 주지 않으면 시도 때도 없이 울곤 한다. 파댕이를 사랑하는 여러분은 일정 시간 동안 파댕이를 돌봐주기로 했다. 여러분은 파댕이를 돌보는 동안 파댕이가 우는 것을 보고 싶지 않기에, 파댕이가 울지 않도록 사탕을 챙겨왔다. 하지만 파댕이를 빨리 보고 싶은 마음에 급하게 사탕을 챙기느라, 돌보는 동안 파댕이가 울지 않게 만들 수 있는 충분한 사탕의 개수인지 확인하지 못했다. 여러분이 가지고 있는 사탕으로 파댕이를 돌보는 동안 파댕이를 울지 않게 만들 수 있는지 알아보자! 여러분은 T분 동안 파댕이를 돌봐야 하며, N개의 사탕을 가지고 있다. 파댕이는 사탕의 맛에 따라 울음을 그치는..

3015: 오아시스 재결합

2023.12.12·

PS/BOJ

시간 제한 메모리 제한 1초 256MB 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람들이 서 있는 순서대로 입력이 주어진다. 출력 서로 볼 수 있는 ..

세그먼트 트리(Segment Tree)

2023.12.07·

PS/Algorithm

트리(Tree) 자료구조는 데이터간 위계가 있어 다양한 처리가 가능하다. 세그먼트 트리는 약간의 메모리를 할애해 구간의 값을 따로 관리하여 빠르게 구간 해를 얻도록 하는 트리이다. 세그먼트 트리는 데이터 전체 구간을 반복적으로 이분해 정복하여 구간에서 원하는 값을 저장해 빠르게 얻도록 한다. 원하는 값이라고 한다면 "구간의 합, 곱", "구간 내 최대, 최소 값" 등이 가능하고 분할 정복으로 구간의 해를 얻을 수 있는 문제라면 세그먼트 트리를 적용할 수 있다. 세그먼트 트리는 데이터 접근에서 정확도가 요구되기 때문에 처음에는 구현하기가 매우 까다롭다.(진짜 개고생했다.) 우선 이 글에서는 새로운 데이터를 추가하지 않는 조건에서 세그먼트 트리를 만들고 원하는 구간 해를 출력하는 쿼리를 구현해본다. 1. 트..

분할 정복으로 행렬의 곱셈하기(슈트라센 알고리즘, Strassen Algorithm)

2023.11.29·

PS/Algorithm

1. 행렬의 곱셈행렬의 곱셈은 단순히 곱셈보다 압도적으로 많은 연산을 필요로 한다. 행렬의 규모가 커질수록 그 정도는 더 심화된다. 행렬의 곱셈은 아래와 같은 규칙을 따른다.2*2 크기의 정사각행렬 두 개를 곱할 때 필요한 연산은 덧셈 4회, 곱셈 8회이다. 3*3 정사각행렬은 덧셈 18회, 곱셈 27회가 필요하다. 연산 횟수로 보았을 때 n*n크기의 정사각행렬의 곱셈은 O(n3)의 시간복잡도를 갖는다. 지수시간이 아닌게 어디겠냐만 이걸 더 줄이는 알고리즘이 여럿 존재한다. 행렬의 곱셈은 공학분야에서 폭넓게 활용되기 때문에 효율적인 연산 방법을 찾는 연구가 꾸준히 진행되고 있다. 최근에는 구글 딥마인드의 알파제로가 새로운 행렬 곱셈 알고리즘을 발견하기도 했다. 아무튼 다양한 방법 중 깡 삼차시간 연산 방..

병합 정렬(Merge sort)

2023.11.23·

PS/Algorithm

분할 정복으로 정렬을 완성해가는 알고리즘이다. 알고리즘은 분할, 병합의 두 단계를 재귀 호출하는 것으로 완성되어 꽤 단순하게 구현할 수 있다. 그 유명한 폰 노이만 박사가 만든 알고리즘이다. 1. 병합 정렬(Merge sort)의 개념 원리는 앞서 말한 분할 정복(Divide and Conquer)이다. 문제 전체를 부분으로 쪼개서 하위 문제의 해를 찾아 상위 문제의 해를 얻는 방식으로 정렬에 적용하면 전체 길이의 배열을 절반, 다시 절반, 반복하여 나눌 수 없는 상태의 크기로 만들고 정렬이 끝난 부분들을 합쳐 정렬을 점차적으로 완성해나간다. 이 일을 진행할 때 코드에서 구현해야 하는 것은 두 가지다. 먼저 "분할"하는 것이고 분할된 것을 바르게 "병합"하는 것이다. 언제 분할하며 언제 병합하는지도 중요..

10986: 나머지 합

2023.11.23·

PS/BOJ

시간 제한 메모리 제한 1초 256MB 문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이 1. 1트 누적 합 알고리즘만 써서 제출 해봤더니 시간초과가 떴다. import sys input = sys.stdin.readli..

누적 합(Prefix sum)

2023.11.22·

PS/Algorithm

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..

20920: 영단어 암기는 괴로워

2023.11.17·

PS/BOJ

시간 제한 메모리 제한 1초(추가 시간 없음) 1024MB 문제 화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자. 입력 첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외..

17103: 골드바흐 파티션

2023.11.16·

PS/BOJ

시간 제한 메모리 제한 0.5초 512MB 문제 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 입력 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 int(N / 2): break if sieve[N - p]: count += 1 print(count)

해시 함수(Hash function)

2023.11.15·

PS/Algorithm

해시 함수는 말 그대로 입력을 변환하는 함수다. 목적은 임의의 데이터를 정해진 크기의 데이터로 바꾸는 것이다. 어떤 크기의 값을 넣어도 정해진 크기로 바뀌니 데이터 관리에 유리한 면이 있다. 하지만 정보의 크기를 한정하는 함수이기 때문에 정보 손실은 불가피하고 이것 때문에 이 함수는 단방향 함수다. 해시 함수인 결과(해시 값)만을 가지고 원래 값이 무엇이었는지는 확실히 알 수 없다. 본문에서는 자료구조로서의 해시 함수를 다룬다. 1. 키(Key)와 해시(Hash) 키는 해시 함수에 입력되는 기존 값을, 해시는 그 결과 값을 말한다. 이름(3글자)을 키로 받아 각 글자의 획수로 바꿔보자. 이 방법으로 이름이 거의 대부분 3자리의 숫자로 반환된다. 이 과정에서 이름은 키, 반환된 3자리 숫자는 해시이다. 수..

15683: 감시

2023.11.12·

PS/BOJ

시간 제한 메모리 제한 1초 512MB 문제 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. (중략) 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지..

티스토리툴바