영

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면..

자료구조 알고리즘/백준 2022. 4. 28. 17:04

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000) 개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/..

자료구조 알고리즘/백준 2022. 4. 27. 08:23

Big-O 알고리즘의 실제 러닝타임보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이다. 예를 들면 데이터가 무한대로 커졌을 때를 상상해보자. 1+1+1+1....+1 은 2*2*2*2*2......*2에 비하면 아주 미비하게 작아 보일 것이다. 전자의 경우 무한대로 가면 x좌표와 맞닿아있다고 생각할 수도 있다. { O(N+N) => O(N) , O(N^2+N^2) => O(N^2)} 이것을 바탕으로 Big-O표기법을 보면 조금 더 이해가 쉬워진다. O(1) O(N) O(N^2) O(NM) O(N^3) O(2^N) Fibonacci Numbers O(logN) Binary Search

자료구조 알고리즘 2022. 4. 26. 02:09

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고..

자료구조 알고리즘/백준 2022. 4. 25. 03:33

DP(Dynamic Programming) f(n)을 1부터 n까지의 곱을 구하는 함수라고 정의를 내리면 f(n) = f(n-1)*n (n>1) : 점화식 f(1) = 1 : 초기조건 첫번째방법으로 for loop를 통하여 1부터 n번까지의 곱을 구할 수 있습니다. f(i-1)의 값을 알고있다는 전제하에 f(1)을 초기조건으로 설정하면 f(n)의 값을 구하는것이 가능해집니다 f[1]=1 for i in range(2,n+1): f[i] = f[i-1]*i print(f[n]) 두번째 방법으로는 재귀함수를 이용하는 것입니다. 백트래킹과 유사하게 종료조건을 초기조건으로 넣어주고 else 부분을 점화식으로 작성해주면 됩니다. def f(n): if n==1: return 1 else: f[n] = f[n-1]..

자료구조 알고리즘/자료구조 2022. 4. 25. 02:04

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 문제 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 안전..

자료구조 알고리즘/백준 2022. 4. 24. 13:31

https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 문제 NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오. 나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다. 현재 나이트의 위치를 (X, Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의..

자료구조 알고리즘/백준 2022. 4. 24. 01:11

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보가..

자료구조 알고리즘/백준 2022. 4. 22. 15:42