GOOD DAY TO CODE: 5월 2016

2016년 5월 31일 화요일

http://ilyoan.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%EA%B8%B0%EB%B2%95-6-%EC%83%81%ED%83%9C%EB%A5%BC-%EB%82%98%ED%83%80%EB%82%B4%EB%8A%94-%EA%B0%92%EC%8B%BC-%EB%B0%A9%EB%B2%95bits

트리의 지름

2016년 5월 26일 목요일

BOJ 의 여러 문제에 대한 백준님의 문제 풀이들

Slideshare(http://www.slideshare.net/Baekjoon/) 에 있는 백준님의 문제풀이들입니다.

(1)

Baekjoon Online Judge 1328, 8895번 풀이 from Baekjoon Choi

1328번: 고층빌딩(https://www.acmicpc.net/problem/1328)
8895번: 막대 배치(https://www.acmicpc.net/problem/8895)

(2)

Baekjoon Online Judge 10986번 풀이 from Baekjoon Choi

10986번: 나머지 합(https://www.acmicpc.net/problem/10986)

(3)

Baekjoon Online Judge 2873번 풀이 from Baekjoon Choi

2873번: 롤러코스터(https://www.acmicpc.net/problem/2873)

(4)

Baekjoon Online Judge 1201번 풀이 from Baekjoon Choi

1201번: NMK(https://www.acmicpc.net/problem/1201)

(5)

Baekjoon Online Judge 1648번 풀이 from Baekjoon Choi

1648번: 격자판 채우기(https://www.acmicpc.net/problem/1648)

(6)

Baekjoon Online Judge 1451번 풀이 from Baekjoon Choi

1451번: 직사각형으로 나누기(https://www.acmicpc.net/problem/1451)

(7)

Baekjoon Online Judge 1019번 풀이 from Baekjoon Choi

1019번: 책 페이지(https://www.acmicpc.net/problem/1019)

(8)

Baekjoon Online Judge 3015번 풀이 from Baekjoon Choi

3015번: 오아시스 재결합

(9)

2014 ACM-ICPC Daejeon 인터넷 예선 해설 from Baekjoon Choi

Coder’s High 2014 풀이 from Baekjoon Choi

(11) SCPC 2015 예선 풀이 (1/2)

(12) SCPC 2015 예선 풀이 (2/2)

(13) DP 강의

BOJ 의 blog 에 있는 문제풀이들입니다.

(1) 다이나믹 프로그래밍 여러가지 점화식으로 풀어보기
https://www.acmicpc.net/blog/view/31

1563번: 개근상(https://www.acmicpc.net/problem/1563)

(2) 나머지 연산의 곱셉 역원
https://www.acmicpc.net/blog/view/29

11401 번:이항 계수 3(https://www.acmicpc.net/problem/11401)

(3) 피보나치 수를 구하는 여러가지 방법
https://www.acmicpc.net/blog/view/28

2747 번:피보나치 수(https://www.acmicpc.net/problem/2747)
2748 번:피보나치 수 2(https://www.acmicpc.net/problem/2748)
2749 번:피보나치 수 3(https://www.acmicpc.net/problem/2749)
10870 번:피보나치 수 5(https://www.acmicpc.net/problem/10870)
11444 번:피보나치 수 6(https://www.acmicpc.net/problem/11444)
1629 번: 곱셈(https://www.acmicpc.net/problem/1629)

(4) 점 3개의 방향성을 나타내는 CCW
https://www.acmicpc.net/blog/view/27

11758 번:CCW(https://www.acmicpc.net/problem/11758)

(5) 세그먼트 트리 나중에 업데이트 해야지!
https://www.acmicpc.net/blog/view/26

10999 번:구간 합 구하기 2(https://www.acmicpc.net/problem/10999)

(6) 가장 가까운 두 점 찾기
https://www.acmicpc.net/blog/view/25

2261 번:가장 가까운 두 점(https://www.acmicpc.net/problem/2261)

(7) 펜윅 트리 (바이너리 인덱스 트리)
https://www.acmicpc.net/blog/view/21

2042 번:구간 합 구하기(https://www.acmicpc.net/problem/2042)

(8) 히스토그램에서 가장 큰 직사각형
https://www.acmicpc.net/blog/view/12

6549 번:히스토그램에서 가장 큰 직사각형(https://www.acmicpc.net/problem/6549)
1725 번: 히스토그램(https://www.acmicpc.net/problem/1725)

(9) 세그먼트 트리 (Segment Tree)
https://www.acmicpc.net/blog/view/9

2042 번: 구간 합 구하기(https://www.acmicpc.net/problem/2042)
10868 번: 최소값(https://www.acmicpc.net/problem/10868)
2357 번: 최소값과 최대값(https://www.acmicpc.net/problem/2357)

(10) Java Scanner와 BigInterger 사용하기
https://www.acmicpc.net/blog/view/3

10757 번: 큰 수 A+B(https://www.acmicpc.net/problem/10757)
10827 번: a^b(https://www.acmicpc.net/problem/10827)

2016년 5월 16일 월요일

알고리즘 공부에 대한 최백준님의 강의 자료

개인적인 소감은 나중에 좀 더 수준이 높아지면 도움이 될 듯한 내용이네요. (어렵다는..)

나는 어떻게 알고리즘 공부를 했을까? - 최백준 님

나는 어떻게 알고리즘을 공부했을까? + 신기한 방법으로 문제 풀어보기 from Baekjoon Choi

2016년 5월 6일 금요일

다시 풀어봐야 하는 문제 정리

1010번: 다리놓기 (https://www.acmicpc.net/problem/1010)

DP, M 개의 지점에서 N 개를 선택하는 조합 문제

1328번: 고층빌딩(https://www.acmicpc.net/problem/1328)

DP, d[i][j][k] = d[i-1][j-1][k] + d[i-1][j][k-1] + d[i-1][j][k] * (i-2);
같은 문제 - 8895번: 막대 배치(https://www.acmicpc.net/problem/8895)

1094번: 막대기(https://www.acmicpc.net/problem/1094)

진수 변환, 10 진수 => 2 진수, 1 의 개수

2096번: 내려가기 (https://www.acmicpc.net/problem/2096)

DP, 메모리 제한으로 sliding window 를 적용해서 풀어야 한다

2193번: 이친수 (https://www.acmicpc.net/problem/2193)

DP, f(n) : 길이 n 인 이친수의 개수, f(n) = f(n-1) + f(n-2)

2294번: 동전 2

DP, f(s) : 합이 s 인 동전의 최소 개수, f(s) = f(s-a) + 1 (a는 동전 가치)

2579번: 계단 오르기

DP, D[N,0]은 이전 단계까지 더해온 값에 현재 계단 값을 더한 값이고,
D[N,1]은 2계단 전까지 왔던 값에 현재값을 더한 값이다.
그 두 값 중 max값을 계속 갱신해가면 마지막엔 최대값

2661번: 좋은 수열 (https://www.acmicpc.net/problem/2661)

이미 만들어진 좋은 수열을 가지고 길이를 늘여나가는 방식

6588번: 골드바흐의 추측 (https://www.acmicpc.net/problem/6588)

50만 이하인 소수 a 에 대해, n - a 도 소수이면 답, a 를 찾지 못하면 예외

7562번: 나이트의 이동 (https://www.acmicpc.net/problem/7562)

BFS, DFS 에 비해 최단 거리, 최소 값을 구하는 데 유리한 경우가 많음

7579 번: 앱

DP, ...

11726번: 2 x n 타일링 (https://www.acmicpc.net/problem/11726)

DP, f(n) : 2 x n 을 채우는 모든 경우의 수, f(n) = f(n-1) + f(n-2)

11727번: 2 x n 타일링 2 (https://www.acmicpc.net/problem/11726)

DP, f(n) : 2 x n 을 채우는 모든 경우의 수, f(n) = f(n-1) + f(n-2) + f(n-2)

알고리즘 공부 순서에 대한 글 소개

늦은 나이에 알고리즘 공부하다 보니 이게 뭔가 싶은 생각이 많이 드는 요즘이었는데, 백준님이 BOJ 자유게시판에 쓴 글을 우연히 보고 정리가 좀 되는 것 같기도 하네요.

알고리즘을 어떤 순서로 공부해야 할 지 모르는 분들께

라는 백준님의 글입니다.

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

참고를 위한 요약 버전

1. 알고리즘과 입/출력

알고리즘을 공부하는 방법

시간 복잡도

입/출력을 받는 방법

2. 자료구조 1

스택

큐

덱

문자열

3. 다이나믹 프로그래밍 1

4. 수학 1

나머지 연산

최대 공약수와 최소 공배수

소수

소인수분해

진법 변환

팩토리얼

5. 정렬

STL의 sort를 응용하는 방법

O(NlgN) 정렬 알고리즘

퀵 소트와 머지 소트는 '분할 정복' 챕터

힙 소트는 '자료구조 2' 챕터

6. 그래프 1

그래프를 저장하는 방법 세 가지 - 인접 행렬, 인접 리스트, 간선 리스트

인접 리스트: 시간과 공간이 더 효율적

효율적인 알고리즘 구현을 위해서 STL의 vector를 사용해서 인접 리스트를 구현

간선 리스트라는 자료구조

그래프의 탐색 - DFS / BFS

DFS와 BFS의 응용 - 연결 요소 / 이분 그래프

그래프에서 가장 중요한 것 => 문제를 그래프로 모델링

그래프 모델링을 연습하기 위해서 사이클을 찾는 연습

이차원 배열 상에서 플로드 필 알고리즘

7. 트리 1

트리를 순회하는 방법: 프리 오더, 인 오더, 포스트 오더

그래프와 마찬가지로 트리를 저장하는 방법 세 가지

트리의 부모에 대한 내용과 트리의 지름

8. 그리디 알고리즘

어렵지만 풀 수 있다

증명이 중요

잘하는 방법은 다양한 문제를 푸는 것

9. 분할 정복

문제를 분할한 다음 합쳐서 문제를 푸는 알고리즘

대표: 이분 탐색 알고리즘 / 머지 소트 / 퀵 소트

가장 가까운 두 점을 찾는 방법: 분할 정복 알고리즘의 하이라이트

10. 이분 탐색으로 정답 찾기

정렬된 리스트에 어떤 수가 있는지 없는지를 조사하는 알고리즘

주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용

11. 완전 탐색 1 (모든 경우 다 해보기)

여섯 가지

부르트 포스(Brute Force)
N중 for문을 이용해서 문제를 푸는 방법
순열을 이용해서 모든 경우를 중복 없이 다 해보는 방법
가장 중요한 알고리즘 중의 하나인 BFS를 이용해서 모든 경우를 다 해보는 방법
재귀 호출을 이용해서 백트래킹
비트마스크를 이용해서 모든 경우를 중복 없이 다 해보는 방법

12. 완전 탐색 2

정답이 될 수 있는 것만 다 해보는 (일부 경우만 다 해보는) 알고리즘

완전 탐색 1에서 배운 BFS를 덱을 사용해서 하는 방법

탐색의 규모가 너무 큰 경우에 문제의 크기를 절반으로 나누어서 푸는 중간에서 만나는 알고리즘 (Meet in the Middle) 알고리즘

13. 자료구조 2

스택을 조금 더 화려하게 사용

그래프 알고리즘 중에서 크루스칼을 배울 때 필요한 Disjoint-set

비트마스크

힙 - 최대 힙과 최소 힙 / 힙을 구현, 힙 소트

이진 검색 트리 (BST)

14. 다이나믹 프로그래밍 2

15. 수학 2

다른 문제를 풀 때 필요한 경우가 많아서 배우는 부분

a^b 제곱 연산

분할 정복 알고리즘을 이용해서 구하는 방법
이진수의 원리를 이용해서 구하는 방법

행렬

피보나치 - 피보나치 수를 구하는 다양한 방법, 피사노 주기, 피보나치 수의 다양한 성질, 피보나치 수를 행렬을 이용해서 구하는 방법

이항 계수 - 파스칼의 삼각형

카탈란 수

오일러 피 함수

두 수를 나눌 때, 나머지 연산을 어떻게 해야하는지 배움

확장 유클리드 알고리즘

순열 - 다음 순열 / 이전 순열 / 모든 순열 / 순열의 순서

16. 그래프 알고리즘 2

위상 정렬

최소 스패닝 트리 (MST) - 프림 / 크루스칼

최단 경로 알고리즘 -벨만 포드 알고리즘 / 다익스트라 알고리즘 / 플로이드 와샬 알고리즘

17. 트리 2

가장 가까운 공통 조상(LCA) - 직관적 구현 / 다이나믹 프로그래밍

임의의 두 정점 사이의 거리를 BFS 알고리즘보다 빠르게 구하는 방법

18. 구간의 최소값 구하기

그냥 다 해보는 방법

이차원 배열에 저장해서 구하는 방법

루트 N으로 나눠서 구하는 방법 (sqrt decomposition)

다이나믹 프로그래밍을 이용해서 구하는 방법

세그먼트 트리를 이용해서 구하는 방법

슬라이딩 윈도우 알고리즘

19. 구간의 합 구하기

누적합을 이용

세그먼트 트리를 이용

펜윅 트리(바이너리 인덱스 트리)를 이용

구간을 업데이트하는 경우: 세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)

세그먼트 트리

BIT

20. 세그먼트 트리 활용하기

구간의 최소값과 합을 구할 때 사용

분할 정복과 함께 세그먼트 트리를 사용

최소값을 찾는 방법을 이용해서 K번째를 찾는 방법

21. 다이나믹 프로그래밍 3

비트마스크를 이용해 상태를 나타내고 그 상태를 다이나믹에 이용

한 문제를 5가지 서로 다른 점화식으로 풀기

22. 네트워크 플로우

네트워크 플로우: 가장 중요한 알고리즘

최대 유량을 구하는 두 가지 알고리즘 - Ford-Fulkerson / Edmond-Karp

이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합

그래프 모델링을 연습

23. 최소 비용 유량 (MCMF)

최대 유량 문제에서 최소 비용문제가 추가되면 최소 비용 유량 문제

그래프 모델링하는 연습

24. 그래프 알고리즘 3

오일러 회로를 구하는 방법

강한 연결 요소 (SCC)을 구하는 Kosaju's Algorithm과 Tarjan's Algorithm

DFS Tree

Tarjan's Algorithm 을 응용해 단절점과 단절선을 구하는 방법

2-SAT 문제

25. 다이나믹 프로그래밍 4

트리 다이나믹

왼쪽과 오른쪽을 왔다갔다 하면서 푸는 다이나믹

다이나믹 점화식을 통해서 정답을 역추적하는 방법

확률 다이나믹

왼쪽과 오른쪽에서 시작해서 가운데로 모이는 다이나믹

26. 문자열 알고리즘

문자열 매칭 알고리즘: KMP, Trie, Aho-corasick, Suffix Array

27. 기하 알고리즘

원, 직선, 선분과 같은 도형에 대한 내용

다각형에 대한 내용

CCW 알고리즘: 선분의 교차를 판별하는 방법

어떤 점이 다각형의 내부에 있는지 아닌지, 다각형의 넓이를 구하는 방법

볼록 껍질(Convex Hull)을 구하는 방법인 그라함 스캔(Graham Scan)

라인 스위핑 알고리즘(Line Sweeping Algorithm) - 가장 가까운 두 점

로테이핑 캘리퍼 알고리즘(Rotating Calipers) - 가장 먼 두 점

겹치는 선분 문제

직사각형 N개의 합집합

28. 알고리즘 게임

조합 게임(Combinatorial Game) 문제 중에서 Impartial Game 문제를 푸는 방법

돌 게임(Subtraction Game)

님 게임 (Nim Game)

The Sprague-Grundy Function을 이용해 조합 게임 문제를 푸는 방법

다양한 님 게임 변형 문제의 Grundy Number

GOOD DAY TO CODE

Hello

2016년 5월 31일 화요일

문제 풀이로 참고했던 글들

2016년 5월 26일 목요일

BOJ 의 여러 문제에 대한 백준님의 문제 풀이들

2016년 5월 16일 월요일

알고리즘 공부에 대한 최백준님의 강의 자료

2016년 5월 6일 금요일

다시 풀어봐야 하는 문제 정리

알고리즘 공부 순서에 대한 글 소개

알고리즘을 어떤 순서로 공부해야 할 지 모르는 분들께

Hello

2016년 5월 31일 화요일

문제 풀이로 참고했던 글들

2016년 5월 26일 목요일

BOJ 의 여러 문제에 대한 백준님의 문제 풀이들

2016년 5월 16일 월요일

알고리즘 공부에 대한 최백준님의 강의 자료

2016년 5월 6일 금요일

다시 풀어봐야 하는 문제 정리

알고리즘 공부 순서에 대한 글 소개

알고리즘을 어떤 순서로 공부해야 할 지 모르는 분들께

구독