BOJ 11404 플로이드

https://www.acmicpc.net/problem/11404

https://github.com/simjaemun2/BaekJoon/blob/4bf0ae92959236c131b54630b87312a8833a0e0a/BOJ11404/BOJ11404.cpp

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

그래프, 플로이드-마샬, 최단 경로

난이도 : MH

BOJ 2096 내려가기

https://www.acmicpc.net/problem/2096

https://github.com/simjaemun2/BaekJoon/blob/7e1e8fa7ca3f040ecabc41ea9954532166dc81ca/BOJ2096/BOJ2096.cpp

분류 : DP

난이도 : MH

문제 조건에서 메모리가 4MB밖에 되지 않으므로,

슬라이딩 기법 등 메모리를 적게 사용하는 방법을 이용한다.

재귀호출을 할 때, 메모이제이션을 이용하면

프로그램이 사용하는 메모리가 증가하지만,

밴복적인 함수 호출 시

재귀호출 횟수를 줄여 더 빠른 함수 값을 얻을 수 있다.

많은 함수형 프로그램들이 메모이제이션을 쉽게할 수 있도록 함수를 제공하지만(클로저, 그루비 : memoize 제공),

스칼라는 직접적으로 제공하지 않는다.

하지만, 다음과 같은 방법으로 memoize() 를 간단하게 구현할 수 있다.

def memoize[A, B](func: A => B) = new (A => B){
  val cache = scala.collection.mutable.Map[A, B]()
  def apply(x: A): B = cache.getOrElseUpdate(x, func(x))
}

def hashFunc = memoize(hash)

BOJ 6588 골드바흐의 추측

https://www.acmicpc.net/problem/6588

https://github.com/simjaemun2/BaekJoon/blob/bbb6bed5763440f079afa91844f0632558e8c30e/BOJ6588/BOJ6588.cpp

분류 : 소수 구하기, 에라토스테네스의 체

난이도 : MH

소수 배열을 만든 후, 3부터 답에 맞는지 확인한다.

BOJ 10472 십자뒤집기

https://www.acmicpc.net/problem/10472

https://github.com/simjaemun2/BaekJoon/blob/25337654f7dcfeac11526bf2ab6d0190897b6c15/BOJ10472/BOJ10472.cpp

분류 : BFS, Bit operation

난이도 : H

N이 3이기 때문에 별 지장이 업지만,

N이 많이 커질 경우를 대비하여 Bit operation으로 구현하였다.

보드의 맨 윗 배열만 버튼을 누르거나 안누르는 모든 경우의 수를 따지면, 총 2 ^ N 의 경우의 수가 나온다.

그 후 0번째 행의 i번째 열이 흑색(1) 일 경우, 1번째 행의 i번째 열을 누른다.

1번 째 행을 0번째 행의 색에 따라 눌러보았을 때, 0번째 행에 검은색이 남아 있는 경우는 답을 구할 수 없는 상태로 함수를 종료한다.

이 후, 마찬가지로 1번째 행의 남은 흑색을 이용해 2번째 행을 눌러본다.

그리고 1번째 행과 2번째 행이 모두 흑색이 없을 때, 저장한 카운트를 이용하여 최소 값을 구한다.

BOJ 11004 K번째 수

https://www.acmicpc.net/problem/11004

https://github.com/simjaemun2/BaekJoon/blob/afba3a503bef21b3c6a5cd5af645c2375f4e43ad/BOJ11004/BOJ11004.cpp

분류 : 정렬

난이도 : MH

nth_element()

- 1부터 n 번째 순위  수 까지 정렬

- 모든 범위의 배열을 정렬할 필요가 없을 때 까지 사용

이 문제는, 일반 정렬(N logN)을 사용해도 답을 구할 수 있다.

BOJ 1874 스택 수열

https://www.acmicpc.net/problem/1874

https://github.com/simjaemun2/BaekJoon/blob/ddca9cb6c5182a2621cd2c01829daedd8bab1c56/BOJ1874/BOJ18874.cpp

분류 : 스택

난이도 : MH

cnt = 스택에 push 한 값

cnt < input

-> 계속 push

스택.탑 != a

-> 답 없음

else

-> 팝, 다음 단계 계속

BOJ 2580 스도쿠

https://www.acmicpc.net/problem/2580

https://github.com/simjaemun2/BaekJoon/blob/65d5d2fed2ce00a8569dafb23cf6050b483aed2a/BOJ2580/BOJ2580.cpp

난이도 : MH

분로 : 백트래킹

벡터를 이용하여 풀어봣는데, 많이 느리다.

BOJ 2776 암기왕

https://www.acmicpc.net/problem/2776

https://github.com/simjaemun2/BaekJoon/blob/fe7c0e15451492f149b35b1689e597327144ce9a/BOJ2776/BOJ2776.cpp

분류 : 이진탐색

난이도 : MH

Int 범위를 hash 하여 풀려면, 512MB의 용량이 필요하여 문제의 조건에 위배된다.

배열에 넣은 후 정렬한 다음에 이진 탐색으로 해당 수가 있는지 확인하여 답을 구한다.

BOJ 2573 빙산

https://www.acmicpc.net/problem/2573

https://github.com/simjaemun2/BaekJoon/blob/338bf600517c49d83c7532013bd0957bcd04ed88/BOJ2573/BOJ2573.cpp

분류 : BFS, DFS

난이도 : MH

빙산이 떨어져 있는 경우를 DFS, 1시간이 지난 후 힝하가 녹는 것을 BFS나 큐로 처리한다.