몇 주 전에 기업 입사를 위한 코딩테스트를 응시한 적이 있다.총 3문제 중 2문제는 금방 풀어서 1 문제만 풀면 되는 상황이었다. 혼자 올솔에 대한 행복회로를 돌리면서 한 문제를 계속 고민했는데,아무리 생각해도 DP인데 DP에 대한 풀이가 익숙지 못해서 결국 풀지 못했다ㅠ그래서 시험이 끝나고 최대한 비슷한 문제를 열심히 찾았고이 문제가 비슷한 것 같아서 한 번 풀어보는 김에 블로그에 정리해보려고 한다. 📕 1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.progra..
오늘은 알고리즘 풀이에 가끔씩 사용되는 '구간 합 구하기'에 대해 다뤄보려고 한다. 구간 합을 구하는 아이디어 자체는 어렵지 않아서, 고등학교 때 수열 문제를 풀면서 가끔씩 사용하곤 했던 기억이 있다. 하지만 대학생 때는 경영학을 전공했기에 통계나 회계 관련 산식들을 제외하고는 수학을 사용할 일이 드물어서 간단한 수학 테크닉들을 모두 까먹었다. 그래서 알고리즘을 풀이할 때 수학적 사고를 꾸준히 하지 않은 탓에 구간합 구하기 등 예상외로 간단한 것들에 고전하는 경우가 생기곤 하는데 이번 기회를 계기로 다양한 수학적 아이디어를 기억 속에서 꺼내봐야겠다. 📕 1. 구간 합(Interval Sum) 구하기란? 연속적으로 수가 나열 된 배열이 존재할 때, 주어진 배열의 특정 구간 내 모든 요소의 합을 구하는 것...
📕 1. 글을 작성하는 이유 : 코테 준비를 위해 정렬 알고리즘을 풀이하다가 내가 생각한 정렬 방식대로 되지 않아서 알아보다가 정리해야겠다고 결심했음. 또한 빅데이터분석기사를 준비할 때도 파이썬이 주력 언어임에도 불구하고 하고 완벽하게 이해하고 사용하는 느낌이 들지 않아서 이번 기회에 한 번 깊게 파보려고 한다. 📕 2. 파이썬에서의 정렬 ( sort와 sorted ) : 파이썬에서 정렬하는 방법으로는 리스트를 제자리에서(in-place) 수정하는 내장 list.sort() 메서드와 이터러블로부터 새로운 정렬된 리스트를 만드는 sorted() 내장함수 2개가 존재함. sort와 sorted의 차이를 간략하게 설명하자면, sort는 리스트를 제자리에서 수정함. ( 즉, 원본을 조작하며 'None'을 반환함..
📕1. 슬라이딩 윈도우 알고리즘이란? • 투포인터와 유사한 알고리즘 ( 투포인터와 달리 '일정한 크기' ) • 슬라이딩 윈도우는 정렬되지 않아도 사용 가능함. 좌우 모두 움직이는 '투포인터'와 달리 슬라이딩 윈도우는 좌우 중 한 방향으로만 이동함. • 배열 또는 리스트와 같은 순차적 데이터 구조에서 일정한 크기의 "윈도우"를 움직여가며 특정 연산을 수행하는 기법. • 주어진 배열에서 연속된 서브 배열의 합, 최댓값, 최솟값 또는 특정 조건을 만족하는 부분 배열 등을 찾는 경우에 슬라이딩 윈도우 알고리즘이 유용하게 적용될 수 있음. • 슬라이딩 윈도우 알고리즘은 반복문을 통해 한 번만 배열을 탐색하므로 시간 복잡도는 O(n)이므로 전체 배열을 다시 계산하는 것보다 효율적인 시간 복잡도를 가짐. 📕2. 알고..
📕 1. 유클리드 호제법이란? • 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법. 호제법(互除法) 이란 말은 서로(互) 나누기(除 때문에 붙여진 이름. • 최대공약수(GCD)란 ? GCD(Greatest Common Divisor)라는 이름에서 알 수 있듯이 두 수 혹은 그 이상의 여러 수들의 공통인 약수 중 최대인 수. 쉽게 설명하면, 각 수들의 공약수 중 가장 큰 값. 📕 2. 유클리드 호제법의 원리 • 유클리드 호제법의 기본 원리는 다음과 같다. X, Y의 최대 공약수는 Y와 X를 Y로 나눈 나머지값의 최대공약수와 같다는 원리를 이용. X와 Y의 최대공약수 == Y와 (X%Y)의 최대공약수 위의 원리를 이용하여 X에는 Y를 대입하고, Y에는 (X%Y)를 반복적으로 대입하다보면 언젠가는 ..
📕 1. LCS (Longest Common Subsequence) 알고리즘이란? • 영어를 번역하면 최장 공통부분 문자열. • 여기서 Subsequence는 '연속되지 않은 부분 문자열'을 뜻함 • 예를 들어, 'ACAYKP' 와 'CAPCAK'라는 두 개의 문자열이 있음을 가정해 보자. ACAYKP CAPCAK 두 문자열의 LCS는 'ACAK', 즉 4개의 알파벳으로 이루어진 문자열임을 알 수 있다. 📕 2. 백준 9251번 - LCS 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예..
📕 에라토스테네스의 체 알고리즘이란? • 고대 수학자 에라토스테네스가 발견한 소수를 찾는 방법. • 소수란? 약수가 자기 자신과 1만 있는 숫자. • 숫자를 체로 걸러낸다고 해서 '에라토스테네스의 체'라고 불림. • 주로 많은 숫자들에 대해 소수인지 아닌지를 판별해서 구해야 할 경우에 사용됨. 📕 알고리즘 작동 원리 • 다음은 위키백과에 있는 GIF 파일이다. • 먼저, 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. ( 그림에서 회색 네모칸에 해당하는 부분 ) 위 그림에서는 2부터 120까지가 해당된다. • 위 그림의 경우, 2부터 120까지 나열되어있는데, 120은 11의 제곱인 121 보다 작으므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, ..
📕 투 포인터(Two Pointer) 알고리즘이란? • 투 포인터 알고리즘은 배열의 인덱스를 가리키는 두 개의 포인터를 설정하고, 이를 옮겨가면서 내가 원하는 값을 찾는 알고리즘. • 정렬되어있는 두 리스트의 합집합에도 사용됨. 📕 대표 예제 문제 - [ 특정한 합을 가지는 부분 연속 수열 찾기 ] • 어떤 숫자들의 리스트가 주어졌을 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제. • N개의 자연수로 구성된 수열이 있다고 가정할 때, 합이 M인 부분 연속 수열의 개수를 구하라 • 시작점( start ) 와 끝점 ( end ) 2개의 포인터를 설정한다. • 예를 들어, 주어진 숫자 배열에서 M이 5인 부분 연속 수열의 개수를 구하라 하면, 그림처럼 3개가 정답이 됨. < 구현 ..
