2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8907 에서 채점할 수 있습니다. 풀이 ) 1) '단색 삼각형의 수 = 모든 삼각형의 수 - 두 개의 색이 있는 삼각형의 수' 입니다. 2) '모든 삼각형의 수 = n*(n-1)*(n-2)/6' 입니다. () 3) '두 개의 색이 있는 삼각형' 은 아래의 두 가지 경우가 있습니다. 이 두 가지 경우의 공통점을 찾아보면 서로 다른 색의 간선이 연결된 꼭지점이 2개라는 점이 있습니다. 따라서 위와 같이(서로 다른 색의 두 간선이 한 꼭지점에 연결된 경우의 수) / 2를 구하면 '두 개의 색이 있는 삼각형'의 수를 구할 수 있습니다. cnt[i] = 꼭지점 i에 연결된 빨간색 선의 개수 위와 같은 cnt 배열을 구하면 으로 서로..
(0) [BOJ 10828] 스택 문제에 주어진 함수들을 그대로 구현하면 해결할 수 있습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960//code by RiKang, weeklyps.com #include typedef int node_type;const int stack_size_max = 1000000; struct DS_stack{ int stack_size=0; node_type arr[stack_size_max]; node_type top(){ if(stack_size==0) return -1; return arr[stack_size-1]..
2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8901 에서 채점할 수 있습니다. 풀이 ) 1) 최초의 A의 양 = a, B의 양 = b, C의 양 = c, 그리고 최종적으로 완성한 AB의 양 = i, BC의 양 = j인 경우를 생각해보겠습니다. 그러면 남은 A는 a-i개, C는 c-j개가 있습니다. 이들을 통해 만들 수 있는 CA의 양은 min(a-i,c-j)가 됨은 당연합니다. 굳이 A와 C를 남겨두지 않고 모두 CA로 바꾸는게 이득이기 때문이지요. 따라서 이 경우 답은 ab*i + bc*j + ca*min(a-i,c-j) 가 됩니다. 이때, AB의 양(i)과 BC의 양(j)은 최대 1000개이기 때문에 i=0~1000, j=0~1000인 경우를 모두 고려해보아도 제..
2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8911 에서 채점할 수 있습니다. 풀이 ) 1) 거북이가 거쳐간 모든 좌표들을 알 수 있다면, 직사각형의 크기는 (max_x-min_x) * (max_y-min_y) 로 구할 수 있습니다. (max_x = 거북이가 거쳐간 x 좌표중 최대값, min_x = 거북이가 거쳐간 x 좌표중 최소값, max_y, min_y 도 같은 식입니다.) 2) 이 문제와 같이 90도로 회전하면서 전진하는 상황은 아래의 배열을 선언하여 시뮬레이션할 수 있습니다. 123// code by RiKang, weeklyps.comint dx[4]={0, -1, 0, 1}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 x좌표의 변화입니다.int d..
Table of Contents 개요 기본 구조 반환 삽입 삭제 코드 문제 C++ STL stack 1. 개요 스택은 선형 자료구조 중 하나로서 추상화에 큰 도움을 주는 자료구조입니다. 요약하면 선형 구조의 양 끝 중에서 한쪽에서만 자료를 삽입하고 삭제할 수 있는 자료구조를 뜻합니다. 이 요약의 의미는 이후의 '기본 구조'란에서 자세히 설명하겠습니다. 스택은 간단한 선형 자료구조인 만큼, 배열만을 활용해도 간단히 구현할 수 있습니다. 굳이 스택이라는 새로운 이름을 붙여야 하나 싶을 정도로 간단하지요. 게다가 배열보다 자유도도 낮기 때문에 오히려 할 수 있는 일은 더 줄어들게 됩니다. 하지만 스택은 선형 자료구조를 공부할 때 빼놓지 않고 등장하는 주제로서, 꽤 중요한 자료구조 취급을 받습니다. 이는 스택의..
Table of Contents 개요효율성추상화재사용분류 1. 개요 자료구조란 자료를 저장하는 방법을 뜻합니다. 프로그램 대다수가 자료를 저장하고 사용하기 때문에, 자료구조는 프로그래밍에서 빼놓을 수 없는 요소로 분류되며, 프로그래밍 언어를 익힌 후에 학습해야 할 필수 과목 리스트에 항상 올라와 있습니다. 그런데 사실, 자료구조를 배우고자 하는 분이시라면 이미 자료구조를 사용하고 계실 가능성이 높습니다. C언어, 자바, 파이썬과 같은 언어를 배울 때 사용하는 변수, 배열, 구조체도 자료구조의 일종이기 때문이지요. 여러분들은 언어를 배우실 때 이들을 이용해 자료들을 잘 저장하고 사용해 오셨을 겁니다. 어쩌면 변수와 배열을 이용해 자료를 저장하고 처리할 자신이 있는데, 굳이 자료구조를 배워야 하나 생각하실 ..
Table of Contents 개요시간복잡도의 예시 : O(1), O(n), O(n^2)O 표기법실제 실행 시간 1. 개요 깔끔하고 이해하기 쉬운 코드, 유지 보수하기 좋은 프로그램 구조 등등 좋은 프로그램의 조건에는 여러 가지가 있습니다. 하지만 이런 요소들은 프로그램을 개발하는 사람들의 기준이고, 프로그램을 사용하는 사람 입장에서 중요한 건 아닙니다. 그렇다면 사용자의 입장에서 중요한 건 무엇일까요? 여기에도 다양한 답들이 존재할 수 있지만, 중 저희가 주목해야 할 요소로 프로그램의 실행 시간을 뽑을 수 있습니다. 예를 들어 검색에 3초가 걸리는 사이트와 0.1초가 걸리는 사이트가 있다고 했을 때, 사용자가 느끼는 답답함은 천지 차이일 것입니다. 따라서 프로그램을 만들 때도 실행 시간을 줄이기 위해..
대회 결과 번호 문제 주관적 난이도 풀이 A Accelerator ★★★★★ - B Contour Maps ★★★ 풀이 보기 C Critical 3-Path ★★★ 풀이 보기 D Dot Number ★ 풀이 보기 E Palindrome ★ 풀이 보기 F Pandora ★☆ 풀이 보기 G Pattern Lock ★★ 풀이 보기 H Pole Arrangement ★★ 풀이 보기 I Rock Paper Scissors ★ 풀이 보기 J Slicing Tree ★★★ 풀이 보기 K Sports Repoters ★★★★ 풀이 보기 L Square Annulus ★★★☆ 풀이 보기 * A번 풀이는 채점 활성화 이후 업로드 예정입니다.
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8898에서 채점할 수 있습니다. 풀이 ) i 경기 이후에 j 경기를 취재할 수 있는 경우, 즉, 인 경우를 ( i -> j )라고 표현하겠습니다. 그러면 이 문제를 '취재할 수 없는 가장 큰 경기의 부분집합의 크기 구하는 문제'에서, '최소한의 경기들을 삭제해서 서로 간선이 없도록 하는 문제'로 바꿀 수 있습니다. 전체 경기 수 - 삭제한 경기 수가 답이 되기 때문이지요. 이제 다음과 같은 이분 그래프를 구성해 보겠습니다. ( i->j ) 인 경우, ( i -> n+j ) 로 간선을 그린 것입니다. (1->2), (2->3), (1->3) 의 경우입니다. 이 그래프에서 만일 최소한의 정점 쌍(2와 n+2를 동시에 없애는 것..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8899 에서 채점할 수 있습니다. 풀이 ) 1) 문제 지문을 보면 German research group가 아래와 같은 사실이 보장한다고 나옵니다. There exists a square annulus A of minimum width containing N given points such that its bigger square is a smallest axis-parallel square containing the N points. 이 말에 따르면, 큰 정사각형을 'N개의 점을 모두 포함하는 가장 작은 정사각형' 중에서만 골라도 정답을 찾을 수 있습니다. 'N개의 점을 모두 포함하는 가장 작은 정사각형'의 한 변의 길이..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8890 에서 채점할 수 있습니다. 요약 ) 동적계획법으로 해결할 수 있는 문제로, DP 문제의 정의를 아래와 같이 하면 dp[t1][t2][t3]로 정답을 알 수 있습니다. dp[i][j][k] = s1 -> i, s2 -> j, s3 -> k 로 갈 때의 정답 (3개의 경로의 가중치 합의 최대값) 주의해야 할 것은 경로 상의 정점이 중복되면 안된다는 점입니다. 간단한 DP 문제 정의로도 해결 가능함에도, 이 중복 제거 조건 때문에 문제가 까다롭게 느껴질 수 있습니다. 이 풀이에서는 max(i,j,k) = 1 인 dp[i][j][k]들부터, max(i,j,k) = n 인 dp[i][j][k]들까지, max(i,j,k) 순서..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8889 에서 채점할 수 있습니다. 요약 ) 1) x, y 좌표의 최대값은 10억이지만, 갯수는 200만개 이하이기 때문에 좌표 압축을 통해 각각의 좌표를 1 ~ 200만으로 바꿀 수 있습니다. 2) 최대 높이인 영역이 꼭지점을 하나 이상 포함하기 때문에, 모든 꼭지점의 높이 중 최대 높이만 구해도 전체 좌표 중 최대 높이가 됩니다. 3) 특정 y좌표 (y1) 에 대한 segment tree를 통해, y좌표가 y1인 꼭지점(x1,y1)의 높이를 구할 수 있습니다.segment tree 는 아래의 식이 성립하도록 설정해야 합니다.0 ~ x1위치의 총합 = 좌표 (x1,y1) 꼭지점의 높이이는 y = y1직선과 등고선의 교차점을..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8893 에서 채점할 수 있습니다. 요약 ) LRLLRLL 형식으로 주어지는 다각형이 y축으로 monotone 인지를 확인하면 해결할 수 있습니다. (x축은 y축과 비슷한 방법으로 해결 가능합니다.) y축으로 monotone이 아니기 위해선 y축 방향으로 오목한 부분이 있어야 합니다. 그래야 y축에 평행한 직선이 다각형을 여러 번 자를 수 있습니다. 다시 말하면 아래와 같은 진행 방향이 나와야만 y축으로 monotone이 아닙니다. 반시계 방향으로 돌아가기 때문에, y축 monotone에 영향을 끼치는 오목한 부분은 위의 두 가지 경우만이 존재합니다. 다시 말하면 이 두 가지 경우가 모두 없다면 monotone 이고, 둘 중..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8894에서 채점할 수 있습니다. 요약 ) 가능한 모든 패턴, 즉, 1,2,...,9 으로 만들 수 있는 모든 순열(중복 허용 X)을 재귀호출로 찾아도 O(9!) 안에 찾을 수 있습니다. 그리고 9! = 362880 입니다. 따라서 이 문제는 모든 패턴을 찾아보면서 입력으로 들어온 그래프와 비교해 보아도 제한 시간을 맞춰 줄 수 있습니다. 문제에서 주어진 예외 사항들을 잘 고려하면서, 재귀호출을 이용하여 모든 패턴을 찾는 프로그램을 구현하면 해결할 수 있습니다. 구현이 핵심인 문제이기 때문에, 코드를 중심으로 봐주시기 바랍니다. 재료 준비 ) 1234567891011121314151617181920212223242526272..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8891에서 채점할 수 있습니다. 요약 ) 이 문제는 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현하면 해결할 수 있습니다. 이 두 함수를 구하기 위해선 점 숫자의 특징을 잘 관찰해야 합니다. 점 숫자의 가장 큰 특징으로는 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점이 있습니다. 이 점을 최대한 활용하기 위해 '대각선 시작 지점의 점 숫자'들을 저장한 배열을 만들면 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현할 수 있습니다. x=1 일 때(대각선 시작 지점) 점 숫자 구하기 ) 123456..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8895에서 채점할 수 있습니다. 요약 ) 문제는 높이가 1,2,...,n 인 n개의 막대를 일렬로 세울 때, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개가 되는 경우의 수를 구하는 것입니다. 이 문제는 '문제'를 '하위 문제'들로 나누어 해결하는 동적계획법으로 해결할 수 있습니다. DP 배열 구하기 ) 먼저 DP문제를 정의해야 합니다. 다행히 이 문제는 있는 그대로, 아래처럼 DP를 정의해도 해결할 수 있습니다. dp[n][l][r] = n개의 막대, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개일 때의 답 이제 하위 문제를 찾아야 합니다. 높이가 n인 막대의 위치를 기준으로 하위 문제를 설정..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8896에서 채점할 수 있습니다. 요약 ) N개의 로봇이 모두 모여 가위 바위 보를 하는 문제입니다. 각 로봇이 R, S, P 중 무엇을 낼지 정해져 있으므로, 가위 바위 보를 통해 로봇이 탈락하고 살아남는 과정을 그대로 구현하면 됩니다. 여기에서는 아래와 같은 배열 alive 를 관리하면서 구현하였습니다. alive[i] = i번째 로봇이 아직 살아있는가? 살아있으면 yes, 탈락했으면 no 초기화 ) 123456// code by RiKang, weeklyps.comscanf("%d",&n);for(int i=1; i>s[i]; alive[i] = true;}cs 먼저 초기화 부분에선 모든 로봇이 살아있도록 설정합니다. ..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8892 에서 채점할 수 있습니다. 요약 ) 문제는 k개의 단어가 주어졌을 때, 그 중 2개의 단어를 붙여서 만든 문자열 중 팰린드롬이 있으면 그 중 아무거나 출력하고, 팰린드롬이 없으면 0을 출력하는 것입니다. 친절하게도 모든 단어 길이의 합이 10000이하임이 보장되므로, 만들 수 있는 모든 문자열을 만들어서 하나 하나 검사하여도 제한 시간내에 해결할 수 있습니다. 팰린드롬 체크 함수 ) 모든 문자열을 검사하려면, 먼저 문자열이 팰린드롬인지를 검사하는 함수를 만들어야 합니다. 팰린드롬의 정의에 따라 아래와 같이 구현할 수 있습니다. 1234567// code by RiKang, weeklyps.combool is_pal(..
Table of Contents 개요구조체 정의구조체 선언구조체 사용 1. 개요 지금까지 저희는 변수와 배열을 사용하여 자료를 저장해 왔습니다. 하지만 C언어에서 지원하는 변수들의 종류는 많지 않기 때문에, 복잡한 자료를 저장하기엔 효율적이지 않습니다. 예를 들면, 고등학교 한 반에 있는 학생들의 이름, 키, 몸무게를 저장해야하는 상황이 있습니다. 이름은 문자열, 키와 몸무게는 실수형 변수로 저장한다고 해보면 아래와 같이 됩니다. 12345678910//code by RiKang, weeklyps.com#include char student_name[55][21]; // 이름float student_height[55]; // 키float student_weight[55]; // 몸무게 int main()..
(0) [BOJ 1110] 더하기 사이클 1234567891011121314151617181920212223//code by RiKang, weeklyps.com#include int next_m(int v){ int v1 = v%10; // 1의 자리 int v2 = v/10; // 10의 자리 return v1*10 + (v1+v2)%10;} int main() { int n, m, ans=0; scanf("%d",&n); m = n; while(1){ // break; 전까지 무한루프 ans++; m = next_m(m); if(n==m){ // m이 초기값인 n으로 돌아왔으므로, 이 지점의 ans가 루프의 길이가 됨. printf("%d",ans); break; } } return 0;}Color..
Table of Contents 개요 기본 문법 함수의 정의 함수의 호출 함수의 선언 전역 변수와 지역 변수 호출 방식 문제 1. 개요 C언어로 만든 프로그램은 운영체제가 main() 함수를 호출하며 시작하고, main() 함수가 0을 반환하면 종료하게 됩니다. 따라서 지금까지는 main() 함수 안에 모든 명령문을 작성하는 식으로 프로그래밍을 해왔습니다. 하지만, 복잡한 프로그램을 만들게 되면 이런 방식은 곧 한계에 부딪힙니다. 예를 들기 위해, 앞글에서 살펴본 strlen() 함수가 존재하지 않는다고 가정하면 어떻게 되는지 생각해보겠습니다. 그러면 일단 strlen()의 효과를 얻을 수 있는 3줄 정도의 명령문을 작성하게 될 것입니다. 물론 여기까지는 1줄로 끝낼 수 있는 작업이 3줄 정도로 늘어난 ..
(0) [BOJ 4999] 아! 12345678910111213//code by RiKang, weeklyps.com#include #include int main() { char a[1005]; char b[1005]; scanf("%s",a); scanf("%s",b); if(strlen(a)>=strlen(b)) printf("go"); else printf("no"); return 0;}Colored by Color Scriptercs (1) [BOJ 5026] 박사 과정 123456789101112131415161718192021222324252627282930//code by RiKang, weeklyps.com#include #include int main() { int n; char a[1..
Table of Contents 개요 strlen() strcmp() strcpy() strcat() 문제 1. 개요 문자열이 다른 변수형의 배열들과 다른 점은, 문자열 자체가 하나의 의미를 가지는 경우가 많다는 점입니다. int 변수가 여러 개가 모여 하나의 의미를 나타내는 경우는 거의 없지만, 문자가 모여 하나의 의미를 나타내는 경우는 굉장히 많습니다. 간단하게 문자를 사용하는 예시를 생각해보면 이름, 제목, 검색 키워드등이 있지요. 이들 모두 문자 한 개보다는 문자열로 표현해야 하는 경우가 많음을 알 수 있습니다. 따라서 문자열은 그 자체를 자유롭게 사용할 수 있어야 합니다. 하지만 문자열도 결국 char들의 배열로 사용되며, 배열 전체를 하나의 변수만큼이나 자유롭게 쓰기는 굉장히 어렵습니다. 예를..
Table of Contents 선형 검색 (linear search) 이분 검색 (binary search) 삼분 검색 (ternary search) 문제 1. 선형 검색 (linear search) 가장 간단한 검색 알고리즘입니다. 목록의 처음부터 끝까지 탐색하여, 모든 요소들과 비교해보는 방법입니다. 예를 들기 위해 다음과 같은 문제를 풀어보겠습니다. 문제 ) 첫 번째 줄에 두 자연수 N, M 이 주어진다. (N,M arr[mid2] 인 경우 : 검색 범위를 mid1 ~ N 으로 줄일 수 있습니다. ( * 최솟값이 mid1 보다 이전에 있다고 가정하면, arr[mid1] < arr[mid2] 가 성립하므로 모순입니다.) 경우 2) arr[mid1] =3) { int range = (r-l)/3; i..
Table of Contents 개요기본 문법간접 참조오프셋포인터와 배열 1. 개요 포인터는 다른 프로그래밍 언어에서는 찾아보기 힘든 C언어의 문법입니다. 또한 고급 언어이면서도 저급 언어에 가까운 C언어의 특징을 잘 나타내주는 요소이기도 합니다. 특이하게도 메모리의 주소를 다루기 위한 문법이기 때문입니다. 포인터를 공부하시는 분이라면, 지금까지 C언어를 공부하면서 메모리에 여러가지 변수들을 저장하고 사용해 오셨을 겁니다. 그런데 변수들을 저장하는 컴퓨터의 메모리는 4byte, 8byte 쯤은 모래알처럼 느껴질 만큼 방대한 용량을 가지고 있습니다. 어떻게 C 컴파일러는 그 방대한 메모리에서 변수의 값을 정확하게 읽어내는 것일까요? 그건 메모리의 각 칸에 '주소(address)'가 있기 때문입니다. 마치 ..
개요 간단한 정렬 문제를 생각해보자. 먼저 자연수N을 입력받는다. (1
Table of Contents 개요 기본 구조 값 삽입 최대값 삭제 힙 정렬 C++ STL priority_queue 1. 개요 힙은 이진 트리를 활용한 자료구조이며, 종류로는 최소 힙과 최대 힙이 있습니다. 최대 힙을 알면 최소 힙을 만드는 건 어렵지 않으므로, 이 문서에서는 최대 힙을 기준으로 설명하도록 하겠습니다. 최대 힙 자료구조는 기본적으로 아래의 세 연산을 빠르게 수행하기 위한 자료구조입니다. 연산 1) 최대 힙에 새로운 값을 삽입. 연산 2) 최대 힙 안의 최대값을 삭제. 연산 3) 최대 힙 안의 값 중에 최대값 찾기. 이 세 연산을 배열로 간단하게 처리하려고 하면, 삽입은 O(1)로 가능하더라도 최대값을 찾기에서 O(N) 이 필요함을 알 수 있습니다. 배열에서 최대값을 찾기 위해선, 배열..
Table of Contents 개요 병합 병합 정렬 문제 STL sort 시간복잡도 계산 1. 개요 병합 정렬은 원소들을 번호순, 사전순과 같이 정해진 순서대로 열거하는 정렬 알고리즘 중 하나입니다. 정렬된 두 집합을 하나의 정렬된 집합으로 합치는(병합하는)데에 필요한 시간복잡도가 O ( 두 집합의 원소의 갯수 ) 라는 점, 그리고 분할정복을 이용하여 병합 정렬을 구현하면 총 시간복잡도 O ( N log N ) 만에 정렬이 가능합니다. 이 문서에서는 병합 정렬을 이용하여, 숫자들을 오름차순으로 정렬하는 방법을 소개합니다. 2. 병합 병합 정렬을 구현하기 위해선, 정렬된 두 집합을 하나의 집합으로 합치는 함수를 구현해야 합니다. 예시 ) A = {1, 3}, B = {2, 4} -> {1, 2, 3, 4..
Table of Contents 개요 변수형 변환 1. 개요 C언어에는 많은 변수형이 존재하며, 상황에 따라 여러 변수형을 혼합해서 사용하는 경우가 있습니다. 123456789101112//code by RiKang, weeklyps.com#include int main(void) { int a = 3; double b = 3.3; int c = a+b; double d = a+b; printf("c = %d\n",c); printf("d = %lf\n",d); return 0;}cs 이 문서에서는 이처럼 서로 다른 변수형을 같이 이용할 때, 컴파일러가 어떤 식으로 처리하는 지에 대해 다룹니다. 2. 변수형 변환 C 컴파일러가 판단하는 변수형의 표현 범위 크기는 아래의 순서에 따릅니다. 오른쪽으로 갈수록..