매일 매일 성장하는 섭섭군

KMP Algorithm KMP 알고리즘이란? KMP(Knuth-Morris-Pratt) 알고리즘은 어떤 문자열에서 특정 문자열을 찾고자 할때 유용한 알고리즘입니다. KMP 란 이름이 붙은 이유는 Knuth, Morris, Pratt 세사람이 함께 만들어냈기 때문이라 합니다. KMP 알고리즘을 살펴보기전에 어떤 문자열에서 특정 문자열을 찾고자 한다면 어떻게 해야할까? 단순히 두 문자열을 앞에서부터 차례대로 비교해 나아가면 된다. 효율적이진 않지만 매우 직관적이며 간단합니다. 단순 비교 알고리즘 원본문자열과 찾을 문자열은 다음과 같습니다. 원본 문자열 : "abcdef" 찾을 문자열 : "cd"찾을 문자열이 원본문자열에 있을지 판단하는 과정은 다음과 같이 진행됩니다. 쉽고 단순하게 찾을 수 있지만 O(M*..

정렬 (Sorting) 정렬은 가장 기초적이면서도 많이 사용하는 알고리즘 입니다. 이미 좋은 정렬 함수들이 많이 존재하고 있어서 직접 만들어서 사용한 경우는 적은 편 입니다. 가장 기초적인만큼 어떤 정렬 알고리즘이 있는지 알고 넘어가면 좋을 것 같습니다. 이번 포스팅에서는 기초적인 알고리즘 3가지를 알아보도록 하겠습니다. 선택정렬(Selection Sort) 버블정렬(Bubble Sort) 삽입정렬(Insertion Sort) 선택정렬 (Selection Sort) 선택정렬은 자리를 선택한 후 해당 자리에 올 요소를 집어넣는 경우입니다. 오름차순으로 정렬을 잰행한다면 첫번째 인덱스에는 가장 작은수를 찾아서 넣고, 두번째 인덱스도 두번째 인덱스부터 가장 작은 수를 찾아서 정렬합니다. 다음 그림을 보면 이해..

leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3419/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제요약 이번에 풀어볼 문제는Excel Sheet Column Number 라는 문제입니다. 문제를 해석해 보면 알파벳으..

영어공부도 할겸 알고리즘 문제를 LeetCode 에서도 풀어보기로 했다. 그 중 Leet Coding Challenge라는 것이 있어 매주 도전하면 좋을것 같다는 생각이 든다. 처음 풀어본 문제는 다소 쉬운 문제다. 해시를 구현하는 것인데 백준이나 프로그래머스 등에서 해시를 사용하여 문제를 푸는 것이 아닌 그냥 해시를 구현하라! 라는 문제이다. 문제는 다음과 같다. leetcode.com/explore/featured/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3410/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and..

이번에 풀어볼 문제는 백준 7453번인 합이 0인 네 정수라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주�� www.acmicpc.net 문제를 살펴보면 4개의 배열이 있고 각 배열의 원소를 하나씩 적출해내어 합을 0으로 만들면 되는 문제입니다. 필자는 처음 시도할때 조합을 이용하여 풀고자 했습니다. itertools 의 product 을 활용하면 각각의 배열에 있..

이번에 풀어볼 문제는 백준 18405번 경쟁적 전염이라는 문제이다. 문제는 다음과 같다. https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 www.acmicpc.net 문제를 요약하면 다음과 같다. N*N의 칸..

이번에 풀어볼 문제는 백준 1431번인 "시리얼 번호" 라는 문제입니다. 일단 문제부터 함께 살펴보도록 하겠습니다. https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다. www.acmicpc.net 정렬과 관련된 문제입니다. 문제에서 주어진 조건대로만 정렬해서 출력한다면 큰 어려움 없이 해결 할 수 있는 문제입니다. 저는 본 문제를 풀때 Python의 lambda 를 활용하여 문제를 풀었습니다, lambda는 파이썬에서 한번만..

이번 문제는 백준 10825 국영수 라는 문제입니다. 정렬 알고리즘에 분류된 문제로 여러개의 조건으로 정렬을 진해하는 것이 최종 목표입니다. 문제의 내용과 입출력은 다음과 같습니다. 문제를 보면 정렬을 해야 하는 조건이 4가지가 있는데요 간략하게 요약해보면 1. 국어점수 내림차순 2. 영어점수 오름차순 3. 수학점수 내림차순 4. 이름 오름차순 저는 이 문제를 python 의 lambda를 활용해서 정렬하였습니다. 학생정보가 들어갈 배열을 하나 생성한 다음에 입력들어온 순서대로 저장합니다. 2차원 배열의 형태로 만들어지게 되며 이를 위에 명시된 기준대로 정렬합니다. python 내에서 lambda 로 정렬 조건을 추가할 때 내림차순으로 정렬하고자 할때에는 - 를 붙이면 됩니다. 그렇다면 위의 조건은 다음..