[C++] 피보나치 수열과 황금비율
피보나치 수열은 수학에서 매우 유명하고 중요한 수열 중 하나.
Algorithm
재귀와 꼬리재귀(2) (Feat. ARC)
Stack frame 어떤 함수든 호출되는 순간 스택에 그 함수를 위한 영역(스택 프레임 stack frame)이 할당된다. 함수가 호출될 때마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다.
[Swift] 베스트앨범
문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
[Swift] Optimal Partition of String
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a sin...
[Swift] Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
[Swift] Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
[Swift] Remove Nth Node From End of List
Given the head of a linked list, remove the n$^t$$^h$ node from the end of the list and return its head.
[Swift] Quick 정렬
시간 복잡도 평균 : O(nlog(n)) 최악 : O(n^2)
[Swift] 윤년 계산
윤년 규칙 윤년 4로 나누어 떨어지는 해 1992, 1996, 2004, 2008, 2012, 2016… 4, 100, 400으로 나누어 떨어지는 해 1600년, 2000, 2400…
[Swift] Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same fo...
[Swift] 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
[Swift] 3Sum Closest
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
[Swift] Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
[Swift] Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the i$^{th}$ day.
[Swift] Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
[Swift] Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a s...
[Swift] 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
[Swift] String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
[Swift] (String)Super Reduced String
Reduce a string of lowercase characters in range ascii[‘a’..’z’]by doing a series of operations. In each operation, select a pair of adjacent letters that ma...
[Swift] Zigzag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for bet...
[Swift] Merge Intervals
Given an array of intervals where intervals[i] = [start$_i$, end$_i$], merge all overlapping intervals, and return an array of the non-overlapping intervals ...
[Swift] (String)Highest Value Palindrome
Palindromes are strings that read the same from the left or right, for example madam or 0110.
[Swift] 순열
Swift 순열은 직접 구현해야 한다. 알고리즘을 풀다 보면 자주 접하게 되는데 구현하려고 하면 매번 기억이 안 나는 마법에 빠져있다.
[Swift] Implement strStr()
Implement strStr.
0으로 나누기는 왜 안될까?
컴퓨터는 왜 0으로 나누기가 안될까? 0 ÷ 10 // NaN(Not a number) 5 ÷ 0 // NaN(Not a number)
[Swift] LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
[Swift] 2448 별 찍기 - 11
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
[Swift] 2447 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, ...
[Swift] 빠른 입출력(fread) - FileIO
기본 readLine()의 속도가 느려 백준에서 시간초과시 해결 가능하다.
[Swift] Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
[Swift] 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
[Swift] Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
[Swift] 두 정수 사이의 합
두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요. 예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다.
[Swift] 영어 끝말잇기
1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
[Swift] Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
[Swift] 수박수박수박수박수박수?
길이가 n이고, “수박수박수박수….”와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 “수박수박”을 리턴하고 3이라면 “수박수”를 리턴하면 됩니다.
[Swift] Valid Parentheses
Valid Parentheses
재귀와 꼬리재귀(1)
리스트, 트리, 그래프 등등의 모든 데이터 구조는 리커시브 하게 정의되며, 그래프도 정의에 리스트가 사용된다. 이렇게 정의된 객체를 효율적으로 다루기 위해선 어떤 알고리즘이 효율적일까?
Divide and conquer
분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.
DFS, BFS
그래프를 탐색하는 방법
Temp 변수를 사용하지 않고 Swap 하기
결론 : Temp 를 쓰자.
1 부터 n 까지의 합
1 부터 n 까지의 합
삽입 정렬
정렬할때 알맞은 자리를 찾아 삽입을 하기 때문에 삽입 정렬이다. 선택 정렬 과 달리 삽입 정렬은 최선의 경우, 즉 리스트가 이미 정렬 돼 있을때, O(n) 입니다. 정렬된 리스트에 삽입할때에는 매우 효율적입니다. 그러나 평균의 및 최악의 경우에는 O(n^2) 이기 때문에 무작위로...
선택 정렬
i 비교 횟수 1 n-1 2 n-2 3 n-3
버블 정렬
정렬 알고리즘을 직접 구현할 일은 거의 없겠지만 각각의 차이와 장단점에 대해 알아둘 필요가 있습니다. 각 알고리즘 마다 장점과 단점이 있고, 모든 경우에 대해 최선의 결과를 내는 알고리즘은 없습니다.