본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 10798번 : 세로읽기 10798번: 세로읽기 (acmicpc.net) 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 풀이 5줄에 걸쳐 문자열을 받고 그 문자열을 세로로 읽은 문자열을 출력하는 문제다. 문제의 포인트는 각 문자열의 길이가 다르기 때문에 빈 공간을 처리하는 방식이다. 직관적으로 빈공간에 모두 별표를 넣어버리고 꽉 찬 사각형을 세로로 읽은 후 나중에 별표를 모두 삭제하는 방식으로 구현하였다. arr = [] for _ in range(5): arr.append(input()) check = [] for i in .. 더보기
알고리즘 - Python / 백준 - 14246번 : K보다 큰 구간 14246번: K보다 큰 구간 (acmicpc.net) 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 풀이 일정 길이만큼의 수열이 주어지고 , 이 수열의 구간합이 k 이상인 구간이 얼마나 있는지 구하는 문제다. 전형적인 구간합 + 투 포인터 문제라고 생각하고 문제를 풀었다. 하지만 계속해서 백준 상에서 valueerror가 나왔고 , 이 문제 때문에 블로그에 글로 남기기로 했다. 문제 풀이 자체는 심플하게 구간합을 구해주고 , 투 포인터로 구간합에 접근하는 방식이다. 만약 이번 포인터에서 합이 k보다 크게 나왔다면 뒤는 볼 필요도 없다. 왜냐하면 빼는 경우가 없기.. 더보기
알고리즘 - Python / 백준 - 17298번 : 오큰수 17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 수열이 주어지고 , 그 숫자보다 오른쪽에서 큰 숫자들 중 가장 먼저 나오는 수가 오큰수 이다. 주어진 수열에 대하여 오큰수(An)을 찾으면 되는 문제다. 스택을 통해서 구현할 수 있고 , 다음과 같은 방식으로 해결하면 된다. 1. 스택의 TOP과 비교해 다음 수가 크다면 , POP 하고 그다음수를 오큰수로 정함 2. 스택의 TOP과 비교해 다음 수가 작다면 , 스택 위에 추가함 1번의 경우 스택이 빌 때까지 진행하고 , 2.. 더보기
알고리즘 - Python / 백준 - 1406번 : 에디터 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 리눅스 vi 에디터 같은 형태의 에디터를 직접 구현하는 문제다. 문제만 읽었을 때는 어려운 부분이 없어 보이지만 , 시간제한을 0.3초 밖에 주지 않는 문제다. 문자열의 원하는 위치에 삽입 혹은 삭제가 가장 시간을 많이 잡아먹는 작업일 테고 이를 효과적으로 줄이는 것이 중요할 것이다. 커서의 위치와 문자열 시작 위치를 저장해놓고 , 커서를 좌우로 옮길 때 , deque를 rotate 해주는 방식으로 구현하였다. 만.. 더보기
알고리즘 - Python / 백준 - 2468번 : 안전 영역 2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 n * n 격자에 지역의 높이가 입력되고 , 해당 지역에 비가 내렸을 때 높이가 비의 양보다 낮다면 물에 잠긴다. 이때 , 만들어질 수 있는 최대 안전지역의 개수를 찾는 문제다. 단순하게 그래프 탐색 문제로 풀 수 있다. dfs를 이용해서 구현하였고 , 가장 높은 지역보다 비가 더 많이 내린다면 측정할 필요도 없이 모두 물에 잠기기에 최대 높이를 구해주고 0 ~ max 값까지 for문을 통해 해당 비의 양에 따라 d.. 더보기
알고리즘 - Python / 백준 - 14921번 : 용액 합성하기 14921번: 용액 합성하기 (acmicpc.net) 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 풀이 오름차순으로 나열된 숫자들 중 2개를 더해서 가장 0에 가깝게 만드는 문제다. 문제를 딱 봤는데 어디서 본문제 같다. 알고리즘 - Python / 백준 - 2467번 : 용액 (tistory.com) 알고리즘 - Python / 백준 - 2467번 : 용액 2467번: 용액 (acmicpc.net) 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 10.. 더보기
알고리즘 - Python / 백준 - 1461번 : 도서관 1461번: 도서관 (acmicpc.net) 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 풀이 수직선 상의 좌표에 책을 가져다 두어야 하고 , 한 번에 m개의 책을 들 수 있다. 이때 가장 적게 움직이면서 책을 가져다 두려면 얼마나 움직여야 하는지 구하는 문제다. 딱 봐도 그리디 스타일의 문제라고 생각하고 바로 예제를 뜯어보았다. 예제 1의 경우 [-39, -37, -29, -28, -6, 2, 11]이다. 마지막에는 책을 꽂고 원점으로 돌아올 필요가 없으므로 무조건 마지막에 좌우에서 가장 먼 부분의 책을 꽂는.. 더보기
알고리즘 - Python / 백준 - 13926번 : gcd(n, k) = 1 13926번: gcd(n, k) = 1 (acmicpc.net) 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 자연수 n이 주어졌을 때 , n보다 작고 gcd(n,k) = 1을 만족하는 자연수 k의 개수를 구하는 문제다. gcd(a,b)는 a와 b의 최대공약수를 의미하고 이 최대 공약수가 1이라는 뜻은 두 수가 서로소라는 뜻이다. 그러면 어떠한 수 n과 1 ~ n 까지의 k가 서로소인지 아닌지 판별해야 한다. 이때 , 다음과 같은 과정을 통해 알아낼 수 있다. 1. 어떠한 수 n을 소인수 분해 한다. 2. n을 소인수 분해한 수들이 p1,p2,p3.... 더보기
반응형

티스토리툴바