전체 글68 chapter10 문자열탐색 10.1 문자열 탐색 알고리즘의 개요Ctrl+F : 탐색단축키본문 : 탐색 대상 문자열패턴 : 탐색어이동 : 탐색 위치 옮기기10.2 고지식한 탐색 알고리즘본문 길이가 n이고 패턴 길이가 k이면 인덱스 0~n-k까지 패턴단위로 한 칸 한 칸 옮겨서 탐색 해보는 것최악의 경우 NxM번의 비교 수행10.3 카프-라빈 알고리즘알고리즘의 핵심 : 해싱 10.3.1 카프-라빈 알고리즘의 동작 방식문자열 탐색을 위해 해시 함수를 이용한다. 패턴의 해시값과 본문 내의 하위 문자열의 해시값을 비교하는 방식연산 비용은 더 커보이는데 천재적인 영감은? 해시함수의 비용을 획기적으로 줄이는 방법 패턴의 길이 m = 4 본문 = S[0…3]인 해시값 H = S[0]x2^3 + S[1]x2^2 + S[2]x2^1 + S[3]x2.. 2023. 6. 9. 이것이 코딩테스트다 4일차 - BFS, DFS 1. 일단 자료구조 기초탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조중요한 자료구조스택 - DFS / python : list - append와 pop모두 맨 뒤가 기준이라(맨 뒤에 삽입, 맨 뒤 부터 출력)큐 - BFS / python : deque (list로 큐를 구현하면 시간복잡도가 높음 - pop이 원소를 꺼낸 후에 이동 함)중요한 함수재귀함수 - 컴퓨터 메모리 - 스택 자료구조 - 종료조건 반드시 명시 2. 탐색 알고리즘DFS동작 기본 - 재귀, 스택, 그리디조건에 맞는 인접노드의 인접노드 계속 방문, 방문처리, 스택에 쌓음. 방문할 노드가 없으면 최상단 노드를 스택에서 제거, 그 다음 노드의 인접노드 방문, 방문처리, 스.. 2023. 6. 7. 이것이 코딩테스트다 3일차 - 구현 1. 구현이란?머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정Problem -> Thingking -> Solution 사실 문제 해결 분야에서 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제‘를 의미한다. 피지컬이 좋다 : 프로그래밍 언어의 문법에 능숙하고 코드작성속도가 빠른 사람 따라서 구현은 피지컬을 요구하는 문제라고 할 수 있다. 구현하기 어려운 문제란?알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제특정 소수점 자리까지 출력해야 하는 문제문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 (파싱을 해야하는) 문제 등 파이썬으로 N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우를 구해야하는 문제는 어떻게 풀까.. 2023. 6. 7. 이것이 코딩테스트다 3일차 - 그리디 1. 그리디란?현재 상황에서 지금 당장 좋은 것만 고르는 방법 따라서 최적의 해가 나오지 않을 때가 많다 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 (정렬, 최단경로 등은 이미 알고리즘 사용법을 정확히 알아야 한다.) 최단경로 문제는 플로이드워셜 or 다익스트라를 이미 알고 있어야 한다 (다익스트라 알고리즘은 그리디 알고리즘으로 분류되긴 한다) 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓어서 단순 암기만으로는 안 된다 많은 유형을 풀어봐야 한다! 훈련! 창의력, 문제를 풀기위한 최소한의 아이디어를 떠올리는 능력을 요구한다. 1.1 문제가 이렇게 나오면 그리디를 고려하자단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀수 있을 때알게모르게 가장 큰 순서대로,.. 2023. 6. 2. 이것이 코딩테스트다 2일차 - 파이썬 문법 : 입출력, 라이브러리 입출력데이터를 입력받을 때는 문자열로 입력받는다.input()따라서 입력받은 데이터를 정수형 데이터로 처리하기 위해서는 정수로 바꾸는 int함수 사용int(input()) 여러 개의 데이터를 입력받을 때는 데이터가 공백으로 구분되는 경우가 많다 입력받은 문자열을 띄어쓰기로 구분하여 각각 정수 자료형의 데이터로 저장하는 코드의 사용빈도가 매우 높다list(map(int,input().split())) #입력받은 값을 공백기준으로 split하여 리스트 만듦 #map 함수로 리스트의 vlaue들을 int형으로 변환 #변환한 값들을 다시 list로 만듦 전형적인 소스코드n=int(input()) data=list(map(int,input().split())) # data.sort(reverse=True)등등 공.. 2023. 5. 31. 이것이 코딩테스트다 1일차 - 파이썬 문법 : 자료형과 함수 부록A2부 이론3부 문제 - 최소 3회이상 ADVICE책의 문제를 푼 다음 동일 유형의 문제 온라인 저지 사이트에서 풀어보기 if 그리디 풀었으면 그리디 다풀어보기(백준)책을 보는 동안에는 책에만 집중 (문제를 많이풀고 복기하는 방법)복기한 내용은 기록 -> 훌륭한 요약집문제해결에 대한 접근방식, 풀이방식을 기억 및 설명파이썬 문법자료형은 자동 무한 : INF, 최댓값이 있을 때는 예를들어 1e9(1,000,000,000)와 같이 설정 실수형의 연산에서는 정확한 값이 나오지 않을 수 있다. 메모리에 저장되는 값이 현실과 다름 보통 소숫점 다섯번째 자리에서 반올림한 값이 같으면 맞았다고 인정하기 때문에 a라는 변수가실수 이면answer = round(a,4) Return answer 거듭제곱 연산자 ** .. 2023. 5. 31. 이전 1 2 3 4 5 ··· 12 다음
