본문 바로가기

CS Study

 (29)
[자료구조] DFS & BFS 0. DFS, DFS 학습 전 알아야 할 것 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 파이썬에서도 2차원 리스트로 구현한다. 연결이 되어 있지 않은 경우에는 논리적으로 정답이 될 수 없는 큰 값 중 999999999 등의 값으로 초기화해서 사용한다. INF = 999999999 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0,7,5], [7,0,INF], [5,INF,0] ] 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인접 리스트는 연결 리스트를 사용하면 되는데, 연결 리스트의 경우 파이썬은 기본 자료형인 리스트 자료형이 append 등 메소드를 제공하기 때문에 단순히 2차원 리스..
[자료구조] 큐, 스택 자료 구조: 데이터를 표현하고 관리하고 처리하기 위한 구조이다. 그 중 스택과 큐는 자료구조의 기초 개념 ! 스택과 큐에서의 핵심 함수는 삽입(Push), 삭제(pop)이며 오버 플로와 언더 플로를 주의해야한다. 오버 플로: 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 찬 상태에서 삽입 연산 수행 언더 플로: 데이터가 들어 있지 않은 상태에서 삭제 연산 수행 1. 스택 first in first out 이다. 박스를 쌓았다가 내리는 상황을 생각하면된다. 파이썬에서는 스택을 이용할 때 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop()을 이용하면 된다. stack = [] stack.append(5) stack.append(4) stack.append(3) sta..
시뮬레이션 문제 풀이 1. 공 (백준 1547번) 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net n=int(input()) array=[1,2,3] for i in range(n): ninput=list(map(int,input().split())) a=array.index(ninput[0]) b=array.index(ninput[1]) array[a], array[b] = array[b], array[a] print(array[0]) 2. 만취한 상범 (백준 6359번) https://www.acmicpc.net/probl..
힙 정렬 힙정렬이란 ? 리스트나 배열을 먼저 최소힙이나 최대힙으로 바꾸고 원소들을 순서대로 정렬하는 방법이다. 최소힙은 최소값을 구할 때, 최대힙은 최대값을 구할 때 사용한다. 최대힙이란? 완전 이진 트리이면서, 부모노드는 자식 노드보다 크다. 삽입) 새 노드에 삽입이 되고 나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다. 부모 노드보다 값이 클 경우, 서로 교환하면서 위로 올라가는 과정을 반복 삭제) 힙의 루트에서 삭제한다. 그러면 루트가 비어있는 상태가 되고, 가장 마지막 노드를 루트 노드로 올린다. 이후 새로 올린 노드가 제자리를 찾아갈 수 있도록 연산을 반복한다. *완전 이진 트리 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다. 2. 최소힙이란? 완전 이진 트리이면서, 각 노드의 키 값이..
구현 문제풀이 1. 문자열 집합 ( 백준 14425번 ) 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 직접 작성한 코드) n,m=map(int,input().split()) array=[] array2=[] count=0 for i in range(n): nn=input() array.append(nn) for i in range(m): mm=input() if mm not in array: continue else: count+=1 print(count) 2. 그룹 단어 체커 (백준 13..
다이나믹 프로그래밍 문제 풀이 1. 피보나치 함수( 백준 1003번 ) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 참고 코드) n=int(input()) def fibo(x): if(x==0): return 0 if x==1 or x==2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] for i in range(n): d=[0]*42 a=int(input()) if(a==0): print(1,end=' ') else: print(fibo(a-1), end=' ') print(fibo(a)) ➡️ 처음에는 재귀를 이용하서 피보나치 수열을 구현..
이진 탐색 문제풀이 1. 수 찾기 (백준 1920 번) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 직접 작성한 코드) n=int(input()) array=list(map(int, input().split())) m=int(input()) targetlist=list(map(int,input().split())) array.sort() def binary_search(array, target,start,end): if start > end: return None mid =(s..
기타 문제풀이 1. 괄호 (백준 9012번) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 직접 작성한 코드) n=int(input()) for i in range(n): count1=0 count2=0 a=input() result='YES' for j in a: if j=='(': count1+=1 else: count2+=1 if (count2>count1): result='NO' if(count1!=count2): result='NO' print(result) 2. 제로 (백준 107..

티스토리툴바