slideshare 의 acmicpc 문제 풀이

전에 정리한 백준님 풀이

http://gooddaytocode.blogspot.kr/2016/05/boj.html

Hongjun 님의 풀이

http://www.slideshare.net/ssuser81b91b

Baekjoon Online Judge 1492번 풀이 from Hongjun Jang

1492번: 합 (https://www.acmicpc.net/problem/1492)

4. dynamic programming(1) from Hongjun Jang

1405번: 미친 로봇(https://www.acmicpc.net/problem/1405)
1750번: 서로소의 개수(https://www.acmicpc.net/problem/1750)
11053번: 가장 긴 증가하는 부분수열(https://www.acmicpc.net/problem/11053)
1693번: 트리 색칠하기(https://www.acmicpc.net/problem/1693)

COCI 2006/2007 contest #1 solution from Hongjun Jang

functionx 님의 풀이

http://www.slideshare.net/geunwoobae/2016-functioncup

2016 FunctionCup 풀이 from geunwoo bae

A => 13133번: Aurora Princess(https://www.acmicpc.net/problem/13133)
B => 13134번: Baseball Watching(https://www.acmicpc.net/problem/13134)
C => 13135번: Corrupt Election(https://www.acmicpc.net/problem/13135)
D => 13136번: Do Not Touch Anything(https://www.acmicpc.net/problem/13136)
E => 13137번: Exchange Problem(https://www.acmicpc.net/problem/13137)
F => 13138번: Fairies' Sorcery(https://www.acmicpc.net/problem/13138)
G => 13139번: Grid Forest(https://www.acmicpc.net/problem/13139)
H => 13140번: Hello World!(https://www.acmicpc.net/problem/13140)
I => 13141번: Lgnition(https://www.acmicpc.net/problem/13141)
J => 13142번: Jolly Jelly Jiffy(https://www.acmicpc.net/problem/13142)
K => 13143번: King of Chairs(https://www.acmicpc.net/problem/13143)
L => 13144번: List of Unique Numbers(https://www.acmicpc.net/problem/13144)
M => 13145번: Masonry Bridge(https://www.acmicpc.net/problem/13145)

국민대학교 교내 프로그래밍 경진대회 문제풀이 슬라이드

출처: https://www.acmicpc.net/board/view/10421

D => 13416번: 주식투자(https://www.acmicpc.net/problem/13416)

G => 13419번: 탕수육(https://www.acmicpc.net/problem/13419)

H => 13420번: 사칙연산(https://www.acmicpc.net/problem/13420)

A => 13413번: 오셀로 재배치(https://www.acmicpc.net/problem/13413)

E => 13417번: 카드 문자열(https://www.acmicpc.net/problem/13417)

J => 13422번: 도둑(https://www.acmicpc.net/problem/13422)

K => 13423번: Three Dots(https://www.acmicpc.net/problem/13423)

L => 13424번: 비밀 모임(https://www.acmicpc.net/problem/13424)

B => 13414번: 수강신청(https://www.acmicpc.net/problem/13414)

C => 13415번: 정렬 게임(https://www.acmicpc.net/problem/13415)

F => 13418번: 학교 탐방하기(https://www.acmicpc.net/problem/13418)

I => 13421번: 국민 랜드(https://www.acmicpc.net/problem/13421)

Sogang 2016 대회 E, G, H, M 솔루션

Telcontar 님께서 공유하신 글
https://www.acmicpc.net/board/view/10859#

E => 13904번: 과제(https://www.acmicpc.net/problem/13904)

E from Gimun Eom

G => 13906번: 대문자(https://www.acmicpc.net/problem/13906)

G from Gimun Eom

H => 13907번: 세금(https://www.acmicpc.net/problem/13907)

H from Gimun Eom

M => 13912번: 외계 생물(https://www.acmicpc.net/problem/13912)

M from Gimun Eom

백준님의 다이나믹 프로그래밍을 이용한 문제 풀이

acmicpc 의 블로그에 백준님이 다이나믹 프로그래밍에 대해서 예제를 들어서 작성한 글이 있다. 아래 링크를 참조하자.

다이나믹 프로그래밍 여러가지 점화식으로 풀어보기

https://www.acmicpc.net/blog/view/31

1563번 문제: 개근상(https://www.acmicpc.net/problem/1563)에 대한 풀이 방법 1, 2, 3, 4, 5 를 볼 수 있다.

알고리즘 공개 강의 모음

Computer Science 관련된 공개 강의가 정리된 곳이 있다
https://github.com/prakhar1989/awesome-courses 에 있는 알고리즘 파트를 보면 전에 정리했던 MIT 공개강의 외에도 많은 자료들이 있다

https://github.com/prakhar1989/awesome-courses#algorithms 를 참고하자

cin 과 scanf 에 대해서

10815번: 숫자 카드(https://www.acmicpc.net/problem/10815) 문제는 500,000 개의 입력값이 주어는지는 문제로 cin / cout 을 쓰면 시간 초과가 발생한다.

해결책으로는 scanf / printf 를 사용하거나, cin / cout 전에 std::ios::sync_with_stdio(false) 를 미리 호출해주어서 시간 지연을 막는 방법이 있다.

입출력 방법별 시간 측정값 참고자료: https://algospot.com/forum/read/2496/


하지만, 이 방법이 만능이 될 수는 없는 듯

API Reference: http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio 에 보면 아래와 같이 언급되어 있다.

If the synchronization is turned off, the C++ standard streams are allowed to buffer their I/O independently, which may be considerably faster in some cases.


상황에 따라서 다를 수 있다는 얘기..

같은 문제는 아니지만, 유사 질문에 대한 백준님의 comments 를 보자
위치: https://www.acmicpc.net/board/view/1294

결론은 scanf / printf 쓰는게 제일 무난한 듯...

알고리즘 문제 해석 능력에 관해서

당연한 얘기겠지만, 문제를 읽고 해석하는 능력이 문제를 쉽고 빨리 풀 수 있는 중요한 요인인 것 같다

7569 번: 토마토 (https://www.acmicpc.net/problem/7569) 의 경우 토마토가 익는 과정을 BFS 를 이용한 가장 먼 곳을 찾으면 되는 것임을 깨닫는 과정에 많은 시간 낭비가 있었다

6359 번: 만취한 상범(https://www.acmicpc.net/problem/6359) 은 1 인 경우 +1 을 하면서 반대로 문을 설정하고, 2 인 경우 +2 하면서 반대로 문을 설정하고, 3 인 경우 +3 하면서 반대로 문을 설정하고, n 인 경우 +n 하면서 반대로 문을 설정하는 단순한 조건의 문제이다. 하지만, 문제 설명으로는 무슨 문제인지 이해자체를 못해서 결과를 보고 이해를 했는데, 문제 설명을 계산 문제로 전환할 수 있는 능력이 중요하다가 다시 한 번 느끼게 된 문제...

3055 번: 탈출 (https://www.acmicpc.net/problem/3055) 은 물(*)이 여러 개일 수 있다는 생각을 처음에 할 수 있어야 한다. TC 에서도 마지막에만 있고, 심지어 1 개로 가정하고 먼저 나오는 물을 시작점을 처리하면 예상 결과값이 나온다. 문제를 잘 읽어야 한다는 것을 또 생각하게 해준 문제..

7573 번: 고기잡이 (https://www.acmicpc.net/problem/7573) 의 경우에 여러 입력값 중에 물고기의 최대값은 얼마 안 된다는 것을 보고, 좌표 기준이 아닌 물고기 기준으로 검색해 보면 되는 것을 알아내면 금방 푸는 문제... 입력값을 잘 보자....