&& 동일한 결과를 도출하더라도 입력값과 목적에 따라 적합한 자료구조 및 알고리즘을 선택하여 최적의 코드를 작성할 수 있다.&&
1. 회문을 판별하는 방법 : 문자열의 역순과 원 문자열이 동일한지를 확인하는 방법
회문 판별 접근법 1 : 역순의 문자열을 만들고 기존의 문자열과 같은지 확인 / 모든 문자가 일치할 시 True
# 회문 : 문자를 뒤집어도 동일한 문자열.
# 문자를 뒤집었을 때 같으면 True, 아니면 False를 return 하는 함수
def rev(word):
rev_word = word[::-1]
if word == rev_word:
return True
else:
return False
# 위 방식은 적어도 n번 이상의 연산이 이루어져아함. 뒤집어서 각각 비교 :O(N+N/2)
# 그런데 회문은 절반만 확인해도 동일한 것인지를 확인할 수 있다. :O(N/2) -> 아래 다른 방법
print(rev('abxxba')) # True
print(rev('abccbb')) # False
회문 판별 접근법2 : 문자열의 양 끝 인덱스 값에서 부터 중앙 방향으로 확인 / 일치하지 문자가 있을 시 False
# 회문이 맞는 경우 => 전체에 대해서 같음을 확인해야 한다.
# 회문이 아닌 경우 => 한번이라도 다르면 아닌것이다.
def func(word):
n = len(word)
left = 0 # index
right = n-1 # index
while right > left: # 오른쪽의 인덱스 값이 좌측보다 작거나 같아지면 확인 종료
if word[left] != word[right]:
return False # 동일하지 않은 문자가 발견됨과 동시에 False return
left += 1 # 문자열을 오른쪽과 왼쪽에서 중간으로 읽어오면서 동일한지 확인
right -= 1
return True # 일치하지 않는 값이 없을 때 True return
print(func("AABBBBAA")) # True
2. 이차원 리스트를 만드는 여러 방법들 : 이차원 배열을 생성하고 값을 변경하는 원리를 이해
방법1 : 4X4 배열을 생성 후, num의 초기값을 1로 설정하고 반복에 따라 1씩 늘려가며 리스트의 값을 변경.
n, m = 4, 4
mat = [[0]*n for _ in range(m)]
num = 1
for i in range(m):
for j in range(n):
mat[i][j] = num # 값을 하나씩 수정
num += 1 # 값의 증가 패턴
print(mat)
방법2: 4X4 배열을 생성 후,각 행의 첫번째 값을 기준으로 변화하는 값의 패턴 파악
mat2 = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
mat2[i][j] = 4 * i + j + 1 # 각 행의 [0]값들의 패턴 and 열의 증가 패턴
print(mat2)
방법3: 빈 리스트 생성 후, 각 행의 리스트를 패턴에 따라 생성한 후 빈 리스트에 추가.
mat3 = []
for num in range(4):
lst = list(range(4*num+1, 4*num+1+4))
mat3.append(lst)
print(mat3)
방법4: 4X4 배열을 생성 후, 4로 나눈 몫과 나머지로 인덱스와 요소의 값을 표현.
mat4 = [[0]*n for _ in range(m)]
for num in range(16):
# 인덱스 값의 증가 패턴
i = num // 4 # 0 1 2 3 / 열에서의 변화 : [[0][1][2][3]]
j = num % 4 # 0 1 2 3 / 행에서의 변화 : [0, 1, 2, 3]
mat4[i][j] = num + 1
print(mat4)
3. 정렬과 탐색 : 기본적인 정렬과 탐색을 통해 수를 원하는 순서대로 배열되도록 하는 방법
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 방법!
def solution(numbers):
# n_lst = sorted(numbers, reverse=True)
n_lst = list(map(str, numbers)) # 9 5 3 과 같이 맨 앞자리의 수를 비교하기 위해 문자로 변화
n_lst.sort(key=lambda x:x*3, reverse= True) # 서로 다른 자리수임에도 비교를 가능하게 함
return str(int("".join(n_lst))) # '00'과 같이 수의 형태가 아닌 것을 처리하기 위함
numbers = [3, 30, 34, 5, 9]
solution(numbers)
# output : "9534330"
4. 그리디 알고리즘: 각 단계 기준 최적을 선택 하고, 조건을 만족시키 않으면 선택 항목을 제외하고 다시 선택
(백준) 설탕배달 문제 : Nkg의 설탕을 5kg과 3kg 단위로 최소한의 개수가 되도록 묶는 방법
N = int(input())
cnt = N//5
answer = 0
while cnt >= 0:
# print("cnt:", cnt)
if N == 5*cnt + 3*((N-5*cnt)//3):
answer = cnt + ((N-5*cnt)//3)
break
else:
cnt -= 1
else: answer = -1
print(answer)
# 방법1 : 일단 5로 나눠보고, 5의 개수를 하나씩 줄여가며 3으로 나눈다.
N = int(input())
def sugar(N):
cnt = 0
for i in range(0,4+1): # 3의 최대 개수는 5개이다. / 3과 5의 최소공배수 = 15
new = N-3*i # 5의 개수가 가장 많은 것이 최적
if new >= 0 and new%5==0: # 조건에 맞지 않을 경우 3을 늘려가며 반복
cnt = i + new//5
# print(i, new//5)
return cnt
else:
return -1
print(sugar(N))
# 방법2: 일단 5로 나눠보고, 3의 개수를 하나씩 늘려가며 5로 나눈다.
5. 피보나치 수열을 푸는 여러가지 방법들 : Fibo(n) = Fibo(n-1)+Fibo(n-2)
