뚝딱햄 탈출기

접근 방식 2024.03.02 - [Algorithm & Data structure/이론] - Dynamic Programming : DP, 동적 계획법, 다이나믹 프로그래밍 Dynamic Programming : DP, 동적 계획법, 다이나믹 프로그래밍 다이나믹 프로그래밍? 다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. DP와 다르게 분할 정복은 동일한 문제를 다시 푼다. 예를 들어 피보나치 수열을 분할 정복 hyrmzz1.tistory.com 일단 하향식으로 코드를 작성해야겠다고 생각했다. 처음엔 메모이제이션을 위한 리스트를 아래 솔루션과는 다르게 별도로 만드려고 했는데 너무 복잡했다. 결국 1시간쯤 끄적이다 다른 분들의 솔루션을 보고 로직을 세웠다. 입력값을 담은 리스..

접근 방식 입력으로 주어진 M개의 수와 상근이가 가지고 있는 숫자 카드 중 일치하는 값이 있는지 순차적으로 확인한다. ❌ Solution 1 - 시간 초과 import sys n = int(sys.stdin.readline()) cards = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) num = list(map(int, sys.stdin.readline().split())) for i in num: if i in cards: print(1, end=" ") else: print(0, end=" ") 이 코드 내에서 시간이 오래 걸릴만한 부분은 if i in cards라고 생각했다. 찾아보니 리스트는 요소 하나하나를..

접근 방식 처음엔 커서를 하나의 문자열로 두고 편집기 명령어에 따라 이동시키려 했다. 알고리즘 분류가 스택인걸 먼저 확인하고 문제를 접했는데, 커서를 이동시키는 방식을 스택에 대입시키기가 쉽지 않아서 많은 고민을 했는데, 두개의 스택을 사용하면 된다는 아이디어를 접했다. 스택 유형의 문제를 많이 풀어보지 않은 나에겐 꽤나 센세이션 했다 두개의 스택을 만든다. 이를 왼쪽 스택과 오른쪽 스택이라고 가정했다. 두 스택 사이에 커서가 있다고 생각하자. 커서는 고정이 커서 대신 스택의 요소들이 움직인다. 커서는 초기에 문장의 맨 뒤에 위치하고 있다고 했으므로 왼쪽 스택에는 초기 문자열(입력값) 모두를 넣어두고, 오른쪽 스택은 비워둔다. ✅ Solution 1 import sys stack_l = list(sys...

❌ 접근 방식 교집합을 구한 후, A + B의 개수에서 2 * (A ∩ B의 개수)를 빼야겠다고 생각했다. 교집합을 구하기 위해 이중 for문을 사용해 A와 B에 중복되는 요소의 개수 즉 교집합의 개수를 구했다. ❌ Solution 1 - 시간 초과 import sys an, bn = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) b = list(map(int, sys.stdin.readline().split())) cnt = 0 for i in a: for j in b: if i == j: # 교집합 cnt += 1 print(an + bn - cnt * 2) 교집합을 구하는 연산자나 라이브러..