도리의 Tech to Art

안녕하세요. 알고리즘을 공부하던 중, 퀵 정렬(Quick sort) 이 한 번에 이해가 가지 않아서, 원리를 파헤치는 글을 올리게 되었습니다!! 퀵 정렬 방식은 간단합니다. 1) pivot(기준)을 정한다.2) pivot의 제자리를 찾아준다. 이를 반복하는 것이 퀵 정렬입니다.퀵 정렬을 하는 방식은 여러 가지가 있지만 저는 제가 배운 호어 분할(Hoare Partition) 방식으로 설명하겠습니다. 예를 들어 1~5 의 숫자가 적힌 카드가 무작위로 나열되어있다고 해봅시다. 이를 오름차순으로 정렬하는 것이 우리의 목표입니다.????? 먼저 가장 첫 번째 카드의 원소를 pivot으로 정합니다.Pivot???? 그럼 뒤에 나열된 4장은 각각 Pivot의 카드에 적힌 수보다 작거나, 큰 수들일 것입니다. 5..

개발기록/알고리즘 2024. 11. 8. 20:42

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net # 몇 줄 들어올지 숫자를 입력받는다. n = int(input()) cnt = 0 # 한줄씩 읽는다. for i in range(n): s = input() li = [] # 한 문자씩 읽어나간다. for j in range(len(s)): if j == 0: li.append(s[j]) else: if s[j-1] == s[j]: pass else: li.app..

개발기록/알고리즘 2021. 1. 16. 00:18

www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net # 속성 : 숫자와 문자를 매칭 dial = {2:["A","B","C"], 3:["D","E","F"], 4:["G","H","I"], 5:["J","K","L"], 6:["M","N","O"], 7:["P","Q","R","S"], 8:["T","U","V"], 9:["W","X","Y","Z"]} # 속성 : 다이얼을 돌려야하는 횟수 sum = 0 # input값 for i in input(): # dial 딕셔너리를 차례로 훑으면서 해당 숫자를 찾는다. for j in dial: # 숫자..

개발기록/알고리즘 2021. 1. 13. 20:43

www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 www.acmicpc.net 우후후... 문장을 주면 이게 몇 개의 단어로 되어있는지를 묻는 문제다. 파이썬으로는 한줄로 풀린다! print(len(input().split())) python string method 중에 split을 사용하여 단어 리스트를 만든 후, 리스트의 길이를 프린트한다! python string - split() method 여기서 볼 수 있듯이 split 함수는 separator를 기준으로 string을 잘..

개발기록/알고리즘 2021. 1. 12. 16:42

www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 어제는 unity 프로젝트때문에 알고리즘을 하루 쉬었다. 지금 dp를 공부하고 있는데 단계별 문제풀이로 다시 돌아가서 풀어보기로 했다. 유니티 C# 을 배울 때, 주석을 먼저 달고 코딩을 하는데 오늘은 조금 단계들이 긴 것 같아서 한글로 먼저 풀어쓴 뒤 코딩을 해보았다. 역시 명확해진다!!!! 굿굿 글로 먼저 쓰고 코딩하는 거 다들 시도해보세요~ㅎㅎㅎㅎ # 먼저 대문자로 모두 바꾼다. word = input().upper() # 차례대로 검사하..

개발기록/알고리즘 2021. 1. 11. 22:22

www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 오늘은 DP의 기본인 피보나치 수를 풀어봤다. 전에 풀어봤던 건데 top-down, bottom-up의 두가지 방식으로 다시 풀어봤다. Top Down # TOP DOWN memo = {0:0, 1:1} def fibo(n): if n in memo: return memo[n] else: memo[n] = fibo(n-1) + fibo(n-2) return memo[n] prin..

개발기록/알고리즘 2021. 1. 9. 12:32

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기는 다이나믹 프로그래밍에서 아주 유명한 문제다. 옛날에 알고리즘 진짜 ㅇ도 모르던 시절에 도전했었는데 막 풀다가 실패했다가 다이나믹 프로그래밍을 공부하면서 다시 마주치게 되었다. 근데 어렵다...ㅎㅎ n = int(input()) memo = [0 for _ in range(n+1)] def makeone(n): for i in range(2, n+1): memo[i] = memo[i-1] + 1 if i % 2 == 0 and memo[i] > memo[i//2] + 1: memo[i] = memo[i//2] +..

개발기록/알고리즘 2021. 1. 8. 22:08

www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net nums = input().split() print(max(nums[0][::-1], nums[1][::-1])) 알게된 것 string[::-1] 을 하면 문자열을 inverse 시켜서 뱉어준다!

개발기록/알고리즘 2021. 1. 8. 21:36