기본적인 논리게이트는 알고 있다는 가정하에 간단하게 표만 보고 넘어가자. AND Gate - 둘 다 1이어야 1, 곱셈이라고 생각하면 편하다. OR Gate - 하나만 1이어도 1, 덧셈이라고 생각하면 편하다. NOT Gate - 0, 1 뒤집기 NAND Gate(Not AND) - AND Gate 다음에 NOT Gate를 통과시킨 것이다. NOR Gate(Not OR) - OR Gate 다음에 NOT Gate를 통과시킨 것이다. XOR Gate(Exclusive OR) - 두 입력의 값이 같으면 0, 다르면 1이다. XNOR Gate(Exclusive NOR) - XOR Gate다음에 NOT Gate를 통과시킨 것이다. Buffer Gate - NOT 게이트와는 반대되는 개념으로 사용되는 논리회로이다...
이전 포스팅 더보기 Chapter 6. 정렬(1) 실전문제 1. 위에서 아래로 하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다. 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1
다음 포스팅 더보기 Chapter 6. 정렬(2) 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 굉장히 다양한데 이중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 알아보도록 하자. 오름차순을 내림차순으로, 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다. 우선 오름차순을 기준으로 알아보도록 하자. 선택 정렬 선택 정렬(Selection Sort) 알고리즘은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것이다. 원시적으로 매번 '가장 작은 것을 선택'한다는 것이다. 간단하게 보면 다음과 같다. 1. 가장 작은 데이터를 찾는다. 2. 맨 앞..
꼭 필요한 자료구조 기초 탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS/BFS가 대표적인 탐색 알고리즘이다. 자료구조(Data structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 스택과 큐가 대표적인 자료구조로 이들은 삽입(Push), 삭제(Pop)의 두 핵심적인 함수로 구성된다. 실제로 스택과 큐를 사용할 때는 삽입, 삭제 외에도 오버플로와 언더플로를 생각해야한다. 오버플로(Overflow) - 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입할 때 발생하는 것이다. 언더플로(Underflow) - 특정 자료구조에 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생하는 것이다. 스택(St..
1. Deque를 스택, 큐에 사용하기 from collections import deque # 만들기(최대길이를 정해둘 수 있다. 처음에 들어갈 때 넘어가면 왼쪽부터 짤린다. # 그다음부터는 평범하게 밀린다. 이 경우 insert에서 maxlen을 넘기면 에러가 뜬다.) haha=[3,2,5,6] dq=deque(haha, maxlen=3) # append, pop 없을때 pop 하면 에러 dq.pop() dq.popleft() dq.append('1') dq.appendleft('5') # 확장하기 dq.extend('lol') dq.extendleft('qeq') # 중간에 넣고 빼기(비추) dq[2]='n' # 리스트처럼 인덱싱 수정 #dq.insert(100, 'K') # 없으니까 맨 끝에 'K..
1. 리스트 컴프리헨션(List Comprehension) n = 4 m = 3 array1 = [[0] * m for _ in range(n)] # 4*3 크기의 0으로 채워진 2차원 리스트 초기화 array2 = [i for i in range(2) if i % 2 == 1] # 0~19까지의 수 중에서 홀수만 포함하는 리스트 array3 = [i * i for i in range(1,10)] # 1부터 9까지의 수의 제곱 값을 포함하는 리스 리스트 컴프리헨션은 리스트를 초기화하는 방법 중 하나로 조건문과 반복문을 넣는 방식으로 리스트를 초기화하는 것이다. 보통 2차원 리스트를 초기화할 때 사용한다. 2. 정렬(sort) array = [7,5,9,0,3,1,6,2,4,8] # result에 정렬된 ..
구현(implementation) 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 코딩 테스트에서는 알고리즘은 아니지만 이 구현이 중심이 되는 문제가 자주 출제된다. 구현 문제는 흔히 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 이런 구현하기 어려운 문제의 예시로는 아래와 같다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제 해당 책에서는 '완전 탐색', '시뮬레이션' 유형을 모두 이 '구현' 유형으로 묶어서 생각한다. 둘 다 구현의 핵심이 되는 경우가 많다. 완전 탐색(Brute Force) - ..
1. 아스키 타입 변환 65 ~ 90은 대문자 A ~ Z를 뜻하고, 97 ~ 122는 소문자 a ~ z를 뜻한다. a = 'a' b = 97 print(ord(a)) # 97 출력 print(chr(b)) # a 출력 ord 함수를 통해 문자를 아스키 코드로 변환할 수 있고, chr을 통해 아스키 코드를 문자로 변환할 수 있다.
1. 최대값, 최소값 구하기 item = [5, 13, 66, 12, 78, 1, 78] a = 3 b = 6 c = 9 minItem = min(item) # 78 maxItem = max(item) # 1 mini = min(a, b, c) # 3 maxi = max(a, b, c) # 9 list, tuple과 같은 것에서 min, max 함수를 통해 최대값, 최소값을 구할 수 있다. 값을 직접 넣어서 2개 이상의 값들 중 최대/최소를 구하는 것도 가능하다. 2. 최대값, 최소값 인덱스 구하기 item = [5, 13, 66, 12, 78, 1, 78] minIdx = item.index(min(item)) # 4 maxIdx = item.index(max(item)) # 5 최대/최소값이 있는 인..
1. 여러개의 데이터를 공백을 통해 입력받기 n, k=map(int, input().split()) a=list(map(int, input().split()) moonja = input().split() # 문자를 공백을 기준으로 받아서 리스트 형태로 저장 3 7 이런식으로 입력하면 각각이 n, k에 들어간다.(2개 이상도 가능) 리스트로 입력받고 싶으면 a와 같이 list로 wrapping 해주면 된다. 하나만 입력받을땐 그냥 n = int(input())해주면 되고 문자는 그냥 map 빼주면 된다. 2. 여러개의 데이터를 공백을 통해 입력받기(속도개선) import sys n, k=map(int, sys.stdin.readline().split()) a=list(map(int, sys.stdin.re..
