🌱 → 🌳

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 설계 방법 나의 방법 ps가 주어졌을 때 “(”면 stack에 넣고 “)”면 stack에서 빼주었음 “)”인데 stack에서 뺄 게 없으면 vps가 아닌거고, ps를 모두 돌고 나서도 (가 남아있어도 vps가 아님 다른 방법 꼭 stack을 이용하지 않더라도 sum = 0 이라고 선언 하여 구현할 수 있음 “(”면 sum +=1, “)” 이면 sum -=1 이런 식으..

https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net stack 자료 구조를 이용하여 구현: N=int(input()) for i in range(N): string=input() string+=" " stack=[] for j in string: if j!=" ": stack.append(j) else: while stack: print(stack.pop(), end='') print(' ', end='') - j 값이 공백이 아닐 때는 s..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net stack class를 정의하여 stack의 기능/명령을 구현함 sys를 쓰지 않으니 시간초과가 났음 import sys로 시간초과 해결 정답코드: import sys input = sys.stdin.readline class Stack: def __init__(self): self.data=[] def empty(self): if len(self.data) == 0: retur..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 정답: def hanoi(n,a,b,c): if n==1: print(a,c) else: hanoi(n-1,a,c,b) print(a,c) hanoi(n-1,b,a,c) n=int(input()) print(2**n-1) # 이동 횟수 hanoi(n,1,2,3) 풀이: 먼저 n-1개를 C를 이용해서 B로 옮기고 A에 남은 하나는 쉽게 C로 옮길 수 있음 B에 있는 n-1개를 A를 이용..

https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 정답코드 def recursion(s, l, r): global cnt cnt += 1 if(l >= r): return 1 elif(s[l] != s[r]): return 0 else: return recursion(s, l+1, r-1) def isPalindrome(s): return recursion(s, 0, len(s)-1) for _ in range(int(input())): cnt = 0 print(isPalindrome(input()..

다이나믹 프로그래밍( 동적 계획법) 다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 탑 다운(하향식) 보텀 업(상향식) 일반적으로 프로그래밍 분야에서 동적(dynamic)이란? 자료구조에서 동적 할당(dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미 반면 다이나믹 프로그래밍에서 ‘다이나믹’은 별 의미 없이 사용된 단어 다이나밍 프로그래밍의 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서..

탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색 동작 예시 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$ 에 비례함 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남음 2단계를 거치면 8개가량의 데이터만 남음 3단계를 거치면 4개가량의 데이터만 남음 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 $O(logN)$을 보장함 파이썬 이진 탐색 라이브러리 bis..

그래프 탐색 알고리즘: DFS/BFS 탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로 DFS/BFS가 존재 자료구조 스택(선입후출) 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 예시) 박스 쌓기 DFS method 정의 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] * 9 dfs(graph, 1, ..