Let's Begin Programming

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 앞선 문제들과 유사한 문제다보니 비교적 쉽게 해결했다. 연속해서 붙어있는 수열의 합이 가장 큰 것을 구하는 문제이다. 일단 연속이라고 했으니 앞에서부터 차례대로 숫자를 살펴본다. 만약에 다이나믹 프로그래밍, 메모를 이용하지 않는다면 모든 경우의 수를 계산해서 최댓값을 구할 것이다. 효율을 위해 메모를 이용한다. 메모에 적는 내용은 현재 보고 있는 숫자와 이전 결과에 현재 숫자를 더했을 때 둘 중에 더 큰 값이다. 예를 들..

개발 공부 (알고리즘) 2021. 4. 16. 21:20

www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 숫자를 입력 받아 4가지의 결과를 출력해야 하는 문제였다. 정렬도 중요하지만 출력을 할 때 값을 어떻게 포맷할지도 중요한 문제였다. 1. 산술평균 산술평균은 리스트의 모든 값을 더한 후 갯수로 나눈 값이다. (a + b + c + ... ) / n 으로 나타낼 수 있다. 단순하게 입력 받은 수들을 모두 더하고 나눠주면 되지만, 출력 조건이 소수점 이하 첫째 자리에서 반올림한 값이었다. 파이썬에는 round()라는 반올림 함수가 기본 내장 함수로 ..

개발 공부 (알고리즘) 2021. 2. 2. 01:43

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이전의 수를 정렬하는 두 문제와 같이 수들을 오름차순으로 정렬하는 문제이다. 이 문제에서는 입력이 최대 10,000,000까지 주어질 수 있으나 입력할 수 있는 수의 유효 범위는 10,000까지 밖에 안된다. 이 입력이 의미하는 것은 중복되는 수는 많을 수 있지만 작은 범위안에서 주어진다는 것이다. 이러한 특징을 이용해 효율적으로 빠르게 정렬할 수 있는 정렬 알고리즘은 계수 정렬이다. 계수 정렬은 한정된 범위안에서 주어지는 정수..

개발 공부 (알고리즘) 2021. 2. 2. 01:14

www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이전 문제와 크게 다르지 않은 문제이다. 차이점은 입력의 범위이다. 최대 1,000,000개의 숫자가 주어질 수 있고, 절댓값이 1,000,000보다 작은 수 이므로 음수도 포함된다. 아마 문제의 의도는 O(nlogn)의 시간 복잡도를 갖는 정렬 알고리즘의 효율성을 깨닫는 것으로 보인다. 하지만 파이썬의 내장 함수를 이용해도 충분히 빠른 시간에 문제를 해결할 수 있다. 중요한 문제는 정렬 알고리즘이..

개발 공부 (알고리즘) 2021. 2. 2. 01:05

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프의 종류 중 하나인 이분 그래프를 판별하는 문제이다. 이분 그래프는 한 정점으로부터 이동한 정점들 사이에서 BFS가 또 수행되면 성립하지 않는다. 즉, 한 정점에서 이미 방문한 정점에 대해 방문했을 때 그 정점이 같은 정점으로부터 방문 받은 정점이라면 이분 그래프가 아닌 것이다. 이를 체크하기 위해서 한 정점으로부터 이동할 때마다 방문을 체크하는 visited 리스트에 두 가지의 숫자를 넣어서..

개발 공부 (알고리즘) 2021. 2. 1. 05:03

www.acmicpc.net/source/25783143 로그인 www.acmicpc.net 언뜻 보면 기존의 문제들과 달라 보이지만 결국 유사한 문제이다. 단순하게 이동하는 방법이 변화했다고 생각하면 쉽게 풀린다. 기존에는 주로 x나 y값에 1을 더하거나 빼는 방식으로 인접한 정점으로 이동했다. 나이트는 두 칸을 상, 하, 좌, 우로 이동한 후에 이동한 방향에 좌 혹은 우로 한 칸 움직이는 방식으로 이동한다. 기존에 미리 정해 놓았던 x와 y 값의 움직임을 나이트의 움직임대로 8가지로 저장해놓으면 된다. 한 정점에서 범위를 벗어나거나 이미 방문한 정점을 제외하고 나이트의 움직임 8가지에 대해 BFS를 수행하면서 목표 위치까지 이동하는 갯수를 센다. [소스코드] from collections import..

개발 공부 (알고리즘) 2021. 2. 1. 04:18

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 앞에서 풀었었던 최단 거리에 특정 목표 지점까지 이동하는 문제들과 같은 맥락의 문제이다. 시작 지점은 항상 같은 위치로 정해져 있고 목표 위치만 입력에 따라 변한다. 다른 문제들과 다른 점은 벽을 한 번 부술 수 있는 "필살기"가 존재한다는 것이다. 시작점에서 출발해서 목표 위치까지 이동할 때 최단 거리로 갈 수 있다면 이동할 수 없는 위치로 이동할 수 있다. 일단 전체적인 문제의 구조..

개발 공부 (알고리즘) 2021. 2. 1. 02:38

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 시작 위치와 목표 위치를 입력 받아 이동하는 최소한의 횟수를 구하는 문제이다. 한 정점 x에서 이동 가능한 지점을 미리 정의하고 BFS를 이용했다. 이동 가능한 위치의 정점이 범위를 벗어나거나, 이미 방문한 정점인 경우는 무시하고 방문이 가능할 경우에는 현재 정점의 값에서 1을 더하면서 이동한다. 한 번 이동할때마다 값을 증가시켜서 최종 필요 시간을 알 수 있게한다. 만약 ..

개발 공부 (알고리즘) 2021. 2. 1. 01:55