Dreaming Dreaming

분류 전체보기

• DP - 점화식의 중요성(BOJ 11052, 16194)

  알고리즘 문제풀이/Java 2020. 4. 17. 18:28

  요새 다이나믹 프로그래밍(Dynamic Programming)을 공부 중인데, 한 번 새로운 깨달음을 얻을 때마다 문제가 슝슝 풀리는 게 기분이 좋다. 강의를 들으면서, 종만북에서 얻지 못할 좋은 사고의 흐름을 얻었는데, 같이 공유할까 한다(물론 종만북은 너무 어려워서 아직 제대로 보지도 못했다. 그래서 종만북에도 있을 수 있는 내용이다. 갓갓 종만북). 먼저, DP의 구조는 익히 들어서 알 것이다. 겹치는 부분 문제(Overlapping problem)와 최적 부분 구조(Optimal substructure)을 둘 다 만족해야 한다. 구조의 정의는 한글말이니 이해하겠는데, 문제에서 해당 정의를 찾아내는 게 나에겐 너무 어려웠다. 기본 개념을 문제에 적용을 못 시키고 있었달까?? 그렇게 혼자 헤매다가, ..

  Read More

• BOJ 2004, 1676 - 팩토리얼에 대한 접근

  알고리즘 문제풀이/Java 2020. 4. 15. 14:40

  https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 강의에서 배운 팩토리얼 문제에 대한 접근을 정리해볼까 한다. 1676번 문제를 먼저 살펴보자. 어떤 수 N이 주어졌을 때, 이 수의 팩토리얼의 값에서 0은 몇 개 일까? (잠시 고민해보자.) 다음과 같은 방법을 생각할 수 있을 것이다. 더보기 1. 팩토리얼 값을 계산한 뒤, 0..

  Read More

• BOJ 1918 후위표기식 - 스택

  알고리즘 문제풀이/Java 2020. 4. 14. 21:17

  문제 수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다. 이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사..

  Read More

• BOJ 17299 오등큰수 풀이를 통한 자료구조에 담을 정보에 대한 회고

  알고리즘 문제풀이/Java 2020. 4. 14. 00:14

  문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1..

  Read More

• 백준 17413번 단어뒤집기2 문제로 알아보는 논리 연산의 중요성

  알고리즘 문제풀이/Java 2020. 4. 13. 20:45

  문제 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

  Read More

• 백준 1406번 에디터

  알고리즘 문제풀이/Java 2020. 4. 12. 22:32

  문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무..

  Read More

• 백준 1874번 스택 수열 해설

  알고리즘 문제풀이/Java 2020. 4. 12. 21:05

  문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어..

  Read More

• 백준 1로 만들기

  알고리즘 문제풀이/Java 2020. 4. 12. 14:49

  문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 1 예제 입력 2 복사 10 예제 출력 2 복사 3 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 해설 다이나믹 프로그래밍(동적 계획법)을 활용해 풀 수 있는 문제이다. 처음엔 어떻게 접근해야할..

  Read More