Swift, Python 둘다 준비해서 코드가 섞여있습니다.
Swift
✅ 시간초과가 발생할 경우, 아래를 살펴보자.
1) 고차함수를 많이 사용하지는 않았는가? 반복문 안에 고차함수가 들어가있지는 않은가?
2) 배열 대신 튜플을 사용할 수 있는가?
3) 수의 범위가 큰데 반복문을 2-3개씩 돌린다거나 하지는 않는가? -> 시간복잡도 확인
4) 백준이고, 위 문제 모두 아니고 알고리즘이 맞는것 같은데 시간초과가 난다..? 하면 백준 특유의 시간초과 문제일 수 있음.
- 이럴땐 FileIO 클래스를 사용하자. (라이노님 FileIO 클래스 외에도 더 빠른 FileIO가 있다고 함)
-> 하지만 백준에서만 해당 파일을 사용할 일이 있고 코딩테스트에서는 쓸일이 없어서 .. 그냥 파이썬 코드 그대로 옮겨보고 맞는지 체크하고 있다.
- 혹은 인자를 참조 인자(inout, &)로 넘기는게 더 빠르므로, 이 방법으로 풀 수 있는지도 고려해보자.
5) 형변환은 시간이 오래걸린다.
✅ 조건문보다 삼항 연산자가 조금 더 시간이 빠른것같다. (이것때문에 시간초과가 해결된 경험이 있음..)
Python
✅ 재귀함수를 돌렸는데 런타임 에러나 recursion error가 뜬다면, sys.setrecursionlimit(10**6) 를 맨 위에 써주자.
(재귀의 limit을 늘리는 메소드임)
공통
✅ core dumped 에러가 뜨면? ( = 백준 런타임에러)
index가 범위를 벗어났거나, nil 인데 억지로 접근하려고 했거나, 수의 범위가 자료형의 범위를 넘어설 때, 자료형 변환 시 변환을 할 수 없을 때, 0으로 나눈다거나 할 때
✅ 소수를 다루는 문제의 경우, 컴퓨터가 부동소수점으로 인해 실수를 정확히 표현하지 못할 수 있으니 이때는 round를 통해 반올림해주자.
✅ 인덱스가 범위를 넘어가지 않게 하려면, 나머지(%) 연산을 활용한다. (예를들어 26까지인데 27을 넘어간다고 하면 26으로 나누면 1이니까 절대 26를 초과하지 않음)
✅ 데이터의 범위가 큰데(입력크기가 큰데) 탐색을 해야한다면 딕셔너리나 세트를 활용하자. (배열은 O(n)인데 해시는 O(1)임)
알아두면 좋을 사항이나 코드
문자열
✅ 애너그램 판별 (순서를 바꿔서 다른 문자로 만들 수 있는지)
두 문자열을 정렬한 다음, 정렬한 문자열이 서로 같으면 애너그램, 아니면 애너그램이 아니다.
✅ 팰린드롬 X -> 팰린드롬 만들기
1) 각 문자의 개수가 홀수인 문자가 2개 이상이면? -> 팰린드롬 불가
2) 홀수인 문자열 중 하나는 중간에 와야하므로, mid 라는 변수에 저장
3) 짝수개인 문자를 자기 자신의 개수의 절반만큼 문자열에 더함
4) 다 더한 문자열에 중간 문자를 더하고, 다 더한 문자열의 역순을 더하면 팰린드롬 완성
from collections import Counter
str = input()
counter = Counter(str)
mid = ''
oddCount = 0
for k, v in list(counter.items()):
if v%2 != 0:
mid = k
oddCount += 1
if oddCount >= 2:
print("팰린드롬 불가")
exit(0)
result = ''
arr = sorted(counter.items())
for k, v in arr:
result += k * (v//2)
result += mid + result[::-1]
print(result)
✅ 아스키코드 (알파벳 순회) 활용 문제
현재 알파벳이 a나 A로부터 얼마나 떨어져있는지? -> (ord(현재 알파벳) - ord('a')/ord('A')) % 26
그만큼 떨어져있는 알파벳을 구하려면? -> 위에 ord('a') 혹은 ord('A') 추가
소문자와 대문자의 아스키코드는 서로 다르므로, 구분해서 사용해야함
n진수 ⭐⭐
✅ 정수(10진수) --> n진수 문자열로 변경하기
func radixChange(_ num: Int, _ radix: Int) -> String {
if num == 0 {
return "0"
}
//16진수라면 10부터는 A ~ F 알파벳 추가
// var code = ["A", "B", "C", "D", "E", "F"]
var nums: [String] = []
var num = num
var remain = 0
while num > 0 {
remain = num%radix // Python에서는 divmod라는 기능으로 몫과 나머지를 한번에 구할 수 있음
num /= radix
nums.append(String(remain)) // 변환하려는 진법으로 나눈 나머지를 차곡차곡 문자열로 저장햇다가
}
return Array(nums.reversed()).joined() // 뒤집어서 출력
}- Swift 진법 변경: String(num, radix: 진수) --> 2부터 36까지의 진수 변환 지원 , 시간초과 발생 시 위 코드 사용 필요
- Python 진법 변경: 2진수/bin(), 8진수/oct(), 16진수/hex() --> 0b나 0x 를 제거할 필요가 있고, 이외의 진수 변환 필요 시 위 코드 사용 필요
✅ n진수 문자열 --> 정수(10진수) 변환
- Swift --> Int(String, radix: n)!
- Python --> int(string, n)
기타
✅ 최대공약수, 최소 공배수
Swift
// 최대공약수
func GCD(_ a: Int, _ b: Int) -> Int {
let mod = a % b
return 0 == mod ? min(a, b) : GCD(b, mod)
}
// 최소공배수
func LCM(_ a: Int, _ b: Int) -> Int {
return a * b / GCD(a, b)
}
Python
import math
math.gcd(a, b)
math.lcm(a, b)
✅ 배열 회전
2차원 (시계방향 90도)
func rotation90right(_ array:[[Int]]) -> [[Int]] { //90도 회전 함수
let n = array.count
var new_array = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 0...n-1 {
for j in 0...n-1 {
new_array[j][n-i-1] = array[i][j]
}
}
return new_array
}1차원 (시계방향 / 반시계 방향) ⭐
- 인덱스 회전
-> 특히 주의할 점은 Swift는 음수 인덱스를 지원하지 않으므로, 반드시 음수일 경우 현재 리스트의 길이만큼 더하는 과정이 필요하다.
index = (index+move_count) % list.count //move_count 만큼 이동하기
if index < 0 { //swift는 음수 인덱스 처리를 못하므로 현재 q의 count만큼 더해줘야함
index += list.count
}- 배열 회전
if index > 0 { //오른쪽으로 index 만큼 밀기 (양수)
for _ in 0..<index - 1 {
q.insert(q.removeLast(), at: 0)
}
} else { //왼쪽으로 index만큼 밀기 (음수)
for _ in 0..<index * -1 {
q.append(q.removeFirst())
}
}
(Python)
1) deque의 rotate를 사용하여 회전 가능 (시간복잡도 O(n))
- 음수 : 반시계 방향 / 양수 : 시계방향 n번 회전
>>> from collections import deque
>>> test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> test = deque(test)
>>> test.rotate(2)
>>> result = list(test)
>>> result
[8, 9, 1, 2, 3, 4, 5, 6, 7]
2) (정수일때) 수학적으로 접근하여 배열 회전의 시간을 줄이는 코드 (O(1))
- 1234 --> 왼쪽 회전 --> 2341
n // 1000 + (n % 1000) * 10
- 1234 --> 오른쪽 회전 --> 4123
n // 10 + (n % 10) * 1000
✅ 제곱수 판별
func solution(_ n:Int) -> Int {
let root = Int(sqrt(Double(n))) //sqrt : 제곱근
return root * root == n ? 1:2
}
✅ 조합, 순열 ⭐
Swift
https://devyul.tistory.com/entry/Swift-%EC%A1%B0%ED%95%A9combination-%EC%88%9C%EC%97%B4permutation
Python
from itertools import combinations/combinations
list(combinations/permuations(data, 3)) // 리스트에서 3개를 선택하는 조합/순열
- 조합 응용 관련해서 좋은 문제 : https://www.acmicpc.net/problem/9375
✅ 소수 판별
1) 에라토스테네스의 체 -> 시간복잡도 O(NloglogN)) ⭐
import math
n = 1000
arr = [True] * (n+1) # 소수인지 여부를 담을 배열 -> 처음엔 다 소수로 가정
for i in range(2, int(math.sqrt(n))+1): # int(n**0.5) + 1
if arr[i]:
# i를 제외한 i의 모든 배수에 False 표시 (무언가의 배수이면 소수가 아님)
j = 2
while (i*j) <= n:
arr[i*j] = False
j += 1
for i in range(2, n+1): # 모든 소수 출력
if arr[i]: # 위 로직을 거쳐서 True인거라는거는 소수라는 의미임
print(i)단, 배열을 n 크기만큼 초기화해야해서 메모리가 많이 필요하여 n의 범위와 무관하게 사용할 시 메모리 초과 오류를 볼 수도 있다.
보통 N이 1,000,000 이내로 주어지는 경우에 사용
2) 일반 방법 -> 시간복잡도 O(X^1/2)
import math
def isPrimeNumber(x):
if n <= 1:
return False
elif n <= 3:
return True
else:
for i in range(2, int(math.sqrt(x)) + 1): # = for i in range(2, int(x**0.5) + 1)
if x % i == 0: # 자기가 아닌 수인데 나눠지는 수가 있다면, 소수가 아님
return False
return True
✅ 구간 합 빠르게 계산하기 ⭐
let n = 5
let data = [10, 20, 30, 40, 50]
var sum_value = 0
var prefix_sum = [0]
for i in data {
sum_value += i
prefix_sum.append(sum_value)
}
//구간 합 계산 -> 세번째 수부터 네번째 수까지
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])
+ 기타 도움되는 블로그 글들 (감사합니다!)
'⚙️ 알고리즘 > 코딩테스트 준비' 카테고리의 다른 글
| [알고리즘] 시간복잡도, 코딩테스트 알고리즘 요약 정리 (0) | 2023.04.03 |
|---|---|
| [Swift] 코딩테스트에 필요한 문법 총정리 (0) | 2023.01.06 |
| [Python] 문자열에서 문자, 숫자 분리하는법 (0) | 2021.04.19 |
| [Python 문법] 주요 라이브러리 정리 (0) | 2021.01.28 |
| [Python 문법] 함수, 입출력 (0) | 2021.01.20 |