소소한 코딩일지

무작위 퀴즈를 구현하는 과정에서 random 하게 문제를 섞어야 했다. random sort를 구현함에 있어서 처음에는 sort함수를 통해 다음과 같이 정렬하는 로직을 구상했었다. function shuffle(arr) { arr.sort((a, b) => Math.random() - Math.random()); } 하지만 이 정렬 방식에는 약간의 문제가 있다. 예를 들어 1, 2, 3이 담긴 배열을 정렬한다고 할 때 다음과 같은 결과가 나온다. let arr = [1, 2, 3]; function shuffle(arr) { arr.sort((a, b) => Math.random() - Math.random()); } // 나올 수 있는 경우의 수를 count한다. let count = { 123: 0,..

슬라이딩 윈도( Sliding Window) 알고리즘은 배열 또는 리스트의 부분 범위 내의 값에 대한 비교를 수행할 때 좋은 알고리즘이다. 슬라이딩 윈도우를 사용한 문제 Longest Substring Without Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 위 문제를 슬라이딩 코드 없이 풀었을 때는 다음과 같은 코드를 사용했고, class Solution: def lengthOfLongestSubstring(self..

오늘은 동적 계획법(Dynamic Programming)에 대해 정리하려고 합니다. 그리디 알고리즘(Greedy Algorithm) 코딩 문제를 풀다가 그리디 알고리즘(Greedy Algorithm) 정리가 필요할 거 같아서 정리하던 도중 동적 계획법(Dynamic Programming)에 대해서도 정리하면 좋을 것 같아 정리하려 합니다. 동적 계획법은 '큰 문제를 작은 문제로 나누어 푸는 방법' 입니다. 동적 계획법은 분할 정복(Divide and Conquer)과 문제를 작은 단위로 분해한다는 비슷한 점이 있습니다. (분할 정복은 문제를 나눌 수 없을 때까지 쪼갠 후 하나씩 처리하면서 결과를 합치는 알고리즘입니다.) 하지만 동적 계획법과 분할 정복의 가장 큰 차이점은 같은 연산을 중복하냐 안 하냐의 ..

백준 문제를 풀다가 정말 쉬운 문제인 줄 알고 제 방식대로 풀었다가... 계속 틀려서... https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 다른 분들 질문을 보니 카운팅 정렬, 계수 정렬을 사용해서 풀면 풀린다고 하셔서 인터넷 폭풍 검색으로 풀고 이 부분을 처음 접해서 블로그에 남겨놓으면 혹시 다른 분이나 이후에 도움이 될 것 같아 간략하게 정리하려 합니다. Counting sort라고 불리는 이유가 리스트 내 요소의 개수를 파악하여 정렬하기 때문입니다. 다음과..

안녕하세요! 학교에서 자바와 C, 파이썬을 배우기 시작하면서 알고리즘 공부도 반드시 해야할 것 같아 혼자 공부한 알고리즘도 같이 기록하려고 합니다! 알고리즘 중에서도 오늘은 재귀 알고리즘에 대해 정리하려 합니다. 재귀 ( Recursion ) 은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말합니다. 그럼 재귀 알고리즘은 어떠한 함수, 메소드가 실행될 때, 또 다시 자기 자신을 불러 연산을 수행하는 것을 말 하겠죠? 재귀 호출이라고도 많이 부른다고 합니다. 재귀 알고리즘을 사용할때 주의 해야할 것이 반복문을 다룰때 처럼 종료 조건이 있어야 합니다. 종료 조건이 없으면 무한히 자기 자신 호출하게되어 무한 루프에 빠지게 됩니다. 재귀 알고리즘의 가장 유명한 예제들 두 가지를 보겠습니다. 1. 팩토리얼 ..