초보 기술블로그

순차 탐색

말 그대로 리스트나 배열의 앞에서부터 원하는 아이템을 찾는 방식

이진 탐색(Binary Search)

탐색 범위를 절반으로 줄이며 아이템을 찾는 방식.

배열 내부의 데이터가 정렬되어 있어야 사용 가능하다

시작점,끝점,중간점을 조절하며 아이템을 찾는다

초기 시작점은 배열의 첫 인덱스(0), 초기 끝점은 배열의 마지막 인덱스, 중간점은 항상 시작점과 끝점의 절반

아이템을 찾거나 배열에 아이템이 없다고 판단될 때까지 반복한다.

이진 탐색 트리(Binary Search Tree, BST)

트리 자료구조 중 특정한 특징을 가진 트리.

이진 탐색 트리의 특징

• 모든 노드는 2개 이하의 자식 노드를 가진다
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드를 만족시킨다

정렬이란?

= >데이터를 특정한 기준에 따라서 순서대로 나열하는 것

'알고리즘의 효율성'을 쉽게 이해할 수 있어 알고리즘의 초반 단계에서 공부함.

선택 정렬

가장 작은 데이터를 맨 앞의 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복

array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
	min_index = i //가장 작은 인덱스를 저장해 둠
    for j in range(i+1,len(array)): //가장 작은 인덱스 다음 번호부터 가장 작은 값을 찾음
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] // 두 개의 순서를 바꿈

print(array)
//선택정렬의 코드

선택 정렬은 N-1번 만큼 가장 작은 수를 찾기 위해 비교 연산을 진행하기 때문에,

N+(N-1)+(N-2)+...+2 ~= N(N+1)/2 정도의 시간 복잡도를 가지고 있다고 할 수 있고,

이를 가장 큰 차수만 차용하여 O(N^2)형태로 표현할 수 있다.

삽입 정렬

데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 방식

데이터가 적절한 위치에 들어가기 전에 그 앞까지는 데이터가 정렬되어있다고 가정함.

따라서 '데이터가 거의 정렬되어 있을 때' 가장 효율적임.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
	for j in range(i,0,-1):
    	if array[j] < array[j-1]:
        	array[j],array[j-1] = array[j-1], array[j]
        else:
        	break
 print(array)
 
 //삽입 정렬의 코드

삽입 정렬도 앞선 선택 정렬과 같이 반복문을 두개 연달아 사용했기 때문에

시간 복잡도는 O(N^2)형태라고 볼 수 있다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

'피벗'이라는 기준을 설정해 보통 정렬을 진행하는데, 가장 대표적인 '호어 분할' 방식에서는

리스트의 첫 번째 데이터를 피벗으로 설정해 정렬을 진행한다.

앞에서부터 피벗보다 큰 데이터와 작은 데이터의 위치를 변경하며 정렬을 진행한다.

만약 두 데이터의 위치가 서로 엇갈리면(큰 데이터가 뒤쪽, 작은 데이터가 앞쪽)

작은 데이터와 피벗의 위치를 변경하여 분할을 수행한다.

만약 분할된 리스트의 길이가 1인 경우에는 해당 리스트에 대해서 정렬을 중지한다.

피벗의 위치가 변경되면 이후 분할된 리스트에 대해 동일한 작업을 반복하여 정렬을 진행한다.

//가장 대표적으로 사용되는 직관적인 퀵 정렬 소스코드
def quick_sort(li, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and li[left] <= li[pivot]:
            left += 1
        while right > start and li[right] >= li[pivot]:
            right -= 1
        if left > right:
            li[right], li[pivot] = li[pivot], li[right]
        else:
            li[left], li[right] = li[right], li[left]
    quick_sort(li, start, right - 1)
    quick_sort(li, right + 1, end)

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]


quick_sort(array, 0, len(array) - 1)
print(array)

퀵 정렬은 N개의 데이터를 절반씩 나눈다고 도식화 시

O(Nlog(N))의 시간 복잡도를 지닌다.

계수 정렬

가장 큰 데이터와 가장 작은 데이터의 범위가 담기도록 리스트를 생성하고

데이터의 갯수만큼 해당 인덱스에 1을 더해 개수를 저장하고 이후 개수가 저장된 리스트의 앞에서부터 개수만큼 출력

따라서

"데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때"만 사용 가능하다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(li) + 1)
for i in range(len(array)):
	count[array[i]] += 1
for i in range(len(count)):
    for j in range(count[i]):
    	print(i, end = ' ')
//계수 정렬 소스코드

DFS/BFS를 알기 전 기본 지식

1. 스택(stack)

선입후출(FILO(First In Last Out))방식을 사용하는 자료구조.

Top이라는 포인터를 지정해 위치를 설정함.

• Push()
  스택에 원소를 추가한다.
• Pop()
  스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
• Top()
  스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.)
• IsEmpty()
  스택이 비어있다면 True, 비어있지 않으면 False를 반환한다

2.큐

후입선출(FIFO(First In First Out))방식을 사용하는 자료구조

Front포인터를 두어 제거 연산을, Rear 포인터를 두어 입력 연산을 담당함. 

• Push()
  큐에 원소를 추가한다.
• Pop()
  스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
• IsEmpty()
  큐가 비어있다면 True, 비어있지 않으면 False를 반환한다

3.재귀함수

말 그대로 자기 자신을 호출하는 함수를 의미한다.

가장 대표적인 예시인 팩토리얼을 재귀로 구현한 방식과 재귀를 이용하지 않은 방식으로 표현하면

//재귀를 이용한 방식
int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

//재귀를 이용하지 않은 방식
int factorial_nonrecursive(int n) {
	result = 1
    for i in range(1,n+1):
    	result *=i
    return result
}

재귀를 이용한 방식이 코드가 짧고 간편하다.

따라서, 재귀함수는 변수를 여럿 만들 필요가 없고 반복문을 사용하지 않아도 되기에 간결한 코드가 된다는 장점이 있으나연속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값을 stack에 저장하며 지연이 생긴다는 단점도 있다.

장점

단점

1. 성능: 지속적인 함수 호출로 호출 스택에 작업이 지속적으로 추가되어 성능 저하가 발생할 수 있다.

4. 그래프

노드와 간선으로 이루어진 자료구조를 말한다.

• 노드(Node) : 데이터를 저장하는 위치, 정점(Vertex)라고도 함.
• 간선(Edge) : 노드와 노드, 정점과 정점을 연결하는 선

보통 그래프를 표현하는 방식은 인접 행렬 방식과 인접 리스트 방식으로 나뉨

인접 행렬(Adjacency Matrix) 방식

2차원 배열로 그래프의 연결 관계를 표현하는 방식

연결이 되어있지 않은 노드끼리는 무한의 비용/0으로 가정함.

모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리가 낭비됨

인접 리스트(Adjacency List) 방식

'연결 리스트'라는 자료구조를 이용해 구현(C++/Java), 파이썬은 기본 리스트 라이브러리 사용 가능

리스트로 그래프의 연결 관계를 표현하는 방식

두 개의 노드가 연결되어있는지 확인하는 과정이 필요해 정보를 얻는 속도가 느림

DFS(Depth-First-Search)

말 그대로 깊이 우선 탐색 방식을 의미한다.

구현 시 대부분 재귀함수를 이용한다.

아래 그림과 동작 과정,코드를 통해 이를 이해해보자

일반적으로 DFS의 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

보통 코딩테스트/문제에서는 관행적으로 번호가 낮은 순으로 처리하기에 정렬의 필요성 존재.

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,visited)

dfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.

보통 DFS는 다음과 같은 상황에 사용한다.

• 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제(조합, 순열)
• 단순히 두 지점 간의 경로가 존재하는지 여부를 찾는 문제(조건문 넣으면 중간에 종료 가능) => 백트래킹

BFS(Breadth-First-Search)

말 그대로 너비 우선 탐색 방식을 의미한다.

보통 선입선출 방식인 큐 자료구조를 이용해서 구현한다.

아래 그림과 동작 과정,코드를 통해 이를 이해해보자

일반적으로 BFS의 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를
   모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

from collections import deque

def bfs(graph,start,visited):
	queue = deque([start])
    visited[start]=True
    while queue:
    	v = queue.popleft()
    	print(v, end=' ')
    	for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
        		visited[i]=True

graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
bfs(graph,1,visited)

bfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.

보통 BFS는 다음과 같은 상황에 사용한다.

•  최단경로 문제를 풀어야할때 => 제일 많이 사용
• 그래프의 깊이가 깊지 않을 경우

우리가 어떤 알고리즘이 더 나은 알고리즘인지 판단할 수 있는 척도는 무엇일까?

흔히 고려해 볼 수 있는 사항은 다음과 같다.

• 실행시간
• 코드의 길이
• 자주 발생하는 작업/연산의 수(소팅에서의 비교 연산)

그러나, 코드가 길다고 해서 실행 시간이 짧다는 보장이 없을 뿐더러, 실행시간의 경우에는 하드웨어의 차이에 따라

그 결과가 달라질 가능성이 높다고 볼 수 있다. 그렇다면, 우리는 어떤 기준을 가지고 이를 판단해야 할까.

시간복잡도

시간복잡도란, 이 중 필요한 단위연산을 기준으로 하는 복잡도를 의미하며,

알고리즘이 한 번 수행되는 동안 수행되는 단위연산의 수를 중심으로 비교한다.

이 단위연산은 해당 알고리즘에서 가장 많이, 필수적으로 수행되어야 하는 연산을 말한다.

보통 시간복잡도를 표현하기 위해 가장 많이 사용하는 표기법은 Big-O-Notation(빅오 표기법)이다.

Big-O-Notation

Big-O 표기법은 문제의 문제의 수행시간에 대한 함수의 표현식으로

문제의 크기에 비례하여 가장 빠르게 증가하는 연산에 관련된 함수로 표현하는 것을 의미한다.

이 함수를 "복잡도 함수"라고 부르며, 이 복잡도 함수가 작을수록 더 나은 알고리즘임을 의미하는 표기 방식이다.

보통 O(f(n))형태로 표현하며, 이 f(n)이 복잡도 함수이고,

연산수가 무한으로 증가한다면 최고차항의 수만 살펴보면 되기 때문에 보통 최고차항의 차수를 중심으로 판단한다.

구현이란?

구현은 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 을 의미한다.

단순히 문제를 보고 떠오르는 과정을 코드로 옮기는 피지컬적인 문제들이 이에 해당한다고 볼 수 있다.

책에서는

"완전 탐색" 유형 => 모든 경우의 수를 주저 없이 다 계산하는 유형

"시뮬레이션" 유형 => 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유횽

을 모두 구현 유형으로 묶어서 다루고 있다. 

보통 이 구현 문제들의 예시로는

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 2차원 배열에서의 이동, 회전 등 까다로운 문제

문제들과 같은 예시들이 존재한다.

주의사항

보통 int 자료형을 다룰 때 다음 범위보다 큰 수가 존재할 경우 이를 다룰 수 없기 때문에 고려하여 코드를 구현해야 한다.

파이썬에서는 프로그래머가 직접 자료형을 지정하는 경우가 적기 때문에 이런 사항을 고려하는 일이 적다.

접근 방법

문제는 긴 경우가 많으나 큰 사고력을 필요로 하지는 않기 때문에

천천히 문제를 읽고 이를 코드로 옮기면 되는 경우가 많다.

이해가 되지 않는 경우에는 A4용지를 사용해 코드를 구체화 시켜 보는 것도 방법

51

a,b=map(int,input().split())
print(a!=b)

52

a=int(input())
print(a!=0)

53

a=bool(int(input()))
print(a!=True)

54

a, b = input().split()
print(bool(int(a)) and bool(int(b)))

55

a, b = input().split()
print(bool(int(a)) or bool(int(b)))

56

a, b = input().split()
print(bool(int(a)) ^ bool(int(b)))

57

a, b = input().split()
print(bool(int(a)) == bool(int(b)))

58

a, b = input().split()
print(bool(int(a)) == bool(int(b)) == False)

59

print(~int(input()))

60

a, b =input().split()
print(int(a) & int(b))

61

a, b =input().split()
print(int(a) | int(b))

62

a, b =input().split()
print(int(a) ^ int(b))

63

a, b =input().split()
print(max(int(a),int(b)))

64

a, b, c =input().split()
print(min(int(a),int(b),int(c)))

65

a, b, c =input().split()
if int(a)%2==0:
    print(int(a))
if int(b)%2==0:
    print(int(b))
if int(c)%2==0:
    print(int(c))

66

a, b, c =input().split()
if int(a)%2==0:
    print("even")
else:
    print("odd")
if int(b)%2==0:
    print("even")
else:
    print("odd")
if int(c)%2==0:
    print("even")
else:
    print("odd")

67

a = int(input())
if a<=0 and a%2==0:
    print("A")
elif (a<=0):
    print("B")
elif (a%2==0):
    print("C")
else:
    print("D")

68

a = int(input())
if a>=90:
    print("A")
elif (a>=70):
    print("B")
elif (a>=40):
    print("C")
else:
    print("D")

69

a = input()
if a=="A":
    print("best!!!")
elif (a=="B"):
    print("good!!")
elif (a=="C"):
    print("run!")
elif (a=="D"):
    print("slowly~")
else:
    print("what?")

70

a = int(input())
if a<3 or a==12:
    print("winter")
elif a<6:
    print("spring")
elif a<9:
    print("summer")
else:
    print("fall")

71

while (True):
    a =int(input())
    if a!=0:
        print(a)
    else:
        break

72

a = int(input())
for b in range(a):
    print(a-b)

73

a = int(input())
for b in range(a):
    print(a-b-1)

74

a = ord(input())
b = ord('a')
while b<=a :
  print(chr(b), end=' ')
  b += 1

75

a = int(input())
for i in range(a+1):
    print(i)

76

a = int(input())
for i in range(a+1):
    print(i)

77

n = int(input())
s = 0
for i in range(1, n+1) :
  if i%2==0 :
    s += i
print(s)

78

a = "b"
while(True):
    a = input()
    if a=="q":
        print(a)
        break
    else:
        print(a)

79

a = int(input())
for i in range(a):
    if ((i*(i+1))//2>=a):
        print(i)
        break

80

a,b=input().split()
for i in range(int(a)):
    for j in range(int(b)):
        print(i+1,j+1,sep=" ")

81

a = int(input(),16)
for i in range(1, 16):
    print("%x".upper()%n,"*","%x".upper()%i, "=", "%x".upper()%(n*i), sep="")

82

n = list(map(str, range(1, int(input())+1)))
for i in n:
    if "3" in i or "6" in i or "9" in i:
        n[n.index(i)] = "X"  
print(" ".join(n))

83

a,b,c=input().split()
for i in range(int(a)):
    for j in range(int(b)):
        for k in range(int(c)):
            print(i,j,k,sep=" ")
print((i+1)*(j+1)*(k+1))

84

h,b,c,s = input().split()
print(format(h * b * c * s / 8 / 1024 / 1024, ".1f"), "MB")

85

w, h, b = map(int, input().split())
print(format(w * h * b / 8 / 1024 / 1024, ".2f"), "MB")

86

a = int(input())
for i in range(a+1):
    if ((i*(i+1))//2)>=a:
        print((i*(i+1))//2)
        break

87

a = int(input())
for i in range(1,a+1):
    if i%3==0:
        continue
    print(i,end=" ")

88

a,d,n = map(int,input().split())
print(a+d*(n-1))

89

a,r,n = map(int,input().split())
print(a*pow(r,(n-1)))

90

a,m,d,n= map(int,input().split())
result=a
for i in range(1,n):
    result=(result*m)+d
print(result)

91

import math
a,b,c= map(int,input().split())
print(math.lcm(a,b,c))

92

a = int(input())
a_list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]
b_list = []
for i in range(23):
    b_list.append(0)
c_list = list(map(int,input().split()))
for j in c_list:
    b_list[a_list.index(j)]+=1
for k in b_list:
    print(k,end=" ")

93

a = int(input())
c_list = list(map(int,input().split()))
c_list = c_list[::-1]
for k in c_list:
    print(k,end=" ")

94

a = int(input())
c_list = list(map(int,input().split()))
c_list.sort()
print(c_list[0])

95

d=[]
for i in range(20) :
  d.append([])
  for j in range(20) : 
    d[i].append(0)
a = int(input())
for i in range(a):
    k,l = input().split()
    d[int(k)-1][int(l)-1]=1
for i in range(19):
  if i>=1:
      print("")
  for j in range(19):
    print(d[i][j],end=" ")

96

answer = []
for _ in range(19):
    arr = input().split()
    answer.append(arr)

n = int(input())

for _ in range(n):
    x, y = map(int, input().split())
    for k in range(19):
        answer[k][y-1] = str(int(not int(answer[k][y-1])))
        answer[x-1][k] = str(int(not int(answer[x-1][k])))
        
for k in answer:
    print(" ".join(k))

97

a, b = map(int, input().split())
matrix = [["0" for _ in range(b)] for _ in range(a)]

for _ in range(int(input())):
    l, d, x, y = map(int, input().split())
    if d == 0:
        for i in range(y-1, y+l-1):
            matrix[x-1][i] = "1"
    else:
        for i in range(x-1, x+l-1):
            matrix[i][y-1] = "1"

for k in matrix:
    print(" ".join(k))

98

matrix = []
for _ in range(10):
    matrix.append(input().split())
    
x, y = 1, 1
while x <= 8 and y <= 8:
    if matrix[x][y] == "2":
        matrix[x][y] = "9"
        break
    matrix[x][y] = "9"
    if matrix[x][y+1] == "1" and matrix[x+1][y] == "1":
        break
    elif matrix[x][y+1] == "1":
        x += 1
    else:
        y += 1

for k in matrix:
    print(" ".join(k))

If문의 기본 구조

if 조건문:
	수행할 문장1
    	수행할 문장2
else:
	수행할 문장A
    	수행할 문장B

if 뒤에 조건문을 쓰고, 콜론(:)을 붙인 뒤 다음 문장은 들여쓰기를 한 후 입력한다.

들여쓰기는 Tap 한번이나, Spacebar 4번 중 1개를 선택해서 수행한다.

비교 연산자

비교 연산자는 다음과 같이 사용하며, 만약 식이 성립하면 True, 성립하지 않으면 False를 리턴한다.

리스트/튜플/문자열 안에 x가 존재하거나 존재하지 않으면 True/False를 리턴한다.

elif문의 기본 구조

if 조건문1:
	수행할문장1
    	수행할문장2
elif 조건문2:
	수행할문장3
    	수행할문장4
else:
	수행할문장A
    	수행할문장B

elif의 개수는 정해지지 않았으며, if문이 거짓일 때 다시 조건을 확인해서 만족하면 elif문 안의 문장을 수행한다.

while문의 기본 구조

while 조건문:
	수행할 문장1
	수행할 문장2
   	수행할 문장3

while문은 조건문이 참인 동안에 while문 아래에 속하는 문장들이 반복해서 수행한다.

Break와 Continue

Break문은 반복문에서 만나면 바로 반복문을 종료시키고,

Continue문은 반복문에서 만나면 반복문 처음으로 돌아가는 함수.

for문의 기본 구조

test_list = ['one','two','three']
for i in test_list:
	print(i)
    
one
two
three

집합이란?

중복을 허용하지 않으며, 순서가 없는 자료형이다.

= > 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다.

집합을 파이썬에서 정의하는 방법

s1 = set([1,2,3])
>>>s1
{1,2,3}
s2 = set("Hello")
s2
{'e','l','o','H'}

위와 같이 set()의 괄호 안에 리스트를 입력하여 만들거나 아래와 같이 문자열을 입력하여 정의한다.

집합의 연산

s1=set([1,2,3,4,5,6])
s2=set([4,5,6,7,8,9])

교집합

s1&s2
>>>{4,5,6}
s1.intersection(s2)
>>>{4,5,6}

'&' 기호를 이용하거나 intersection함수를 이용하여 교집합을 구한다

합집합

s1|s2
>>>{1,2,3,4,5,6,7,8,9}
s1.union(s2)
>>>{1,2,3,4,5,6,7,8,9}

'|'기호를 이용하거나 union함수를 이용하여 합집합을 구한다. 

차집합

s1-s2
>>>{1,2,3}
s1.difference(s2)
>>>{1,2,3}
s2-s1
>>>{8,9,7}
s2.difference(s1)
>>>{8,9,7}

'-'기호를 이용하거나 difference함수를 이용하여 차집합을 구한다.

집합 함수들

값 1개 추가하기(add)

>>>s1 = set([1,2,3])
>>>s1.add(4)
>>>s1
{1,2,3,4}

값 여러개 추가하기(update)

>>>s1 = set([1,2,3])
>>>s1.update([4,5,6])
>>>s1
{1,2,3,4,5,6}

특정 값 제거하기(remove)

>>>s1 = set([1,2,3])
>>>s1.remove(2)
>>>s1
{1,3}