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

DFS 풀이

1. head, tail 을 둔다

2. push
   • head는 초기 추가된 노드를 계속 가르킴
   • tail이 가르키느 노드는, 새로 추가된 노드를 가르킴
   • tail은, 새로 추가된 노드를 가르킴
3. pop
   • head가 가르키는 노드가 가르키는 노드를 head가 가르킴

https://programmers.co.kr/learn/challenge_codes/144

풀이

1. 소문자이면

   • 현재 문자에서 ‘a’ 기준으로 얼만큼 떨어져 있는지 + n
   • 알파뱃 수 만큼 %
   • • a

2. 대문자이면

   • 소문자와 같은 방식

3. 공백

   • pass

정의

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

원리

• 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
• 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결

예제

• 막대기 자르기 ( 막대기를 적절히 잘라서 가장 가격이 높게 만들어야 함)

1
2

길이(i)   0  1  2  3  4   5   6   7   8   9  10
가격(Pi)  0  1  5  8  9  10  17  17  20  24  30

• 길이가 4인 막대기로 자를 때 얻을 수 있는 최대 가격 : 길이 2인 막대기 두 개로 자름. -> 5 + 5 = 10
• 길이가 6인 막대기 : 자르지 않고 그대로
• 길이가 n인 막대기의 최대 가격 = Rn = max(Pi + Rn-i) (i는 1부터 n)
• R1 = max(P1 + R0) =1
• R2 = max(P1 + R1, P2 + R0) = 5
• R3 = max(P1 + R2, P2 + R1, P3 + R0) = 8
• R4 = max(P1 + R3, P2 + R2, P3 + R1) = 10

–> R1, R2, R3… 가 반복적으로 나옴 . 메모제이션 사용. 이전에 계산한 값들 저장.

단점

https://programmers.co.kr/learn/challenge_codes/145

풀이

1. 리스트의 값 중 최대값을 찾음

2. n이 0이 될때 까지, 그 최대값 -1

3. 최종 제곱의 합을 출력

https://programmers.co.kr/learn/challenge_codes/152

풀이

1. 두 수의 최소 공배수

   • 두 수의 곱 / 두 수의 최대공약수

2. 두 수의 최대 공약수

   

3. 10 12 14 의 최소공배수

   • (10, 12) 의 최소공배수와 14의 최소공배수

개념

유클리드 알고리즘 (from 위키백과)

- 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘.
- 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), 
- a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
- 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 
- 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 
- 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

https://programmers.co.kr/learn/challenge_codes/153

풀이

1. 한 칸을 오르는 방법 : 1

2. 두 칸을 오르는 방법 : 2

3. 세 칸을 오르는 방법
   ​

    처음 한 칸 오르고 나머지 두 칸 오르는 방법 
   

   ​ + 처음 두 칸 오르고 나머지 한 칸 오르는 방법

4. 네 칸을 오르는 방법

    처음 한 칸 오르고 나머지 세 칸 오르는 방법
   

   ​ + 처음 두 칸 오르고 나머지 두 칸 오르는 방법

5. f(1) =1 / f(2) =2 / … / f(n+2) = f(n+1) + f(n)

개념

1. Dynamic Programming

   • 복잡한 문제를 간단한 문제로 나눠 푸는 방법.
   • 문제를 여러 하위 문제로 나눠 푼 다음, 그 결과를 이용하여 결합해 문제 해결

2. 피보나치 수열

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

풀이

1. ‘(‘ 이면 스택 push

2. ‘)’ 이면 스택 pop

3. 마지막에 스택 size 가 0 이면 VPS

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

풀이

1. 스택 두개 생성. lStack, rStack

2. 초기 입력 문자열 lStack에 모두 push

3. 명령어 대로

   • L : lStack의 top 문자를 rStack에 push
   • D : rStack의 top 문자를 lStack에 push
   • B : lStack pop
   • P $ : lStack에 $ push

4. 왼쪽 스택 문자 하나하나 pop해서 rStack에 push

5. rStack 하나하나 pop 해서 출력

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

풀이

• ‘(‘ 이면 stack에 push
• ‘)’ 이면 바로 전 문자 확인. 전 문자가
  • ‘(‘ 이면 stack에서 pop 하고 stack size 만큼 더해
    • 레이저이기 때문에, stack size만큼 짤림
  • ‘)’ 이면 1 더하고 stack pop
    • 막대기의 끝이기 때문, 한 개만큼 짤림

https://programmers.co.kr/learn/challenge_codes/170

풀이

1. 79, 80, 81, 82, 83 ~ 차례대로

2. 이진수로 바꿨을 때의 1 개수 count

3. 78을 이진수로 바꿨을 때의 1 개수와 같은지 확인

4. 1개수가 같은 순간의 숫자가 정답.

   • 1 개수가 같은, 가장 작은 숫자를 찾는 것이므로