SSAFY를 하며 본격적으로 공부를 시작하고 정리할 필요를 느끼며 벨로그에서는 파이썬을 사용한 알고리즘 공부를 정리해왔지만

이제 자바에 집중하기 위해...!

2022.07.25 새롭게 블로그를 시작하며

D3 10965번 제곱수 만들기(python)

문제

풀이과정

단순히 소인수 분해를 할 경우 시간 초과 발생, 최대 값인 $10^7$을 고려해야한다. 소수를 구해 소수로 나누고 더 이상 나눠질 수 없는 소수인지 판별하는 과정으로 연산횟수 줄이기

$10^7$의 제곱근까지의 소수를 구한다. 제곱근 이상의 수 중 소수로 더 이상 나눌 수 없으면 해당 수 역시 소수다.

소수를 구하기 위해 에라토스테네스의 체 알고리즘 사용

이미 제곱수인 경우 결과는 1 제곱수가 아닌 경우 동일한 소수로 나누는 횟수가 홀수인 경우 해당 소수를 곱하면 제곱 수가 된다.

소스코드

T = int(input())

# 소수 구하기
max_n = int((10 ** 7) ** 0.5)
array = [True for _ in range(max_n + 1)]

for i in range(2, int(max_n ** 0.5) + 1):
    if array[i]:
        j = 2
        while i * j <= max_n:
            array[i * j] = False
            j += 1

prime = []

for i in range(2, len(array)):
    if array[i]:
        prime.append(i)

result = []

for t in range(1, T + 1):
    n = int(input())
    answer = 1

    if n ** 0.5 != int(n ** 0.5):
        for p in prime:
            count = 0
            while n % p == 0:
                n //= p
                count += 1
            if count % 2 != 0:
                answer *= p
            if n == 1 or p > n:
                break
        if n > 1:
            answer *= n

    result.append(answer)

for t in range(1, T + 1):
    print("#{} {}".format(t, result[t - 1]))

D3 2814번 최장경로(python)

문제

풀이과정

재귀함수를 이용한 DFS 각각의 노드에서 DFS 수행, 사이클이 없는 경로가 이어지는 경우 경로의 길이(노드의 개수)를 카운트 경로 탐색시 파생되는 경로를 모두 탐색하기 위해 방문한 노드의 방문 여부를 False로 지정

소스코드

T = int(input())

for t in range(T):
    vertex, edge = map(int, input().split())
    graph = [[] for _ in range(vertex + 1)]

    for i in range(edge):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    result = 0

    for i in range(1, vertex + 1):
        visited = [False] * (vertex + 1)

        def dfs(v, count):
            global result
            visited[v] = True
            result = max(result, count)
            for x in graph[v]:
                if not visited[x]:
                    dfs(x, count+1)
                    visited[x] = False

        dfs(i, 1)

    print("#{} {}".format((t+1), result))

D3 1220번 [S/W 문제해결 기본] 5일차 - Magnetic(python)

문제

풀이과정

정해진 규칙에 따라 테이블 내에 더 이상의 이동이 불가할 경우(교착상태 도달)할 때 까지 정해진 규칙에 따라 이동해야 한다.

이동의 조건을 명시 이동이 발생할 경우 move = True 더 이상 이동이 발생하지 않을 경우 movep = False 이동 종료, 이후 교착 상태 확인

교착상태 확인 n극과 s극이 맞닿은 상태 n극과 s극이 맞닿은 상태의 개수 == 교착상태의 개수

소스코드

T = 10

for t in range(1, T+1):
    table_length = int(input())
    table = []

    for _ in range(table_length):
        table.append(list(map(int, input().split())))

    while True:
        move = False
        for i in range(table_length):
            for j in range(table_length):
                if table[i][j] == 1 and i == table_length-1: #n극이 아래로가서 떨어지는 경우
                    table[i][j] = 0
                    move = True
                if table[i][j] == 2 and i == 0: #s극이 위로가서 떨어지는 경우
                    table[i][j] = 0
                    move = True
                if table[i][j] == 1 and table[i+1][j] == 0: #n극이 아래로
                    table[i][j] = 0
                    table[i+1][j] = 1
                    move = True
                if table[i][j] == 2 and table[i-1][j] == 0: #s극이 위로
                    table[i][j] = 0
                    table[i-1][j] = 2
                    move = True

        if not move:
            break

    count = 0
    for i in range(table_length):
        for j in range(table_length-1):
            if table[j][i] == 1 and table[j+1][i] == 2:
                count += 1

    print("#{} {}".format(t, count))

D3 1216번 [S/W 문제해결 기본] 3일차 - 회문2(python)

문제

풀이과정

100 * 100 테이블에서 회문을 찾고 가장 길이가 긴 회문의 길이를 출력 가로(행)에서 회문 탐색 하나의 행에서 회문의 길이가 최대 100부터 1씩 감소하며 이어지는 문자열 검색 뒤에서 부터 탐색하기 때문에 기존의 회문이 발견되면 기존의 최대 길이와 비교후 다음 행으로

세로(열)에서 회문 탐색 하나의 열에서 회문의 길이 1부터 최대 100 까지 1씩 증가하며 이어지는 문자열 검색 회문이 발견되면 기존의 최대 길이와 비교 길이가 1인 경우부터 비교하기 때문에 하나의 행에서 최대 길이가 될때 까지 회문의 여부를 확인해야한다.

소스코드

for t in range(10):
    test_number = int(input())

    board = []

    for _ in range(100):
        board.append(input())

    row_max = 0
    for i in range(100):
        for j in range(100):
            for k in range(100-j):
                row_string = board[i][j:101-k]
                if row_string == row_string[::-1]:
                    row_max = max(row_max, len(row_string))
                    break

    col_max = 0
    for i in range(100):
        for j in range(100):
            col_string = ''
            for k in range(100-j):
                col_string += board[j+k][i]
                if col_string == col_string[::-1]:
                    col_max = max(col_max, len(col_string))

    result = max(row_max, col_max)

    print("#{} {}".format(test_number, result))

D1 2047번 신문 헤드라인(python)

문제

풀이과정

파이썬 정규식을 사용하지 않고 문자를 숫자로 ord() 숫자를 문자로 chr() 대문자 A의 경우 65 알파벳의 순서 + 65 chr(ord(char) - ord('a') + 65)

소스코드

string = input()

upper = ''
for char in string:
    if ord('a') <= ord(char) <= ord('z'):
        upper += chr(ord(char) - ord('a') + 65)
    else:
        upper += char
print(upper)

D3 2817번 부분 수열의 합(python)

문제

풀이과정

조합 combinations를 모두 구해 문제를 해결할 경우 시간 초과

재귀함수를 통해 완전 탐색 현재 인덱스에 해당하는 원소를 포함하는 경우, 그렇지 않은 경우 각각의 재귀함수 호출을 통해 확인

재귀함수의 종료 조건과 호출 형태 설계하기

소스코드

T = int(input())

result = []


def solve(idx, curr_sum):
    global count
    temp = curr_sum + seq[idx]

    if temp == k: #조건과 일치할 경우
        count += 1
        return

    if idx == n: #끝까지 탐색한 경우
        if temp == k:  # 조건과 일치할 경우
            count += 1
        return

    if temp > k: #정해진 k 보다 큰 경우 추가되는 조합을 찾을 필요가 없다
        return

    solve(idx + 1, curr_sum) #현재 인덱스의 숫자를 선택하지 않은 경우
    solve(idx + 1, temp) #현재 인덱스의 숫자를 선택하여 합한 경우


for t in range(T):
    n, k = map(int, input().split())
    seq = list(map(int, input().split()))
    count = 0
    solve(0, 0) #0번째 원소부터, 현재 합은 0
    result.append(count)

for t in range(T):
    print("#{} {}".format((t + 1), result[t]))

1215번 [S/W 문제해결 기본] 3일차 - 회문1 / Python

문제

풀이과정

정해진 길이의 회문을 찾아서 완전탐색 가로 검사의 경우 행 접근, 슬라이싱으로 문자열 확인 세로 검사의 경우 열 접근, 정해진 회문의 길이 만큼 열을 탐색, 문자열 확인

string == string[::-1] 문자열 원문과 역순 비교

소스코드

T = 10

result = []
for i in range(T):
    length = int(input())
    testcase = []
    for _ in range(8):
        testcase.append(input())

    count = 0
    for i in range(8):
        for j in range(8 - length + 1): #검사 할 인덱스 주의
            #가로 검사
            string = testcase[i][j:j+length] #가로의 경우 슬라이싱
            if string == string[::-1]: #문자열 역순
                count += 1
            #세로 검사
            string = ''
            for k in range(length):
                string += testcase[j + k][i] #세로의 경우 row 인덱스와 col 인덱스 주의
            if string == string[::-1]:
                count += 1

    result.append(count)

for i in range(T):
    print("#{} {}".format((i+1), result[i]))

1209번 [S/W 문제해결 기본] 2일차 - Sum / Python

문제

풀이과정

반복분 안에서 행의 합, 열의 합 구하기 2개의 대각선에 따른 인덱스 접근으로 대각선 합 구하기

반복문을 수행하는 과정에서 구한 하나의 행의 합과 하나의 열의 합 중 큰 값을 저장 최종적으로 합의 결과가 저장된 리스트에서 최대값 출력

소스코드

T = 10

result = []
for t in range(T):
    test = int(input())
    testcase = []
    for _ in range(100):
        arr = list(map(int, input().split()))
        testcase.append(arr)

    arr_sum = []
    left_top_sum = 0 #left-top to right-bottom 대각선
    right_top_sum = 0 #right-top to right-bottom 대각선
    for i in range(100):
        row_sum = 0
        col_sum = 0
        left_top_sum += testcase[i][i]
        right_top_sum += testcase[i][-i - 1]
        for j in range(100):
            row_sum += testcase[i][j] #행의 합
            col_sum += testcase[j][i] #열의 합
        arr_sum.append(max(row_sum, col_sum))
    arr_sum.append(max(left_top_sum, right_top_sum))

    result.append(max(arr_sum)) #최대 값 구하기

for t in range(T):
    print("#{} {}".format((t+1), result[t]))

2005번 파스칼의 삼각형 / Python

문제

풀이과정

출력 형태를 고려하여 삼각형 그리기 왼쪽 위와 오른쪽 위에 인덱스 조작으로 접근 계산을 위해 0으로 채워진 2차원 리스트 선언

소스코드

T = int(input())

testcase = []
for i in range(T):
    n = int(input())
    testcase.append(n)

for i in range(T):
    n = testcase[i]
    result = [[0] * n for _ in range(n)]
    result[0][0] = 1
    for j in range(1, n):
        for k in range(j+1):
            result[j][k] = result[j-1][k-1] + result[j-1][k]  #출력 형태에 따라 왼쪽 위 오른쪽 위 접근

    print("#{}".format((i+1)))
    for j in range(n):
        for k in range(n):
            if result[j][k] != 0:
                print(result[j][k], end=' ')
        print()

2001번 파리 퇴치 / python

문제

풀이과정

파리채의 크기 만큼 완전 탐색 파리채의 크기 만큼 탐색시 탐색의 범위 지정

소스코드

T = int(input())

result = []
for i in range(T):
    n, m = map(int, input().split())
    fly = []
    for _ in range(n):
        arr = list(map(int, input().split()))
        fly.append(arr)

    kill = 0
    for x in range(n - m + 1): # 파리채의 영역 접근, 인덱스 계산에 주의
        for y in range(n - m + 1):
            temp = 0
            for a in range(m):
                for b in range(m):
                    temp += fly[x + a][y + b]
            if temp > kill:
                kill = temp

    result.append(kill)

for i in range(T):
    print("#{} {}".format((i + 1), result[i]))

1983번 조교의 성적 매기기 / Python

문제

풀이과정

학생 번호와 점수를 저장 key=lambda x: x[1], reverse=True 조건을 통해 성적 순으로 내림차순 정렬 성적을 기준으로 각 학생 번호에 성적 부여

소스코드

T = int(input())

result = []
for i in range(T):
    n, k = map(int, input().split())
    student = []
    grade = [''] * n
    grades = ['A+', 'A0', 'A-', 'B+', 'B0', 'B-', 'C+', 'C0', 'C-', 'D0']

    for j in range(n):
        middle, final, homework = map(int, input().split())
        score = middle * 0.35 + final * 0.45 + homework * 0.2
        student.append((j, score)) #학생번호 0 ~ (n-1) 인덱스 사용 주의
    student.sort(key=lambda x: x[1], reverse=True) #람다식 주의, 성적 내림차순 정렬

    for j in range(1, 11):
        for x in range(n//10*(j-1), n//10*j): #반복문 사용시 내부 변수 명 주의
            grade[student[x][0]] = grades[j-1]

    result.append(grade[k-1]) #인덱스에 주의

for i in range(T):
    print("#{} {}".format((i+1), result[i]))

1974번 스도쿠 검증 / Python

문제

풀이과정

가로 줄의 스도쿠 성립 여부 세로 줄의 스도쿠 성립 여부 박스의 스도쿠 성립 여부 인덱스 조작을 통한 접근, 각 성립 여부를 확인하기 위한 리스트 한 번이라도 틀리는 경우 더 이상 검사 필요 없다 이중 반복문 탈출

소스코드

#정답일 경우 1, 오답일 경우 0

T = int(input())

result = []
for t in range(T):
    testcase = []
    for _ in range(9):
        arr = list(map(int, input().split()))
        testcase.append(arr)
    verify = 1
    breaker = False
    for i in range(9):
        row_verify = [] #가로 검증
        col_verify = [] #세로 검증
        box_verify = [] #3*3 박스 검증
        for j in range(9):
            if testcase[i][j] not in row_verify and \
                    testcase[j][i] not in col_verify and \
                    testcase[i//3 * 3 + j % 3][i//3 * 3 + j//3] not in box_verify:
                row_verify.append(testcase[i][j])
                col_verify.append(testcase[j][i])
                box_verify.append(testcase[i//3 * 3 + j % 3][i//3 * 3 + j//3]) #3*3 box를 차례로 검사하기 위한 인덱스 접근
            else:
                verify = 0 #한번이라도 틀리면 더 이상 검사할 필요 없다.
                breaker = True
                break
        if breaker: #이중 반복문 탈출
            break
    result.append(verify)

for t in range(T):
    print("#{} {}".format((t+1), result[t]))

2007번 패턴 마디의 길이 / Python

문제

풀이과정

패턴 찾기 최초의 패턴은 첫 글자 하나 패턴이 성립되기 위해선 하나의 패턴이 나오고 다음부터 다시 같은 길이의 패턴이 등장해야한다. test[:len(pattern]] == test[len(pattern) : len(pattern) * 2] 패턴이 성립하지 않는 경우 패턴의 길이 1 증가

소스코드

T = int(input())

testcase = []
for i in range(T):
    testcase.append(input())

for i in range(T):
    test = testcase[i]
    pattern = test[0]
    end_point = 1
    while True:
        if pattern == test[len(pattern):len(pattern) * 2]: # 패턴 유효성 검사
            break
        pattern = test[:end_point] # 패턴 정의
        end_point += 1
    print("#{} {}".format((i+1), len(pattern)))

1926번 간단한 369 게임 / Python

문제

풀이과정

주석으로 코드 설명 대체

소스코드

n = int(input())

game = ['3', '6', '9'] #박수치는 경우
for i in range(1, n+1):
  num = (str(i)) #각 자리에서 비교위해 문자열로 치환
  count = 0 #박수치는 횟수
  for j in range(len(num)): #숫자의 자리수 마다
    if num[j] in game: #3, 6, 9 포함여부
      count += 1 #포함하는 경우 박수 횟수 증가
  if count > 0: #3, 6, 9가 하나라도 포함된 경우
    num = '-' * count #박수 횟수 만큼 '-'
  print(num, end=' ')

2086번 N-Queen / Python

문제

풀이과정

N * N 보드에서 N개의 퀸이 있을 수 있는 경우의 수 구하기 N개의 퀸의 서로 같은 행과 열, 대각선에 위치할 수 없다. rows 리스트의 인덱스는 행의 번호(x좌표), 해당 인덱스의 값은 열의 번호(y좌표) 같은 열에 위치하는 경우(y좌표) rows[x] == rows[i] 대각선에 위치하는 경우 abs(rows[x] - rows[i]) == abs(x - i) 퀸이 위치할 수 있는지 여부를 확인하는 함수 is_promising(x)

경우의 수를 계산할 전역 변수 global result 마지막 행 까지 검사한 경우 x == n 경우의 수 추가, 재귀 종료 (0, 0)부터 퀸을 위치 시키고 다음 행부터 퀸이 올 수 있는 경우를 재귀적으로 찾는다.

소스코드

T = int(input())

testcase = []

for i in range(T):
  testcase.append(int(input()))

def is_promising(x):
  for i in range(x):
    if rows[x] == rows[i] or abs(rows[x] - rows[i]) == abs(x - i):
      return False
  return True

def solve(x):
  global result
  if x == n:
    result += 1
    return

  for i in range(n):
    rows[x] = i
    if is_promising(x):
      solve(x+1)

for i in range(T):
  n = testcase[i]
  rows = [0] * n
  result = 0
  solve(0)
  print("#%d %d"%((i+1), result))

1208번 [S/W 문제해결 기본] 1일차 - Flatten / Python

문제

풀이과정

가장 큰 값에서 1을 빼고 가장 작은 값에 1을 더한다. 가장 큰 값(MAX)와 가장 작은 값(MIN)에 접근 필요 sort()을 통해 접근 혹은 max()와 min()을 통해 접근

소스코드

T = 10

dump = []
boxes = []

for i in range(T):
  dump.append(int(input()))
  box = list(map(int, input().split()))
  box.sort(reverse=True)
  boxes.append(box)

def solve(box, count):
  result = box[0] - box[-1]
  for i in range(count):
    box[0] -= 1
    box[-1] += 1
    box.sort(reverse=True)
    if result == 0 or result == 1:
      break
    result = box[0] - box[-1]
  return result

for i in range(T):
  result = solve(boxes[i], dump[i])
  print("#%d %d" %((i+1), result))

2056번 연월일 달력 / Python

문제

풀이과정

입력으로 주어진 8자리 날짜를 연, 월, 일 분리 숫자로 받을 것인가 문자열로 받을 것인가 자리수에 따라 날짜 분리를 위해 문자열로 받는다. 출력시 한자리 수의 경우 앞에 0이 붙어야 한다. 하드 코딩을 통해 날짜 성립 조건 확인 날짜 성립 조건인 1~12월의 경우 30일, 31일 분리하여 선언 2월의 경우 28일까지 날짜의 경우 01 ~ 31 리스트 선언, 각 월의 최대 날짜까지 슬라이싱으로 사용

출력시 숫자(테스트케이스 번호)와 문자열(결과)를 출력하기 위해 포맷 형식에 유의할 것

소스코드

T = int(input())

testcase = []

for i in range(T):
  testcase.append(input())

thirty = ['04', '06', '09', '11']
thirty_one = ['01', '03', '05', '07', '08', '10', '12']

days = []
for i in range(1, 32):
  day = ''
  if i < 10:
    day += '0' + str(i)
    days.append(day)
  else:
    day = str(i)
    days.append(day)


for i in range(T):
  year = testcase[i][:4]
  month = testcase[i][4:6]
  day = testcase[i][6:8]
  result = year+'/'+month+'/'+day

  if month not in thirty and month not in thirty_one and month != '02':
    result = '-1'
  elif month in thirty:
    if day not in days[:31]:
      result = '-1'
  elif month in thirty_one:
    if day not in days:
      result = '-1'
  elif month == '02':
    if day not in days[:29]:
      result = '-1'

  print("#%d %s"%((i+1), result))

D2 1204번 [S/W 문제해결 기본] 1일차 - 최빈수 구하기 / Python

문제

풀이과정

0 ~ 100점 사이 최빈 수 구하기 정해진 범위의 정수 형태, 계수 정렬 동일한 최빈 수가 있을 때 높은 점수를 출력, 뒤에서 부터 큰 값을 찾자 입력과 출력을 분리, 내가 보기 편하게

소스코드

T = int(input())

def sovle(grade):
  d = [0] * 101

  for i in range(1000):
    d[grade[i]] += 1 #계수정렬

  max = 0
  result = 0
  for i in range(0, 101):
    if d[-1-i] > max: #뒤에서 확인
      max = d[-1-i]
      result = 101-1-i #최빈수의 인덱스

  return result

answer = []

for i in range(1, T+1):
  n = int(input())
  grade = list(map(int, input().split()))
  result = sovle(grade)
  answer.append(result)

for test_case in range(1, T+1):
  print("#{} {}".format(test_case, answer[test_case-1]))

D3 1206번 [S/W 문제해결 기본] 1일차 - View / Python

문제

풀이과정

조망권이 성립되는 조건, 양쪽의 거리 최소 2이상 확보 거리 확보 위해선 거리 2 이내의 빌딩보다 높이가 높아야 한다. 왼쪽 빌딩과의 높이 계산, 오른쪽 빌딩과의 높이 계산 후 양쪽 빌딩보다 높은 층(왼쪽, 오른쪽 둘 중에서 작은 값)을 계산

소스코드

t = 10

answer = []

for i in range(t):
  n = int(input())
  height = list(map(int, input().split()))

  result = 0
  for j in range(2, n-2):
    left = height[j] - max(height[j-1], height[j-2])
    right = height[j] - max(height[j+1], height[j+2])
    if left > 0 and right > 0:
      result = min(left, right)

  answer.append(result)

for i in range(t):
  print("#%d %d" %(i+1, answer[i]))