분류 전체보기

[백준] 1182번: 부분수열의 합_JAVA

문제(1182번: 부분수열의 합 (acmicpc.net) 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,..

[백준] 1018번: 체스판 다시 칠하기_JAVA

문제(https://www.acmicpc.net/problem/1018) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 ..

[CSAPP] 5.9 Enhancing Parallelism(병렬성 향상시키기)

5.9 Enhancing Parallelism(병렬성 향상시키기) 이 시점에서 우리의 기능은 산술 unit의 latency에 의한 한계에 도달했다. 그러나 덧셈과 곱셈을 수행하는 functional unit은 모두 fully pipelined으로 되어 있다. 이는 매 clock cycle 마다 새로운 operation을 시작 할 수 있으며, 일부 operation은 여러 functional unit에서 수행될 수 있는 것을 의미한다. 하드웨어는 더 높은 속도로 곱셈과 덧셈을 수행할 수 있는 잠재력을 가지고 있지만, 우리 코드는 단일 변수 acc로 값을 축적하고 있기에(루프 언롤링으로 성능 향상 불가) 이 기능을 활용할 수 없다. 이전 계산이 완료될 때까지 acc에 대한 새 값을 계산할 수 없기 때문이다...

[CSAPP] 5.8 Loop Unrolling(루프 풀기)

5.8 Loop Unrolling(루프 언롤링) Loop Unrolling(루프 언롤링)이란 각 반복에서 계산되는 요소의 수를 늘려 루프틔 반복 횟수를 줄이는 프로그램 변환법이다. 5.2에서 나온 psum2가 대표적인 예시이다. 아래 코드가 루프 언롤링을 적용한 것. psum1 -> psum2 /* Compute prefix sum of vector a */ 2 void psum1(float a[], float p[], long n) { long i; p[0] = a[0]; for (i = 1; i < n; i++) p[i] = p[i-1] + a[i]; } void psum2(float a[], float p[], long n) { long i; p[0] = a[0]; for (i = 1; i < n-..

[CSAPP] 5.7 Understanding Modern Processors(현대 프로세서 이해)

5.7 Understanding Modern Processors(최신 프로세서 이해) 코드의 성능을 더 개선하기 위해서는 프로세서의 마이크로구조, 즉 프로세서가 instruction을 실행하도록 하는 하부 시스템 설계를 활용하는 최적화 기법을 고려해야 함. 성능 향상을 위해 현대 프로세서의 마이크로구조를 이해해야 한다. 현대 프로세서는 많은 트렌지스터들이 하나의 칩으로 구성되어 있기 때문에 현대의 마이크로프로세서는 프로그램 성능을 극대화시키는 복잡한 하드웨어에 적용될 수 있다. 실제 동작은 기계어 프로그래밍(machine level)에서와 다르다. 코드 레벨(code level)에서는, 한번에 하나의 instruction이 실행 되는 것처럼 보인다. 실제 프로세서에서는 여러 개의 instrucions이 ..