크래프톤 정글 WEEK1

알고리즘 문제를 풀다 알게 된 정보들에 대해 정리해봤다.
알고리즘 문제 푸는게 익숙치 않아서 풀이를 많이 참고하게 되는데 아직은 초보인지라..

그래도 그만큼 알아가는 것들이 많은 것 같다!

 

 

[백준 2562] 최댓값

 

a = []

for i in range(1,10):
    a.append(int(input()))

print(max(a))
print(a.index(max(a))+1)

최댓값 내장 함수 max()
최솟값 내장 함수 min()

인덱스 값 구하기 list.index()

 

 

[백준 11654] 아스키 코드

 

text = input()

print(ord(text))

ord() : 문자 -> 아스키 코드 변환
chr() : 아스키 코드 -> 문자 변환

print(chr(65))

 

 

[백준 9020] 골드바흐의 추측

 

짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

먼저 소수를 판별하고 주어진 두 수의 조합을 찾아야 한다.

 

 

1. 소수 판별(제곱근 범위 나누기법)

 

제곱근 범위 나누기법이란 어떤 수의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 수까지만 검사하면 나머지는 검사할 필요가 없다는 방법이다.

어떤 수의 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
-> 그 이유는 어떤 수의 약수는 양쪽 끝을 곱하면 자기 자신이 되는데, 그 수의 제곱근 곱하기 그 수의 제곱근은 자기 자신이 되고 즉 중간에 위치하게 된다.

import math

def prime(a):
	# 1은 소수가 아니기 때문에 False
	if a == 1:
    	return False
    # 2부터 제곱근까지 반복
    for i in range(2, int(math.sqrt(a))+1):
    	# 나머지가 없으면 짝수
    	if a % i == 0:
        	return False
    # 홀수
    return True

 

2. 가장 차이가 적은 두 소수를 합해서 짝수가 되도록?

 

주어진 수를 반으로 나누어서 한 개는 +1, 한 개는 -1을 해서 두 수가 모두 소수인지 확인한다.

예를 들어 8이 주어졌다면
8을 반으로 나누면 8 = 4 + 4
그러나 4는 짝수이므로 8 = (4-1) + (4+1) => 3 + 5
3과 5 둘다 소수 -> 골드바흐 파티션 O

# 테스트 케이스의 개수
T = int(input())

for _ in range(T):
    n = int(input())
	#n에 중간 수를 두 개의 변수로 저장
    A = n //2
    B = n //2
    #0부터 중간 수까지 
    for i in range(n//2):
    	#소수이면 출력
        if prime(A) and prime(B):
            print(A,B)
            break
        #짝수이면 두 수를 하나씩 더해주고 빼기    
        else:
            A -=1
            B +=1

 

 

완성 코드

import math

def prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a))+1):
        if a % i == 0:
            return False
    return True
            
T = int(input())

for _ in range(T):
    n = int(input())
    A = n //2
    B = n //2
    for i in range(n//2):
        if prime(A) and prime(B):
            print(A,B)
            break
        else:
            A -=1
            B +=1
    

 

 

[백준 2751] 수 정렬하기 2

 

 

import sys

N = int(sys.stdin.readline())
Nlist = []
for _ in range(N):
    Nlist.append(int(sys.stdin.readline()))
    
Nlist.sort()
Nlist_ = set(Nlist)
Nlist = list(Nlist_)

for i in Nlist:
    print(i)

 

1) sys.stdin.readline()

 

시간 초과가 떠서 찾아보니 input() 대신 sys.stdin.readline()을 사용해야 한다는 것을 알게 되었다.
반복문으로 여러 줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 발생할 수 있기에 반복문으로 여러 줄을 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않는다.

 

+ input이 느린 이유

1. input()은 매개변수로 prompt message를 받는다.(따라서 입력을 받기 전에 prompt message를 출력해야 한다.)
2. 입력받은 값의 개행 문자를 삭제시키고 반환한다

+ prompt message란?

in_ input("prompt message를 입력해주세요:")
print(in_)

 

메세지를 입력 받지 않을 때도 있지만 속도 지연에 여전히 작용.

 

 

2) 파이썬 리스트 중복 제거 set

 

set 자료 구조의 특징은 중복이 없다는 것이다.
중복이 불가능하다는 성질을 이용해서 리스트에서 중복을 제거할 수 있다.

리스트 자료형을 set(리스트)를 통해서 set 타입으로 변경하면서 중복을 제거하고
그 후 list(set(리스트)) 다시 리스트로 감싸주어서 리스트 타입으로 데이터를 변경한다.

Nlist_ = set(Nlist)
Nlist = list(Nlist_)

 

3) sorted()와 sort()의 차이

 

sorted() 함수는 sorted(리스트명) 형식으로 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환
sort() 함수는 리스트명.sort() 형식으로 "리스트형의 메소드"이며 리스트 원본값을 직접 수정

 

 

[백준 1181] 단어 정렬

 

N = int(input())
words = []

for _ in range(N):
    words.append(input())

# 중복 제거 위해 set 타입으로 변경
# -> set을 list 타입으로 변경 
words_list = set(words)
words = list(words_list)

# 오름차순 정렬
words.sort()
# 길이 순으로 정렬
words.sort(key = len)

for i in words:
    print(i)

1. 길이 순 정렬
   sorted(key = len)
2. 절대값 기준 정렬
   sorted(key = abs)

 

 

[백준 10828] 스택

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

 

push() 스택에 원소 추가

- 리스트의 가장 마지막에 원소를 넣는다.

stack = [1,2,3]
stack.append(4)

stack	

#[1,2,3,4]

 

pop() 스택에서 원소 제거
- 리스트의 가장 마지막 원소를 제거.

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

print(top)
stack	

#3
# [1,2]

 

top 스택의 top 가져오기

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

top

#3

 

 

완성코드

import sys

N = int(sys.stdin.readline())
stacks = []

for _ in range(N):
    command = sys.stdin.readline().split()
    
    if command[0] == 'push':
        stacks.append(command[1])
    elif command[0] == 'pop':
        if len(stacks) == 0:
            print("-1")
        else:
            print(stacks.pop())
    elif command[0] == 'size':
        print(len(stacks))
    elif command[0] == 'empty':
        if len(stacks) == 0:
            print("1")
        else:
            print("0")
    elif command[0] =='top':
        if len(stacks) == 0:
            print("-1")
        else:
        	#스택의 가장 위에 있는 정수 - > 가장 나중에 들어온 정수
            print(stacks[-1])

 

 

[백준 9663번] N-Queen

 

• N X N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제.
• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오.

 

퀸을 놓지 못하는 경우는 이와 같다.

 

1. 같은 열에 다른 퀸이 있는 경우

 

Q_row라는 배열 안에 같은 값이 있는지 없는지를 확인한다.
즉, Q_row[x] =[i]는 동일한 i값이 있는지 보겠다는 것.
퀸을 [x,i]위치에 놓겠다!

 

2. 대각선(왼쪽,오른쪽)에 다른 퀸이 있는 경우

 

퀸을 맨 윗 행부터 차례로 채우고 있기 때문에 현재 i보다 큰 값들은 확인할 필요 없이 i보다 작은 곳, 즉 체스판의 위쪽만 확인하면 된다.
첫 번째로, 위쪽 위 대각선의 값들을 보면
만약 현재 퀸을 놓은 위치가 (3,3)라고 가정, 왼쪽 대각선의 좌표는 각각 (2,2),(1,1),(0,0)이 된다.
여기서 (3,3)을 x와 i라고 하고, (2,2)를 x1,y1, (1,1)을 x2,y2, (0,0)을 x3,y3이라고 하면
x에서 x1을 뺀 값과 i에서 y1을 뺀 값 모두 1로 같다.
x에서 x2를 뺀 값과 i에서 y2를 뺀 값 모두 2로 같다.
x에서 x3을 뺀 값과 i에서 y3을 뺀 값 모두 3으로 같다.

오른쪽도 마찬가지이므로 절댓값을 사용하여 함수를 짜면 된다.

if Q_row[x] == Q_row[i] or abs(Q_row[x]- Q_row[i]) == abs(x-i):

 

만약 현재 퀸을 놓으려는 위치가 promising하다면, 다음 퀸을 놓기 위한 n_queens(x+1)을 호출해주도록 하고, 그렇게 n번째까지 돌다가 x가 n이 되면 모든 퀸을 놓았다는 것이므로 count에 1을 추가해준다.

 

 

완성코드

N = int(input())

Q_row = [0] * N
count = 0

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

def n_queens(x):
    global count
    if x == N:
        count += 1
        return
    else:
        #각 행에 퀸(i) 놓아보기
        for i in range(N):
            #퀸을 [x,i] 위치에 놓겠다.
            Q_row[x] = i
            #퀸의 위치를 정하고 나서는, 해당 위치에 퀸을 놓을 수 있는지 없는지 is_promising 함수를 통해서 판단한다.
            if is_promising(x):
                n_queens(x+1)    
                
n_queens(0)
print(count)

 

 

[백준 2309] 일곱 난쟁이

 

아홉 개 줄에 걸쳐 난쟁이들의 키가 주어진다.
일곱 난쟁이의 키의 합이 100이다. 아홉 난쟁이의 키가 주어졌을 때, 일곱 난쟁이를 찾아라
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

 

 

 

풀이
7명을 합한 값이 100, 9명 중에서 합이 100이 되는 7명을 찾아야 한다.
그러면 모든 경우의 수를 구해야하는데, 9명을 다 더한 값에서 2명을 빼서 100이 되면 7명을 찾을 수 있다. (브루트 포스법)

#난쟁이 키 리스트
nan = []
for i in range(9):
    nan.append(int(input()))
    
nan.sort()      #오름차순 정렬
nan_sum = sum(nan)

#찾을 2명
temp1 = 0
temp2 = 0

for i in range(len(nan)):
    for j in range(i+1, len(nan)):
        if nan_sum - (nan[i] + nan[j]) == 100:
            temp1 = nan[i]
            temp2 = nan[j]
        
nan.remove(temp1)
nan.remove(temp2)

for i in nan:
    print(i)            
    

 

 

[백준 2805] 나무자르기

 

상근이가 절단기에 높이를 15로 지정했다면, 나무의 높이가 20, 15, 10, 17인 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다

(총 7미터) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0
상근이는 필요한 만큼만 집으로 가져가려고 한다.

 

 

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값 출력

풀이방법

1. 이분탐색을 통해서 중간값(mid = start(최소) + end(나무의 최댓값))을 찾고 나무를 자른다.
2. 총 잘린 나무의 길이(total)가 상근이가 필요로 하는 길이(M)보다 길면 start = mid + 1
짧으면 end = mid -1로 해서 start가 end보다 작거나 같을 때까지 범위를 좁혀가며 찾는다.

완성코드

N, M = map(int,input().split())
H = list(map(int,input().split()))
    
end = max(H)
start = 0

#이분 탐색
while start <= end:
    mid = (start+end) //2		
    total = 0

    for tree in H:
        if mid <= tree: 
            total += tree - mid
    
    if total > M:
        start = mid + 1	#자를 높이를 높여준다.
    else:	#적어도 M미터의 나무를 가져갸아 한다고 했으니
    	result = mid
        end = mid - 1 	#자를 높이를 낮춰준다.
           
print(result)

 

 

[백준 2630] 색종이 만들기

 

분할 정복, 재귀 문제

 

 

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 X N/2색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

n/2로 나누어 4개의 종이를 만들면 각 사면체를 재귀함수로 돌려 반복한다.

1사면체 cut(x, y, n//2)
2사면체 cut(x+n//2, y, n//2)
3사면체 cut(x, y+n//2, n//2)
4사면체 cut(x+n//2, y+n//2, n//2)

import sys

n = int(input())

paper = []
for i in range(n):
    paper.append(list(map(int,sys.stdin.readline().split())))
    
white = 0
blue = 0    
def cut(x,y,n):
	#paper[0][0] , color = 1
    color = paper[x][y]
    global white, blue
    
    for i in range(x,x+n):
        for j in range(y,y+n):
            if paper[i][j] !=color:
                cut(x,y,n//2)				#1사면체
                cut(x+n//2,y,n//2)			#2사면체
                cut(x,y+n//2,n//2)			#3사면체
                cut(x+n//2,y+n//2,n//2)		#4사면체
                return 0
    
    if color == 0:
        white +=1
    else:
        blue +=1
        
cut(0,0,n)
print(white, blue, sep ="\n")