코딩애벌레

import sys input = sys.stdin.readline K = int(input()) info = [] for i in range(6): info.append(list(map(int, input().split()))) if info[0][0] == 1: if info[1][0] == 3: if info[2][0] == 1: if info[3][0] == 3: print(K * (info[4][1] * info[5][1] - info[1][1] * info[2][1])) elif info[3][0] == 4: print(K * (info[3][1] * info[4][1] - info[0][1] * info[1][1])) elif info[2][0] == 2: if info[2][1] < inf..

완전탐색을 할 때 주로 쓰이는 파트이므로 꼭 알아야하므로 한번 더 리뷰하려고 한다. 물론 재귀를 사용하는 중요한 방법이고 중복순열과 일반 순열이 있으니 두개 다 알아보도록 하자. 순열(Permutation)이란? 서로 다른 N개에서, R개를 중복없이 순서를 고려하여 나열한 것 [경우의 수 = N * (N - 1) * (N - 2) ... (N - R + 1)] 예를들어 0, 1, 2 로 구성된 3장의 카드들이 여러장 존재하는데, 이 중 2장을 뽑아 순열을 나열해 보자. 그렇다면 해당하는 순열은 [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] 으로 총 6개임을 알 수 있다. 중복순열은 서로다른 N개에서 R개를 중복 허용, 순서를 고려하여 나열하는 것 [경우의 수 = N**R] 위와 같은 예..

알고리즘 풀면서 가장 많이하는 두가지 인 것 같다. 반복문을 사용하느냐, 함수의 재귀 호출을 사용하는가를 선택하는 것은 중요하다. 개인적을 재귀 호출을 잘 사용하지 못하다 보니 반복문을 사용하는데, 이렇게 되면 코드가 쓸 때 없이 길어지며 재귀를 사용하지 않고는 문제를 해결할 수 없는 문제가 생긴다. 재귀는 어려운 개념이지만, 간단하고 깔끔하게 함수식을 통해 풀 수 있다는 장점이있다. 가장 큰 단점으로 느껴지는 것은 함수 재귀 호출 시 디버깅이 어렵다는 단점이 있는 것 같다. (아직 안익숙해서 그런 것일지도..) 아무튼 중요하다보니 한번 이해하고 정리할 겸 짚어보려고 한다. 반복(Iteration) : 수행하는 작업이 완료될 때 까지 계속 반복한다 루프 (for, while 구조) 반복문은 코드를 n 번..

블로그 작성하다가 초기화 됐다.. 슬프다.. bit를 미루고 미루다가 부분집합 부분을 풀면서 내가 사용하는 방식이 시간초과가 자주 뜨길래 이제는 미룰때까지 미뤘다 생각하여 bit를 이용한 연산에 도전하려 한다. 잘하는 친구들 보면 이미 비트연산을 자유롭게 사용하던데(특히 코드에 시프트 연산자 >> 2 # 우측에서 2개가 제거된다 파이썬 코드로 Shift 연산자를 확인해보자. print(bin(0b1011 > 3)) # 0b101 num = 1 for i in range(5): print(bin(num), num, sep = ' : ') num = num

이제 그림이 많이 나올 예정이다.. PPT로 만드느라 시간은 많이 걸리지만 이해하기에는 굉장히 도움이 많이 되고 있고, 혹시나 문제가 있다면 수정 요청해주셨으면 한다! 트리 (Tree) : 아래의 조건을 만족하는 한 개 이상의 노드로 이루어진 유한 집합. (node가 한개여도 트리라고 부를 수 있다) 노드 중 최상위 노드를 루트(root) 나머지 노드들은 n(>= 0)개의 분리 집합 T1, ... TN으로 분리 가능 분리 집합들이 각각의 하나의 트리가 되며(재귀적 정의) root의 부 트리(subtree)라고 한다 노드(node) : 트리의 원소 (A, B, C, D, E, F, G, H, I, J, K) 간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 루트 노드(root node..

이전에 완전 탐색을 baby-gin을 통해 다룬 적이 있다. 대신 그때는 순열과 재귀를 제대로 배우지 않았기 때문에, 그리디 탐색을 이용해서만 해결했고, 이번에는 완전 탐색을 이용해서도 풀어볼 예정이다. 이외 다른 유형의 문제 2문제도 다뤄보려고 한다. Brute-Force 알고리즘 ( = 완전탐색) : 모든 가능한 경우를 시도해서 정답을 찾아내는 알고리즘 간단한 예시로는 좌물쇠 비밀번호가 있다. 0부터 9까지 3자리 숫자를 맞춰야 좌물쇠가 열리는데, 이때 반복문을 사용하여 모든 경우를 나열할 수 있고, 재귀를 이용한 중복순열을 통해서도 가능하다. for i in range(10): for j in range(10): for k in range(10): print(i, j, k) ''' 0 0 0 0 0..

이제부터 머리아플 구간이다. stack에서 심화된 알고리즘 기법인데, 시간 복잡도와 메모리를 크게 아낄 수 있는 방법이기 때문에 알고 있으면 많은 도움이 되는 기법이다. 음식을 할 줄 아는데, 맛있게 빠르게 만든다고 할까? 가보자 백트래킹 (Backtracking) : 해를 찾는 도중에 '막히면' = '해가 아니라면' 탐색을 멈추고 되돌아가서 다시 해를 탐색하는 기법이다. 최적화(optimization) 문제와 결정 (decision) 문제를 해결하는데 도움이된다. 결정문제 : 문제의 조건을 만족하는 해가 존재하는지 여부를 확인하는 문제 (True / False) 미로찾기 n-Queen Map coloring 부분 집합의 합 문제 등 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 ..

가장 처음 파이썬을 공부할 때 다른 친구들이 알고리즘 문제 풀고 있는것을 들었을때 무슨 전문용어마냥 'DFS로 푸는거야?' 이럴때부터 쫄아있던 단원이다. 굉장히 어려워보이는 단어처럼 보이지 않는가? 정답이다. 서론을 간단하게 풀자면 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 깊이 우선 탐색(DFS) 와 너비 우선 탐색 (Breadth First Search, BFS) 총 두가지 방법이 있으며 오늘은 DFS에 대해 알아볼 것이다. 깊이 우선 탐색(Depth First Search, DFS) : 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳(가장 깊은 곳)까지 깊이 탐색해 가다가 더이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으..

Recusion (재귀호출) : 필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조. 얼마전에도 간단하게 Factorial을 예시로 다룬적이 있다. https://codinglarva.tistory.com/21 에서 확인 할 수 있다. 간단하게 더 설명하자면, 일반적인 호출 방식보다 재귀 호출 방식을 사용해 메모리, 시간을 줄이고 가독성이 더 좋게 작성이 가능하다. 이번엔 코드로 살펴보자 # 재귀함수를 이용한 피보나치 구현 def fibo(n): if n = 2 and memo[n] == 0: memo[n] = fibo(n-1) + fibo(n-2) # 재귀호출 형태 확인 return memo[n] # memo에 저장할 데이터 리턴하여 자동으로 넣는다. n = int(input()) memo = ..

이제 시작이다.. 여기서 부터는 알면 알수록 많은 풀이법을 생각 해낼 수 있고, 시뮬레이션이나 시간 복잡도를 개선하는 방식들이 있기 때문에 알고리즘 문제를 푸는데 실질적으로 도움이 많이 될 형태들이다. 가보자고. 스택 (=Stack) : 데이터를 후입 선출 구조 (LIFO : Last In, First Out 구조)이며 가장 최근에 들어온 데이터가 가장 먼저 빠진다는 개념이다. 실생활 예시로는 설거지한 컵들을 정리할 때, 가장 위에 있는 컵이 가장 먼저 사용될 것이고, 마지막 맨 아래의 컵은 마지막에 사용된다고 생각하면 좋을 것 같다. 스택에 저장된 데이터들은 선형 구조(데이터 간의 관계가 1대1 관계)의 특성을 띄고있다 스택에 데이터를 삽입하거나 스택에서 데이터를 빼낼 수 있다 스택을 프로그램에서 사용..