Algorithm

[백준 / Python 파이썬] 2475번 - 검증수

[Bronze V] 검증수 - 2475 문제 링크 분류 구현(implementation), 사칙연산(arithmetic), 수학(math) 문제 설명 컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들어간다. 검증수는 고유번호의 처음 5자리에 들어가는 5개의 숫자를 각각 제곱한 수의 합을 10으로 나눈 나머지이다. 예를 들어 고유번호의 처음 5자리의 숫자들이 04256이면, 각 숫자를 제곱한 수들의 합 0+16+4+25+36 = 81 을 10으로 나눈 나머지인 1이 검증수이다. 입력 첫째 줄에 고유번호의 처음 5자리의 숫자들이 빈칸을 사이에 두고 하나씩 주어..

[백준 / Python 파이썬] 1890번 - 점프

[Silver I] 점프 - 1890 문제 링크 분류 다이나믹 프로그래밍(dp) 문제 설명 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에..

[SWEA / Python 파이썬] 1954번 - 달팽이 숫자

[D2] 달팽이 숫자 - 1954 문제 링크 ※ SW Expert 아카데미의 문제는 무단 복제하는 것이 금지되어 있습니다. # 테스트케이스 입력 받기 T = int(input()) for t in range(1,T+1): # 정수 N 입력받고 0으로 채운 N*N 2차원 행렬 만들기 N = int(input()) arr = [[0]*N for n in range(N)] # 델타를 이용하기 위해 시계 방향으로 배열 생성 dc = [0, 1, 0, -1] dr = [1, 0, -1, 0] # N**2 만큼 반복문 실행하여 0으로 채워진 행렬에 숫자 채우기 nc = 0 nr = 0 # arr[0][0]은 1로 초기값 설정하고 2부터 반복문 시작 arr[0][0] = 1 for i in range(2, (N**2..

[프로그래머스 / Python 파이썬] Level1 - 폰켓몬

[level 1] 폰켓몬 - 1845 문제 링크 구분 코딩테스트 연습 > 해시 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두..

[백준 / Python 파이썬] 22857번 - 가장 긴 짝수 연속한 부분 수열 (small)

[Silver II] 가장 긴 짝수 연속한 부분 수열 (small) - 22857 문제 링크 분류 다이나믹 프로그래밍(dp), 두 포인터(two_pointer) 문제 설명 길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다. 예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자. 입력 수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구..

[백준 / Python 파이썬] 2212번 - 센서

[Gold V] 센서 - 2212 문제 링크 분류 그리디 알고리즘(greedy), 정렬(sorting) 문제 설명 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다. 편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직..

[백준 / Python 파이썬] 4949번 - 균형잡힌 세상

[Silver IV] 균형잡힌 세상 - 4949 문제 링크 분류 자료 구조(data_structures), 스택(stack), 문자열(string) 문제 설명 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재..

[백준 / Python 파이썬] 10773번 - 제로

[Silver IV] 제로 - 10773 문제 링크 분류 자료 구조(data_structures), 구현(implementation), 스택(stack) 문제 설명 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이..