미정

문제 설명

문제를 풀기전, 최소공배수를 구하는 방법에 대해 알아보자.

간단한 예로 최소공배수를 구해보자.

def ex_gcd(a, b): 	# a=18, b=24라고 가정
    A = a
    B = b
    while b > 0:
        a , b = b, a % b
    gcd = a 	# 최대공약수
    return A*B // gcd

위의 예시는 최소공배수를 구하는 문제이다. 18과 24의 최소공배수를 구해보자.

밑의 그림과 같이 구하면 되고, 최소공배수는? 2*3*3*4를 해서 72가 나올 것이다.

또 하나, 최대공약수는 6이 나올 것이다.

규칙을 찾았는가?

바로 최소공배수는 최소공배수를 구할 두 수를 서로 곱하여 최대공약수로 나누면 최소공배수가 된다는 것이다.

즉, 18 과 24를 서로 곱하여 나온 수를 최대공약수(6)로 나누면 최소공배수(72)가 나온다.

본 문제에 대한 나의 풀이

def solution(arr):
    from math import gcd                           
    answer = arr[0]                                 
    for num in arr:                                
        answer = answer*num // gcd(answer, num)     
    return answer

1.  최대공약수를 구하는 gcd() 함수를 import 한다. ((gcd() 함수는 두 수의 최대공약수를 구해주는 함수))

2. answer을 arr[0]으로 초기화

3. 반복문을 처음부터 끝까지 돈다.

4. arr[0], arr[1])의 최소공배수를 구한 후 answer에 저장

5. 4번에서 구한 최소공배수, arr[2])의 최소공배수를 구한 후 answer에 저장

6. 모든 배열을 돌면서 최소공배수를 구하고, 저장하고 하는 방식을 진행 ((최소공배수 = (x*y) / gcd(x,y))

정리하자면 이렇다.

• 최소공배수를 계속해서 answer에 저장시켜 answer와 arr[index]를 통해 계속해서 최소공배수를 구해야 함
• gcd() 함수는 두 수의 최대공약수를 구해주는 함수
• // 연산자는 몫만 구하는 연산자

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

풀이

def solution(brown, yellow):

    answer = []
    yellow_x = 0
    yellow_y = 0
    for i in range(1, yellow+1) :
        if yellow % i == 0 :
            yellow_x = int(yellow/i)
            yellow_y = i
            if yellow_x*2 + yellow_y*2 + 4 == brown :            
                answer.append(yellow_x+2)
                answer.append(yellow_y+2) 
                return sorted(answer, reverse = True)
    return answer

노란 격자의 가로(yellow_x)와 세로(yellow_y)를 이용해서 위와 같은 코드로 해결할 수 있다.

1부터 노란색의 개수만큼 for문으로 반복하면서 노란색의 수가 i로 나누어 떨어지면 노란색의 가로는 노란색을 i로 나눈 몫이되고, i는 노란색의 세로가 된다.

이때 위에서 언급한 수식을 사용하여 answer 리스트에 yellow_x+2와 yellow_y+2를 넣어준다.

가로가 세로보다 크거나 같아야 하기 때문에 내림차순으로 정렬을 한 리스트가 반환되도록 했다.

다른사람 풀이

def solution(brown, yellow):
    n = (brown-4)//2
    for i in range(n):
        x, y = i, n-i
        if x*y == yellow:
            return [y+2, x+2]

갈색 공간의 4개의 꼭짓점을 빼고 반으로 나누면, 노란색 구역의 가로+세로가 나오게 되며, for문을 돌면서 가로 * 세로가 노란색이 될 때, 가로+2, 세로+2 가 정답이 된다.

def solution(brown, yellow):
    total = brown + yellow
    # 카펫의 가로길이가 세로길이보다 크거나 같기 때문에 큰수에서 작은수로 반복
    for weight in range(total, 2, -1):
        if total % weight == 0: # 카펫넓이에서 가로길이 탐색
            height = total // weight # 카펫넓이 / 가로길이를 통해 세로길이 탐색
            # 구해진 카펫의 길이에서 테두리길이(2)만큼 빼주고 면적을 구한뒤 yellow의 면적과 같다면 해당 값 return
            if yellow == (weight-2) * (height-2):
                return [weight, height]

카펫의 넓이 = brown + yellow = width x height
외부 사각형 갯수(brown) = 2w + 2h + 4
내부 사각형 갯수(yellow) = (x-2) * (y-2)

문제 설명

풀이

def solution(n, words):
    rs=[] # 나온 단어 확인할 리스트
    for i in words:
        if i in rs: #같은 단어를 말했을때
            break
        if len(rs)!=0 and (rs[-1][-1]!=i[0]): # 앞단어의 뒷부분과 일치하지 않은 단어를 말했을때
            break
        rs.append(i)
        
    if len(rs)==len(words): # 문제없이 진행됐을시
        return [0,0]
    return [(len(rs)%n)+1, (len(rs)//n)+1]

1. word를 저장할 rs을 생성한다. rs는 나온 단어를 확인할 리스트이다.

2. words를 탐색하며 현재 word가 rs에 없고, rs의 마지막 원소의 마지막 문자가 현재 word의 첫번째 문자와 같다면 rs에 추가한다.

3. 위 조건에 맞지 않는다면 잘못된 단어이므로, 현재 word의 인덱스를 사용하여 탈락자 번호와 순서를 알아낸다.

result[0] = (len(rs) % n) + 1

result[1] = (len(rs) // n + 1

위 코드를 짧게 줄여보았다.

def solution(n, words):
    for i in range(1,len(words)):
        if words[i] in words[:i] or words[i][0]!=words[i-1][-1]:
            return [(i%n)+1,(i//n)+1]
    return [0,0]

• return 값은 >> 번호 = (i%n)+1, 차례 = (i//n)+1 << 이다.
• 비교를 할 때 words[i][0] != words[i-1][-1] 을 하기 때문에 반복문 범위는 1~len(words)로 해야한다.(0~len(words)로 하면 안 됨)

다른 사람의 풀이

def solution(n, words):
    answer = [0,0]

    cnt = 0  # 탈락번호,차례 계산할 변수
    checks = []  # 나온 단어 확인할 리스트
    checks.append(words[0])
    for i in range(1, len(words)):  # 단어 순회하면서
        cnt += 1
        # 아직 안나온 단어이면서 & 앞 단어의 마지막 알파벳과 일치하면 checks 리스트에 넣음 (pass)
        if words[i] not in checks and list(words[i-1])[-1] == list(words[i])[0]:
            checks.append(words[i])
        else:  # (fail)
            answer[0] = cnt%n +1  # 탈락번호
            answer[1] = cnt//n +1  # 탈락차례
            break

    return answer

Python의 if in 문법

문제가 좀 길어서 당황 했지만, 의외로 이런 문제가 더 쉬운 경향이 있다.

* Stack(스택)

• 스택은 LIFO(Last - In - First - Out)로써 가장 나중에 들어온 자료가 가장 먼저 꺼내어진다라고 이해하면 쉽다.

1. 정의

• 스택은 데이터를 한 쪽 끝에서만 넣고 뺄 수 있는 자료 구조이다.
• 큐는 대표적으로 FIFO 정책을 사용하지만 스택은 LIFO(Last In First Out) 후입선출 정책을 사용한다.
• 즉 가장 나중에 쌓은 데이터를 가장 먼저 제거할 수 있다. 또한 단어 그대로 쌓아 올린다는 것을 뜻한다.
• 프링글스 과자를 생각하면 쉽다.

2. 스택의 장단점

• -장점 
  
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• -단점
  
  • 스택에 데이터를 쌓을 수 있는 최대 범위를 미리 정해놓아야한다.
  • 이로인해 저장 공간의 낭비가 발생할 수 있다.

3. 스택의 메서드

파이썬 리스트 기능에서 스택은 두 가지 메서드를 제공한다.

- append(push) : 데이터를 집어넣기

- pop : 데이터를 빼기

4. 스택의 쓰임

- 웹브라우저의 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기
- 실행 취소(undo)

* Python에서 Stack 구현하기

Python에서는 기본 클래스인 list를 통해 스택 자료구조를 쉽게 구현할수있다.

list pop / push 시간복잡도

** list를 이용하여 Stack 구현하기 - 1

stack - Init

list는 파이썬에서 자주 쓰이기 때문에 리스트 자료형 생성은 매우 익숙할거같다.

stack = [] # []

stack = [1,2,3] # [1,2,3]

stack - push

스택에 원소를 넣을 때에는 append 메소드를 이용해 리스트의 가장 마지막에 원소를 넣으실 수 있다.

stack = []
stack.append(4) # [4]
stack.append(2) # [4,2]

stack - pop

스택에 원소를 제거할 때는 pop 메소드를 이용하여 리스트의 가장 마지막 원소를 제거한다.

이때 pop메소드에 의해 제거된 원소를 리턴 받는다.

리스트의 pop(0) 연산은 O(n) 시간 복잡도를 가진다. 즉, 리스트의 첫 번째 요소를 제거하면, 나머지 모든 요소를 왼쪽으로 이동해야 하기 때문에 큐의 크기가 커질수록 성능이 저하된다.

stack = [1,2,3,4]
top = stack.pop() # stack [1,2,3]

print(top) # 4

stack - top

스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하여 찾을 수 있다.

stack = [1,2,3,4]
top = stack[-1]# 4 , stack [1,2,3,4]

print(top) # 4

** deque를 사용하여 스택 구현하기 - 2

from collections import deque

stack = deque()

# 스택에 요소 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)

print(stack)  # deque([1, 2, 3])

# 스택에서 맨 뒤의 요소 제거 (pop)
top_element = stack.pop()
print(top_element)  # 3
print(stack)  # deque([1, 2])

# 스택에서 맨 앞의 요소 제거 (popleft)
print(queue.popleft())  # 1
print(queue.popleft())  # 2
print(queue.popleft())  # 3

• append(): 스택의 맨 위에 요소를 추가한다.
• pop(): 스택의 맨 위에서 요소를 제거하고 반환한다.
• popleft() : 스택의 맨 앞의 요소를 제거하고 반환한다. O(1) 시간 복잡도를 가지며, 이는 리스트의 pop(0)보다 훨씬 효율적이다. 따라서 큐의 크기가 커져도 성능이 일정하게 유지된다.

문제 설명

나의 풀이

def solution(s):
    answer = 0
    s = list(s)
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)

    if len(stack) == 0:
        return 1  
    else:
        return 0

두 가지를 비교해서 같으면 pop, 아니면 남긴다는 말에 stack이 생각났다.

1. stack을 활용할 것. 이 문제는 스택을 이용해서 풀었다.
2. s에 들어있는 문자를 하나씩 뽑아 스택에 있는 문자랑 비교하고
3. 만약 같다면 스택에 있는 문자 pop
4. 만약 다르다면 s에 들어있는 문자를 스택에 넣기

stack을 사용하지 않고 while, for문으로 앞 뒤 값을 비교 후 replace() 함수를 사용하는 방식으로 처음에 풀었는데, 시간 초과문제가 발생한다. 문자열 길이가 1,000,000이하이기 때문에 너무 큰 배열이 들어온다면 그럴 수 밖에 없을 것이라고 생각되었다. 그러다 stack이 생각이 났고, stack을 활용해 쉽게 문제를 해결할 수 있었다.

문제 설명

def solution(n):
    c = bin(n).count('1')
    for m in range(n+1, 1000001):
        if bin(m).count('1') == c:
            return m

• 2진수를 구하는 함수는 bin()이다. https://eesko.tistory.com/150

문제 설명

나의 풀이

def solution(n):
    answer = [0,1]			# F(0)=0, F(1)=1
    for i in range(2,n+1):	
        answer.append((answer[i-1] + answer[i-2]) % 1234567)
    
    return answer[-1] # return answer[n]

• F(0)=0, F(1)=1
• F(n) = (F(n-1) + F(n-2)) % 1234567
• 마지막 결과를 return

(A+B) % C 와 (A % C + B %C) % C가 같다는 나머지 연산 법칙만 알면 쉽게 풀 수 있다.

다이나믹 프로그래밍은 작은것부터 시작해서 큰걸 알아내는 기법이기 때문에

여기에서는 f[0]와 f[1]을 먼저 구해두고 2부터는 f[i] = f[i-1] + f[i-2] 라는 식으로 반복문을 돌리면 된다.

다른사람 풀이

def solution(n):
    a,b = 0,1
    for i in range(n):
        a, b = b, (a+b)%1234567
    return a

문제 설명

나의 풀이

def solution(n):     
    count = 0
    for i in range(1, n+1):         
        sum = 0                     
        for j in range(i, n+1):    
            sum += j               
            if sum == n:           
                count += 1          
                break
            if sum > n:            
                break
    return count

• 우선 문제에서 "연속한 자연수들로 표현 하는 방법"은 더하기만 생각하면 된다.
• 연속된 숫자의 합이므로 하나의 값을 시작으로 다시 반복문을 실행시켜야 한다.
• 예시를 보면  `15=15`도 있기 때문에 n+1 까지 반복문 실행
• i값을 시작으로 반복문 실행
• i값부터 계속해서 값을 더해준다.
• 더한 값이(sum)이 n과 같다면 count +1, 아니면 break
• 더한 값(sum)이 n보다 크다면 계산할 필요가 없음. 계속해서 더해지는 값(sum)이 n보다 커지는 순간 break
•  

다른 사람의 풀이

def solution(n):
    answer = 0
    for i in range(1, n + 1):
        s = 0
        while s < n:
            s += i
            i += 1
        if s == n:
            answer += 1


    return answer