정신차려 하프물범 정신차려 하프물범

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 문제 풀이 첫 번째 '-' 이전의 값은 더하고, 그 이후의 값은 모두 빼준다. '-', '+' 를 기준으로 나누고, '-'의 위치를 기준으로 숫자들의 합을 주해주면 되기 때문에 필요하기 때문에 정규식(re)이 필요했다. 정규식 정규식(re) 패턴 참고 사이트 []: 안에 들어간 문자를 기준으로 모두 구분한다. ex) '[AB]' : A또는 B를 기준으로 나눈다. (): 구분자..

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 프로그래밍에선 그래프, 트리 등 자료구조 안에서 탐색을 하는 문제를 많이 다룬다. 대표적인 탐색 알고리즘: DFS, BFS 필요한 자료구조 기초 DFS, BFS 를 이해하기 위해선 스택, 재귀함수, 큐에 대해 알아야한다. 스택, 큐, 재귀함수 스택 선입후출(FILO)/후입선출(LIFO)의 구조 파이썬에서 스택을 이용할 땐 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append(), pop() 메서드 이용. 큐 선입선출(FIFO) 구조 파이썬에서 큐를 구현할 땐 collections 모듈에서 제공하는 deque 자료구조를 사용. deque란 스택, 큐의 장점을 모두 채택한 구조인데, 데이터를 넣고 빼는 속도가 일..

아이디어를 코드로 바꾸는 구현 구현(implementation) 이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어려운 구현문제는 어떤 유형인가? 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 파싱하는 문제 등 -> 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다. 그러므로 구현 문제일수록 파이썬이 빛을 발하는 언어이다. 예를 들면, N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야하는 문제를 만난다면 무작정 기능을 짜는 것 보다 파이썬의 itertools 와 같은 표준 라이브러리로 쉽게 해결 가능하다 1. 완전 탐색, 시뮬레이션 [이..

복잡도 알고리즘의 성능을 나타내는 척도 크게 아래 2가지를 의미하며, 둘은 trade-off 관계를 가진다. 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양 시간 복잡도 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 간단히 정의하면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 예로 아래 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간을 O(N) 으로 표기한다. array = [3, 5, 1, 2, 4] summary = 0 for x in array: summary += x print(summary) #15

브루트 포스(brute force) 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조(저장되는 자료의 전후관계가 1:1 )를 전체적으로 탐색하는 순차탐색, 비선형 구조(데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프)) 전체를 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) *너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊음 문제해결 방법 주어진 문제를 선형 구조로 구조화한다. 구..

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 그림의 경우, 11^{2}>120이므로 1..

1. AI : intelligent(지능적인) 행동을 할 수 있는 컴퓨터 software를 만드는 것. 2. Machine Learning - AI의 하위 분야 - 패턴 인식과 컴퓨터 학습 이론에 대한 분야 - 자동으로 데이터로부터 규칙을 배우는 프로그램을 만드는 것 Supervised Learing : 지도 학습은 훈련 데이터로부터 하나의 함수를 유추해내기 위한 기계 학습의 한 방법. - predictive approach(예측적 접근) - input에서 output으로 가는 것을 어떻게 맵핑하는지 배워야한다 - ex) classification(분류), regression(회귀) Unsupervised Learning - descriptive approach(기술적 접근) - data에서 intere..