Algorithm Cinema

1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이해하기는 쉬운 문제였다만 코드로 구현하기 어려웠다. *문제파악 문제의 첫 조건 1. M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. >> MxN 즉 , 이 전체의 틀은 직사각형일수도 있고 정사각형일 수도 있지만 이들을 8x8 짜리 정사각형으로 강제로 만들어서 이상적인 체스판을..

24313번: 알고리즘 수업 - 점근적 표기 1 (acmicpc.net) 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 이게 전제조건인데 보면 주어진 양수 이상의 모든 구간에 대해 저 조건을 만족하는것을 O()로 정의했다.사실 "여기서 o(N)의 정의를 만족하는지 물어봤기에 G(N)= N인것을 알 수 있고이제는 f(n) ≤..

2563번: 색종이 (acmicpc.net) 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 좌표평면을 다루는다는 생각으로 접근했다. X좌표의 MAX = 100, Y좌표의 MAX= 100. 100X100 짜리 좌표평면에 10X10짜리 정사각형 N개를 올리고, 이 N개들의 넓이의 영역을 구하는 문제이다. 10X10짜리 정사각형이 3개있고 이들이 자신들의 영역이 아닌 각자의 영역을 서로 침범할 경우 넓이의 영역이 300보다 작아지겠다. 이를 고려해야하는 문제임. 내 첫번째 접근은 패턴을 찾는 것이었다. input이 예를들어..

10798번: 세로읽기 (acmicpc.net) 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 5개의 단어를 입력받아 이를 세로로 읽은 값을 띄어쓰기 없이 출력하는 프로그램이다. 각각의 다른 단어들의 글자 순서대로 출력을 하는 것이니까 2중배열을 쓴다면 간단히 해결될 것 같았다. 여기서의 중요한 점은 단어들의 글자수가 다를 수 있다는 것. 예를들어 apple banana 1234 ABee3 답 = ab1Apa2Bpn3ela4een43n3a 마지막 n3이나 a같은 경우 다른 단어들의 알파벳이 없기에 이렇..

2941번: 크로아티아 알파벳 (acmicpc.net) 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 문제는 상당히 직관적이다. 주어진 문자열에서 크로아티아 알파벳이라는 특이한 문자가 있는지 검사하면 끝. indexing을 잘 다루는 능력이 요구된다고 생각한다. c=, c- dz= 와 같은 한 character가 2개이상일 경우를 검사할때 그 이전 인덱스 그 이전의 이전 인덱스 여유공간을 두는 조건문을 적어야만 indexoutofrange오류가 뜨지 않겠다. 그것을 잘 ..