CS

마침 스택을 보고 와서인지 문제를 보자마자 스택이 떠올랐다. 1. 스택이 비었다면 입력값을 추가한다. 2. 입력값과 스택의 마지막값이 같다면, 스택에 입력값을 추가한다. 3. 또한 스택의 마지막값이 )이고, 입력값이 (일때도 추가한다. 4. 스택에 남아있는 것이 없다면 YES, 남아있다면 NO를 출력하게 한다. n=int(input()) for _ in range(n): stack=[] inp=list(input()) for x in inp: if not stack: stack.append(x) else: pop=stack.pop() if pop==x or (pop==")" and x=="("): stack.append(pop) stack.append(x) if not stack: print("YES")..

사실 이 문제는 퀵정렬, 합병정렬이 아니다. 근데 왜 이런 태그를 붙여놨느냐? 내가 메모리 제한을 못보고 합병정렬로 풀었기 때문이다. 합병정렬 합병 정렬은 배열(리스트)을 크기가 1이 될 때까지 자르고, 정렬을 하며 붙여나가는 알고리즘이다. 합병정렬은 다음과 같이 구현된다. 1. 배열을 반으로 나눈다.(길이가 1이 될때까지) 2. 양 옆의 배열을 비교하며, 합병한다. 합병정렬은 어떻게 자료가 정렬되어 있던 상관없이 시간복잡도가 O(nlogn)이다. 대신 제자리 정렬이 안되고, 임시 배열이 필요하다는 단점이 있다. 하지만 연결리스트로 작성하면, 제자리 정렬도 가능하다고 한다. 아래는 합병정렬 알고리즘이다. def msort(l): if len(l)==1: return l else: mid=len(l)//2..

이녀석을 처음 만난 것은 1654번이다. 나는 평범하게 이 녀석의 모든 경우를 계산해서 해결하려고 했다. k,n=map(int,input().split()) a=[] res=[] for _ in range(k): a.append(int(input())) for y in range(1, min(a)+1): cnt=0 for x in a: cnt=cnt+x//y if(cnt>=n): res.append(y) print(max(res)) 결과는 시간초과. 그래서 찾다가 알게된 이진탐색. 아래는 개념이다. 이진탐색(Binary Search) 데이터가 정렬되어 있는 배열에서 특정 값을 찾아내는 알고리즘이다. 배열 중간의 값을 골리 찾는 값과 비교하고, 중간 값이 찾는 값보다 작으면 최소값을 중간값 +1로 바꾼다...

그들과의 첫 조우 - 백준 1260번 이번 문제, 푸는데 20시간은 걸린거 같다. 그만큼 몰랐던 개념이 많았던 문제고 그에따라 많은 개념을 익혔다. 일단 문제를 풀며 가장 난이도를 느낀 부분이 그래프의 구현이었다. 나는 애초에 그래프가 뭔지도 몰랐다. 그리고 스택과 큐 역시 전공수업을 들으며 대충은 개념을 알고 있었지만, 실제로 써본 것은 처음이었다. 1. 그래프 그래프란 정점과 간선으로 이뤄진 자료구조다. 정확하게는 정점사이의 관계를 나타낸 자료다. 자 이걸 어떻게 프로그램한테 설명할 것인가? 크게 두가지 방법으로 표현 할 수 있다. 1) 인접 행렬 정점의 수에 따라 n*n의 2차원 리스트를 생성한뒤, 그 내용을 0으로 채워넣는다. 그 후에 1,2라는 정점사이에 간선이 존재한다면 arr[1][2]=1,..

실버 2 찍었다. 근데 풀다보니까 더 이상 무지성 때려박기로는 안된다는 생각이 들어서 알고리즘을 공부하기로 했다. 1. 선택정렬 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 인덱스 값을 증가 시키며 인덱스 이후의 최소값과 값을 바꿔주는 방식이며, 반복문을 두번 사용하기 때문에 시간복잡도는 N(O^2)이다. 파이썬 코드(오름차순) arr=[2,5,3,1,8,7,6,9,4] for j in range(0,len(arr)): low=arr[j] for i in range(j,len(arr)): if low>=arr[i]: low=arr[i] index=i arr[index],arr[j]=arr[j],low print(arr) 자바스크립트 코드(오름차순) 2. 삽입 정렬 현재위치에서 이하의 배열을 비교, ..

지금까지 적은게 영 부실한거 같아서 다시 한번 정리해서 적으려고 한다. 무지성 노베이스 파이썬으로 6월 25일부터 시작했다. 오늘부로 9일차 아래는 문제로 쳐맞아가며 배운 소중한 내용들이다. 배운 점 1. map(적용시킬 함수, 적용할 요소들) 2. split() -> 공백을 기준으로 나눠주는 함수 응용 : 임의의 숫자 두개(공백기준으로 나눔) 입력 a,b=map(int, input().split() 3. 연산자들(** : 거듭제곱, /: 실수형 나누기 //: 정수형 나누기) 4. 파이썬에서 특수한 문자(",',\)를 입력할땐 \를 앞에 붙여야 한다. 5. int(입력, 진수) -> 몰라서 리스트로 받아서 공식써서 변환시키려고 했음 6. d=list() -> 빈 리스트 생성 7. print(내용, end..