🤖 옌지니어의 IT 기록 🤖

https://school.programmers.co.kr/learn/courses/30/lessons/42584

문제

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

소스 코드

# 1
def solution(prices):
    n = len(prices)
    answer = []

    for i in range(n):
        idx = 0
        for j in range(i+1,n):
            if prices[j] < prices[i]:   # 현재 주식가격보다 떨어진 경우
                idx = j                 # 떨어진 시점을 idx에 저장하고 종료
                break

        if idx==0:                      # 현재 주식가격에서 떨어지지 않은 경우
            answer.append(n-i-1)        # 전체 길이에서 현재 인덱스를 뺀 값
        else:
            answer.append(idx-i)        # 떨어진 시점에서 현재 인덱스를 뺸 값

    return(answer)

풀이 # 1

• 현재의 주식가격은 i번째에 있는 값이고 나머지 주식가격은 j번째에 있는 값
• 현재 주식가격과 나머지 주식가격을 비교해서 가격이 떨어지는 시점을 idx에 저장
  • 가격이 떨어졌다면 for문 빠져나오기
• idx가 0이면 가격이 떨어지지 않은 것이므로 전체길이에서 현재 주식가격의 인덱스 빼기
• idx가 0이 아니면 가격이 떨어진 시점이 idx이므로 떨어진 시점에서 현재 인덱스 빼기

# 2
def solution(prices):
    n = len(prices)
    answer = [0] * n     

    for i in range(n):
        for j in range(i+1, n):
            answer[i] += 1
            if prices[i] > prices[j]:   # 가격이 떨어진 경우
                break                   # for문 종료

    return answer

풀이 #2

• 주식가격 길이만큼의 리스트 생성
• 현재 주식가격은 i번째에 있는 값이고 나머지 주식가격은 j번째에 있는 값
• answer 리스트에 1을 더하고 가격이 떨어졌다면 for문을 종료
  • 가격이 떨어지지 않았다면 for문으로 돌면서 +1 연산을 진행

처음에는 문제 이해가 안됐었는데 단순하게 생각해보니 현재 인덱스 값과 나머지 인덱스 값을 비교해서 가격이 떨어지기 전까지 시간을 구하는 문제였다. 정확도와 효율성을 모두 테스트하는 문제라서 어렵게 생각했었는데 필요없는 연산을 지우고 주식가격이 떨어지는 순간까지만 연산을 진행하니 의외로 쉽게 풀 수 있었다.

https://school.programmers.co.kr/learn/courses/30/lessons/76502

문제

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다.
  예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다.
  예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• s의 길이는 1이상 1,000이하입니다.

입출력 예

소스 코드

def solution(s):
    answer = 0
    n = len(s)

    for i in range(n):
        stack = []  
        for j in range(n):
            # 문자열 회전
            c = s[(i+j)%n]

            # 열린괄호의 경우
            if c=="(" or c=="[" or c=="{":
                stack.append(c)
            # 닫힌괄호의 경우
            else:
                # 스택이 비어있다면 0을 추가하고 종료
                if len(stack)==0:
                    stack.append(0)
                    break
                # 스택의 가장 마지막을 확인하고 짝이 맞다면 제거
                elif c==")" and stack[-1]=="(":     
                    stack.pop()
                elif c=="]" and stack[-1]=="[":
                    stack.pop()
                elif c=="}" and stack[-1]=="{":
                    stack.pop()
                # 짝이 맞지 않은 경우 0을 추가하고 종료
                else:
                    stack.append(0)
                    break
        
        # 중간에 종료되지 않았다면 스택은 비어있으므로 +1
        if not stack:
            answer += 1

    return answer

풀이

• for문에 따라 괄호 문자열을 회전
• 문자열이 열린괄호인 경우 스택에 괄호를 추가
• 문자열이 닫힌괄호인 경우
  • 닫힌괄호이면서 스택이 비어있다면 앞에 열린괄호가 없는 것이므로 스택에 0을 추가하고 종료
  • 닫힌괄호와 스택에 마지막 문자와 짝 맞추기 (짝이 맞다면 제거)
  • 짝이 맞지 않다면 스택에 0을 추가하고 종료
• 중간에 종료되었다면 스택에 0이 있을 것이고 아니라면 스택이 비어있을 것이므로 answer + 1

문자열을 회전하면서 짝을 맞춰야하는 문제였다. 경우의 수를 나누어서 생각하는 것이 좀 어려웠다... 알고리즘 책에서 스택의 예시 문제로 나와있어서 스택으로 풀어야겠다고 생각할 수 있었는데 문제만 봤을 때는 스택을 떠올리기 힘들었을 것 같다.

https://www.acmicpc.net/problem/24263

(알고리즘 수업 문제는 시간 복잡도가 무엇인지 확인하고 풀어보기)

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

→ 코드1 이 21회 수행되고 알고리즘의 수행 시간이 n²에 비례한다.

소스 코드

# 문제 시각화
n = int(input())
sum = 0
count = 0

for i in range(1,n):
    for j in range(i+1,n+1):
        sum += (i * j)    # 코드 1
        count += 1
        print("{:^4}+({}*{})={:^4} ({:^2}번 수행)\t".format(sum-(i*j),i,j,sum,count), end="   ")
    print()

# 정답 코드
n = int(input())

print(int(n*(n-1)/2))
print(2)

풀이

• 첫 번째 for문은 총 n번 수행
• 두 번째 for문은 n-i번 수행
  • i=1인 경우, n-1번 수행
  • i=2인 경우, n-2번 수행
• 수행 횟수 공식을 첫 번째 줄에 출력
  • 첫 번째 for문이 수행된 횟수 n과 두 번째 for문이 수행된 횟수 n-i를 곱한 값 (중복을 제거하기 위해 2로 나누기)
• 위의 공식에서 최고차항의 차수인 2를 두 번째 줄에 출력
  • 시간 복잡도(=코드1의 수행횟수)는 n*(n-1)/2이므로 최고차항의 차수는 2

이전 포스팅과 마찬가지로 시간 복잡도에 대해 알면 쉽게 풀 수 있는 문제였다. 익숙한 언어로 for문이 총 몇 번 수행되는지를 시각화해보면 좋을 것 같다.

https://www.acmicpc.net/problem/24263

(알고리즘 수업 문제는 시간 복잡도가 무엇인지 확인하고 풀어보기)

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

→ 코드 1이 7회 수행되고 수행 시간이 n에 비례한다.

소스 코드

# 문제 시각화
n = int(input())
sum = 0

for i in range(1,n+1):
    sum += i    # 코드 1
    print(sum-i, "+", i, "=", sum, "\t", i,"번 수행")

# 정답 코드
n = int(input())

print(n)
print(1)

풀이

• 문제에서 코드1은 총 n번 수행
• 입력의 크기 n을 첫 번째 줄에 출력
• 최고차항의 차수인 1을 두 번째 줄에 출력
  • 시간 복잡도(=코드1의 수행횟수)는 n이므로 최고차항의 차수는 1

시간복잡도가 뭔지 몰랐을 때는 문제 이해가 아예 안됐는데 개념을 알고 나서 푸니까 쉽게 풀 수 있었다. 일단 문제의 내용을 시각화해서 코드가 총 몇 번 수행되는지 알면 쉽게 풀 수 있다!!!

https://www.acmicpc.net/problem/2745

문제

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

소스 코드

# 1
N,B = input().split()

idx = len(N) - 1
decimal_num = 0

for num in N:
    add_num = 0
    if num.isdigit():
        add_num = int(num) * (int(B)**idx)
    else:
        add_num = (ord(num)-55) * (int(B)**idx)
    decimal_num += add_num
    idx -= 1

print(decimal_num)

풀이 # 1

• 숫자를 N, 진법을 B에 저장
• 숫자의 길이에서 1을 뺀 값을 idx에 저장 (진법 계산 시 사용)
• N을 한 자리씩 돌면서 숫자인지 문자인지 확인
  • 숫자인 경우 해당 숫자에 idx 제곱을 add_num으로 사용
  • 문자인 경우 해당 문자의 아스키 코드 번호에서 55를 뺀 수에 idx 제곱을 add_num으로 사용
• decimal_num에 위에서 구한 수를 더하고 자릿수 idx에는 1을 뺴기

# 2
N,B = input().split()

N = N[::-1]
numbers = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
decimal_num = 0

for idx,num in enumerate(N):
    decimal_num += (int(B)**idx)*(numbers.index(num))

print(decimal_num)

풀이 # 2

• 숫자를 N, 진법을 B에 저장
• 숫자 N을 거꾸로 만들기 (진법 계산시에 앞에서부터 자릿값을 곱하기 위한 과정)
• 숫자와 문자를 numbers에 저장
• N을 한 자리씩 돌면서 값 더하기
  • (B진법의 idx 제곱) x (numbers에서 num의 인덱스 번호)

아스키코드 번호를 이용한 첫 번째 풀이로 풀었는데 다른 풀이를 찾아보니 대부분 두 번째 풀이로 푼 것 같다. 확인해보니 사용되는 메모리 크기와 시간은 똑같아서 편한 방법으로 풀면 될 듯 하다.

https://www.acmicpc.net/problem/2563

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

소스 코드

# 도화지
paper = [[0 for col in range(100)] for row in range(100)]

n = int(input())

for _ in range(n):
    x,y = map(int, input().split())

    temp_x = x
    temp_y = y

    # 색칠하기
    while temp_x < x + 10:
        for idx in range(10):
            paper[temp_x][temp_y+idx] += 1
        temp_x += 1

# 도화지를 돌면서 색칠되어 있으면 cnt+1
cnt = 0
for row in paper:
    for col in row:
        if col > 0:
            cnt += 1

print(cnt)

풀이

• 100 x 100 크기 도화지 2차원 리스트로 정의
• 색종이의 수를 n에 저장
• 색종이의 수만큼 색칠하는 과정을 반복
  • 색종이의 행 번호를 x, 열 번호를 y에 저장
  • 행 번호와 열 번호를 임시로 temp_x, temp_y에 저장
  • 색종이의 길이가 가로세로 10이므로 행열번호의 +10만큼을 색칠
• 도화지를 돌면서 값이 1보다 큰 경우에 cnt+1

처음에 도화지를 정의할 때 [[0]*100]*100으로 정의했었는데 원하는 대로 나오지 않아서 찾아보니 연산자 *를 이용하여 배열을 선언하면 단순하게 요소만 복사하는 얕은 복사(shallow copy)가 일어난다고 한다. 그래서 바라보는 객체는 동일하고 값을 변경할 경우에 다른 원소의 값도 변하는 현상이 발생하니 값을 변경하지 않는 경우에만 사용하는 것이 좋다고 한다. 선언 방식을 변경하니까 다행히 문제없이 정답을 구할 수 있었다!!