Hello

: )

2016년 9월 29일 목요일

Croatian Highschool Competitions in Informatics(CHCI) 문제 정리

CHCI (Croatian Highschool Competitions in Informatics) 문제들은 아래 사이트에 잘 정리되어 있습니다

Solutions/정답 코드: O
Testcase(TC)/Input, Output/입출력 데이터: O
Link: 각 연도별 참조
BOJ: https://www.acmicpc.net/category/25

http://hsin.hr/coci/ 로 가셔서 연도별로 선택하시면 됩니다.









작성자: 시간: 댓글 없음:
라벨:

2016년 9월 24일 토요일

Canadian Computing Competition (CCC) 문제 정리

Canadian Computing Competition (CCC) 문제들도 입출력 데이터가 잘 정리가 되어 제공이 되고 있는데, 답안(Solution)이 C 코드가 아니라서 (2011 년부터 Python) 아쉽네요.

Official
http://www.cemc.uwaterloo.ca/contests/past_contests.html#ccc

Official site 에 link 까지 있는 아래 unofficial site 는 (Python 으로 만든 답안이 있습니다)
http://mmhs.ca/ccc/index.htm

문제에 대한 난이도 및 분류까지 잘 정리되어 참고하기 좋습니다.

BOJ 에는 https://www.acmicpc.net/category/173








작성자: 시간: 댓글 없음:
라벨:

2016년 9월 21일 수요일

순열과 조합

순열(permutation): 순서 고려, 중복 허용하지 않음
중복순열: 순서 고려, 중복 허용
조합(combination): 순서 고려하지 않음, 중복 허용하지 않음
중복조합: 순서 고려하지 않음, 중복 허용


n 개 중에서 r 개를 뽑아

순열: 순서를 정해서
1, 2, 3
1, 3, 2
2, 1, 3
...
nPr = n!(n-r)!, nP0 은 1, nPn 은 1

중복순열: 순서를 정해서, 중복 허용
1, 1, 1
1, 1, 2
1, 1, 3
...
nTTr = n 의 r 제곱승

조합: 순서에 상관없이 (1, 2, 3, 4 중에 2 개 선택)
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

n 개 중 r 개를 선택하는 모든 조합의 경우의 수
nCr = n-1Cr-1 + n-1Cr (nC0 = 1)


중복조합: 순서에 상관없이, 중복 허용  (1,2,3,4 중에 2 개 중복 선택)
1, 1
1, 2
1, 3
1, 4
2, 2
...
nHr = n + r-1Cr
nHr = nHr-1 + n-1Hr


코드
 #include <cstdio>  
 #define REPETITION  
 int T[10]; // nPr 을 이루는 각각의 경우를 저장  
 int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
 void swap(int& i, int& j) {  
   int temp = i;  
   i = j;  
   j = temp;  
 }  
 void process(int q) {  
   int i;  
   for (i = q - 1; i >= 0; i--) {  
     printf("%d ", T[i]);  
   }  
   printf("\n");  
 }  
 void permutation(int n, int r, int q) {  
   if (r == 0) {  
     process(q);  
     return;  
   }  
   int i;  
   for (i = n - 1; i >= 0; i--) {  
     swap(data[i], data[n - 1]); // n-1 을 모든 index 와 swap 해서 다양한 순서를 만든다  
     T[r - 1] = data[n - 1];  
 #ifdef REPETITION  
     permutation(n, r - 1, q);  
 #else  
     permutation(n - 1, r - 1, q);  
 #endif  
     swap(data[i], data[n - 1]);  
   }  
 }  
 void combination(int n, int r, int q) {  
   if (r == 0) {  
     process(q);  
     return;  
   }  
 #ifdef REPETITION  
   else if (n == 0)  
 #else  
   else if (n < r)  
 #endif  
   {  
     return;  
   }  
   else {  
     T[r - 1] = data[n - 1];  
 #ifdef REPETITION  
     combination(n, r - 1, q);  
 #else  
     combination(n - 1, r - 1, q); // n-1Cr-1  
 #endif  
     combination(n - 1, r, q); // n-1Cr  
   }  
 }  
 int main() {  
   permutation(4, 3, 3);  
   combination(4, 2, 2);  
   return 0;  
 }



정리 출처: http://hochulshin.com/permutation-composition-summary/

조금 응용하면 푸는 문제:
6603번: 로또 (https://www.acmicpc.net/problem/6603)
작성자: 시간: 댓글 없음:
라벨:

2016년 9월 16일 금요일

Croatian Open Competition in Informatics(COCI) 문제 정리

*Update: 2022-04-26

COCI (Croatian Open Competition in Informatics) 출처의 문제들은 입출력 데이터와 설명과 답안까지 잘 정리되어 제공되고 있습니다... : )



작성자: 시간: 댓글 없음:
라벨:

2016년 9월 13일 화요일

채점 시스템에서만 compile 오류 발생하는 경우 간단한 확인법

예를 들어, Windows 10 에서 Visual Studio Express 2015 버전으로 code 를 만들고 있는데,
제출한 code 가 채점 시스템 상에서는 컴파일 에러가 발생한다고 하면 다음과 같이 간단히 확인해 볼 수 있다.

1) Windows 10 에 설치된 bash shell 을 실행
  => Windows 기능 켜기/끄기에서 Windows Subsystem for Linux 설치 확인

2) sudo apt-get install build-essential 로 g++ 이용할 수 있도록 설치

3) https://www.acmicpc.net/help/judge 로 가서 각 버전별 빌드 옵션 확인
  => 채점 사이트 별로 확인 필요

4) bash shell command 로 가서 a.cc 에 저장해 둔 code 에 대해서 compile test 진행

예) error 가 없는 경우
GOODDAYTOCODE@DESKTOP-70ILJRL:/mnt/c/home$ g++ a.cc -o Main -O2 -Wall -lm --static -std=c++11 -DONLINE_JUDGE
GOODDAYTOCODE@DESKTOP-70ILJRL:/mnt/c/home$

예) error 가 있는 경우
GOODDAYTOCODE@DESKTOP-70ILJRL:/mnt/c/home$ g++ a.cc -o Main -O2 -Wall -lm --static -std=c++11 -DONLINE_JUDGE
a.cc: In function ‘int main()’:
a.cc:4:5: error: ‘a’ was not declared in this scope
     a = 0;
     ^
GOODDAYTOCODE@DESKTOP-70ILJRL:/mnt/c/home$
작성자: 시간: 댓글 없음:

2016년 9월 12일 월요일

topcoder 사이트의 초보자용 읽을꺼리

topcoder 사이트의 문제는 풀어 볼 엄두도 못 내는 상태지만,
초보자용 가이드 페이지에 좋은 내용이 있는 것 같아서 시간 날 때(?) 읽어 보려고 정리

Data Science Tutorials
https://www.topcoder.com/community/data-science/data-science-tutorials/



1) Dumitru 의 How to Find a Solution

목차
Introduction / 소개
Straight-forward problems that don’t require a special technique / 특별한 기법을 필요로 하지 않는 간단한 문제들
Breadth First Search (BFS) / 넓이 우선 탐색
Flood Fill / 플러드 필
Brute Force and Backtracking / 완전 탐색과 백트래킹
Brute Force / 완전 탐색
Backtracking / 백트래킹
Dynamic Programming / 동적계획법
Hard Drills /
Maximum Flow /
Optimal Pair Matching /
Linear Programming (Simplex) / 선형계획법 (단체법)
Conclusion / 결론


2)
작성자: 시간: 댓글 없음:
피드 구독하기: 글 (Atom)