soonmyeong / code-plus

code-plus 에 나온 문제 풀기

code-plus

수학 (chap 1)

• 나머지 연산
• 약수
• 최대공약수(GCD), 유클리드 호제법, 최소공배수 (LCM)
• 소수
  • 에라토스테네스의 체
  • 골드바흐의 추측

브루드포스

• 문제 범위에 해당하는 내용을 모두 구해보는 문제
• 재귀
• 순열
  • 기본형은 재귀함수로 구할 수 있음(visited 사용)
  • NP 로 구하려면 자바에선 제공하는 메서드가 없어서 구현해야 함
  • 비트마스크(TODO)

다이나믹 프로그래밍 (DP)

• 동적계획법이라 해석할 필요없음, DP 라는 용어를 처음 발표한 사람이 그냥 다이나믹이라는 단어가 멋있어서 썼다고함...

• top down

  • 커다른 문제를 점점 쪼개가면서 마지막에 리턴받아서 구함 (재귀로 구현)

• bottom up

  • 가장 작은 단위의 값을 가지고 점점 큰 문제를 풀어가면서 해결 (반복문)

• 문제 풀이 전략

  • 점화식 정의 하기 (처음엔 코드말고 한글로 써가며 연습)
  • 문제를 작게 만들 수 있는 방법을 찾기
  • top down 방식이나 bottom up 방식 중 구현하기 쉬운걸로 구현

그래프와 BFS

V : vertex (or Node, 정점)

E : edge (간선)

• 인접행렬

  • 공간 : V^2
  • 효율성 : V
  • 장점 : 임의의 두 정점 사이에 간선이 있는지 판단 O(1)
  • 단점 : 공간을 많이 필요로 한다.

• 인접리스트

  • 한점과 연결된 모든 간선
  • 공간 : E
  • 효율성 : O (정점의 차수만큼)
  • 장점 : 인접행렬보다 공간 적게 사용

• 간선리스트

  • 간선을 모두 저장하고 있는 리스트

• DFS 와 BFS

  • 한 정점에서 시작해서 연결된 모든 정점을 방문하는 탐색 방법
  • BFS 의 경우 큐에 정점을 집어 넣는 의미는 그 정점을 방문했다는 의미가 된다.
  • 최단거리, 최소비용 같은 단어가 있다면 보통 BFS 로 풀어야 한다.

시물레이션 구현