코딩테스트 #01

MUUU·2022년 1월 10일

코딩테스트 코테

코딩테스트

목록 보기

1/8

코테사이트

프로그래머스
https://programmers.co.kr/
백준
https://www.acmicpc.net/
코드업
https://codeup.kr/
sw expert 아카데미
https://swexpertacademy.com/main/main.do
리트코드
https://leetcode.com/
코테강의 : 코드플러스
https://code.plus/
코드포스
https://ndb796.tistory.com/164

나동빈 강의

https://youtu.be/m-9pAwq1o3w

온라인 개발환경

https://pythontutor.com/visualize.html#mode=edit

라이브러리화 _ 팀노트

출제빈도

빅오

평균적으로 5초라고 생각할것

코테강의

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9-%EC%9D%B8%ED%84%B0%EB%B7%B0

자료형

실수형은 비교가 제대로 되지 않음

리스트 초기화

리스트 컴프리헨션

리스트 관련 메소드

array=[1,3,4,5,6,3,5]
array.sort()
array

[1, 3, 3, 4, 5, 5, 6]

문자열 연산

튜플 특징 : 변경불가 , 해쉬

딕셔너리

셋 (집합) #딕셔너리랑 구분

집합과 딕셔너리 차이점: 순서가 없어 인덱싱불가

표준입력법 : input(), map()

map(int, input().split())
정수 숫자 여러개 공백 기준으로 입력 받을 수 있다.
data=list(map(int, input().split()))
sys.stdin.readline()

import sys

data=sys.stdin.readline().rstrip()
print(data)


print(7, end=" ")
print(8, end=" ")

7 8

연산자

비교연산자 : >= ,!=,
논리연산자

반복문

PASS

score=85

if score>=80:
    pass #나중에 작성
else: 
    f'성적이 80점 미만이다'


f'프로그램 종료'

프로그램 종료

break

반복문 예제

함수

글로벌 변수

array=[1,2,3,4,5]

def func():
    array=[2,4,6]
    array.append(8)
    print(array)

    
func()
print(array)

[2, 4, 6, 8]

[1, 2, 3, 4, 5]

array=[1,2,3,4,5]

def func():
	global array
    array=[2,4,6]
    array.append(8)
    print(array)

    
func()
print(array)

[2, 4, 6, 8]

람다

(lambda a,b: a+b)(3,7)

10

array=[('홍길동',50),('이순신',43),('아무개',74)]
print(sorted(array, key=lambda x: x[1]))

[('이순신', 43), ('홍길동', 50), ('아무개', 74)]

list1=[1,2,3,4,5]
list2=[6,7,8,9,10]
result=map(lambda a,b: a+b, list1, list2)
print(list(result))

[7, 9, 11, 13, 15]

파이썬 라이브러리

itertools
heapq
bisect
collections
math : sum(), min(),max(), eval()

순열과 조합

from itertools import product

data=['A','B','C']
result=list(product(data,repeat=2)) # 2개를 뽑는 모든 순열
print(result)

print('*'*50)
from itertools import combinations_with_replacement
result=list(combinations_with_replacement(data,2)) # 2개를 뽑는 모든 조합
print(result)

[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

counter

if a=='blue' 같은거 필요없다

gcd, lcm (최대공약수, 최소공배수)

그리디

현재상황에서 가장 좋은것부터

거스름돈 예제 :

동전의 값이 각각의 배수여야함 ( if 500 ,400, 100 원이면 불가)
빅오:O(K)

n=1260
cnt=0
array=[500,100,50,10]

for coin in array:
	cnt+=n//coin
    n%=coin
print(cnt)

6

1이 될때까지: 제한시간 2초

첫째줄에 N( 1<=N <100,000) 과 K(2<=K <=100,000)가 공백을 기준으로 하여 각각 자연수로 주어짐
첫째줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값?
- 1. N에서 1을 뺀다
- 2. N을 K로 나눈다
입력값: 25 5
출력값: 2

무조건 나누면 된다고 생각하고 작성한 코드

n,k=map(int,input().split())

cnt=0
quo=0 # quotient: 몫 

while n>1:
    quo=n//k
    n=quo
    cnt+=1
     
print(cnt)

2차풀이 : 변수 더 적게

n,k=map(int,input().split())
cnt=0
while n>1:
    n//=k
    cnt+=1
print(cnt)

제대로 된 풀이 : k가 2이상이면 무조건 나누기 우선 연산

n,k=map(int,input().split())
res=0

while 1:
    # N이 K의 배수가 될때까지 빼기
    t=(n//k)*k  #t는 k의 배수
    res+=(n-t) 
    n=t 
    
    # N이 k보다 작아지면 탈출
    if n<k:
        break 
    
    #k로 나누기 : 시간복잡도 낮춤
    res+=1 #k를 나누는 연산을 추가
    n//=k 
    
    
# 마지막으로 남은수에 대하여 1씩 빼기
res+=(n-1) # 아직 n!=1 이므로 빼준다 
print(res)

곱하기 혹은 더하기

숫자로만 이뤄진 문자열 s 사이에 'x' 혹은 '+' 연산자를 넣어 가장 큰수를 구하기. 모든 연산은 왼쪽부터 순서대로 이뤄짐
가장 큰 출력값은 20억 이하의 정수 : 최대값 명시
s= 02984 : (0+2)98*4=576
첫째줄에 여러개의 숫자로 구성된 문자열 s가 주어짐(1<=len(s)<=20)
시간제한 1초
입력예시: 567
출력예시: 210

s=input()
# res=0 # 결과값은 0이나 1로 둘 수 없음
res=int(s[0])

for i in range(1,len(s)):
    n=int(s[i]) # 문자열의 정수화
    print(n)
    if n<=1 or res<=1: #res값도 0,1일 경우 포함
        res+=n
    else:
        res*=n
print(res)

2가지 전략 필요

res 초기값이 0이나 1의 정수일 수 없음

문자열 s를 int로 바꾸기

모험가 길드

n명의 모험가 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹수의 최댓값?
공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야
모든 모험가를 넣을 필요없음
시간제한 1초
입력조건:
-첫째줄에 모험가의 수 N이 주어집니다. (1<=N<=100,000)
-둘째줄에 각 모험가의 공포도값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분
출력조건: 여행을 떠날수 있는 그룹수의 최댓값을 출력합니다.
입력예시:
5
2 3 1 2 2
출력예시:
2

n=int(input())
data=list(map(int, input().split()))
data.sort()

res=0 # 총 그룹의 수
cnt=0 # 현재 그룹에 포함된 모험가의 수

for i in data:
    cnt+=1
    if cnt>=i:
        res+=1
        cnt=0
print(res)

구현

풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려움
2차원 행렬 (matrix)

예시

for i in range(5):
    for j in range(5):
        print('(',i,',',j,')', end=' ')
    print()

( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 )
( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) ( 1 , 4 )
( 2 , 0 ) ( 2 , 1 ) ( 2 , 2 ) ( 2 , 3 ) ( 2 , 4 )
( 3 , 0 ) ( 3 , 1 ) ( 3 , 2 ) ( 3 , 3 ) ( 3 , 4 )
( 4 , 0 ) ( 4 , 1 ) ( 4 , 2 ) ( 4 , 3 ) ( 4 , 4 )

# x * y matrix

# 동, 북, 서 ,남
dx=[0,-1,0,1]
dy=[1,0,-1,0]

#현재위치
x,y=2,2

for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    print(nx,ny) # 다음 위치

2 3
1 2
2 1
3 2

상화좌우 문제

n * n 정사각형 공간, 시작좌표는 (1,1)
LRUD: 좌우위아래
공간을 벗어나는 움직임은 무시
시간제한 2초
입력조건
- 첫째줄에 공간의 크기를 나타내는 N이 주어집니다( 1<=N<=100) # 10,000
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어집니다. (1<=이동횟수<=100)
출력조건
-첫째줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X,Y)를 공백을 기준으로 구분하여 출력
입력예시
5
R R R U D D
출력예시
3 4
처음 답안 : 출력값 안 나옴


# X, Y

x,y=(1,1)

n=int(input())
s=input().split()

for i in range(len(s)):
    if 1<=(x and y) <= n:
        if i=='R':
            y+=1
        elif i=='L':
            y-=1
        elif i=='U':
            x+=1
        elif i=='D':
            x-=1
    else: continue
print(x,y)

모범 답안

# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
            print(nx,ny)
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        print(f'else{nx,ny}')
        continue
    # 공간 이내라면 이동 수행
    x, y = nx, ny

print(x, y)

5
R R R U D D
1 2
1 3
1 4
0 4
else(0, 4)
2 4
3 4
3 4

시각문제 : 완전탐색(Brute Forcing) :모든 경우의 수

3이 하나라도 포함되는 시각 모든경우의 수를 구하기
시간제한 2초
입력조건: 첫째줄에 정수 N이 입렵됨(O<=N<=23)
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수
입력예시:5
출력예시:11475

h=int(input())
cnt=0
for i in range(h+1): #시간
    for j in range(60): #분
        for k in range(60): #초 
            if '3' in str(i)+str(j)+str(k):
                cnt+=1
print(cnt)

왕실의 나이트

시간제한 1초
입력조건:
8 * 8 좌표평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력. 입력문자는 a1처럼 열과 행으로 이뤄짐
출력조건: 첫째줄에 나이트가 이동할 수 있는 경우의 수 출력
입력예시 : a1
출력예시 : 2

# 현재 나이트 위치 입력받기
place=input()
row=int(place[1])
col=int(ord(place[0]))-int(ord('a'))+1 #ord로 숫자로 변경 

#나이트가 이동할 수 있는 8방향 정의
steps=[(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]


# 8가지 방향에 대해 각 위치로 이동 가능한지 확인
res=0
for step in steps:
    #이동하려는 위치 확인
    next_r=row+step[0]
    next_c=col+step[1]
    if next_r>=1 and next_r<=8 and next_c>=1 and next_c<=8:
        res+=1
print(res)

문자열 재정렬

알파벳 대문자와 숫자(0~9)로만 구서된 문자열이 주어짐.
알파벳은 오름차순 정렬. 숫자의 합 출력
입력조건: 첫째줄에 하나의 문자열s가 주어집니다. (1<= S의길이 <=10,000)
출력조건: 첫째줄에 문제에서 요구하는 정답을 출력
입력예시1: K1KA5CB7
출력예시1: ABCKK13
입력예시2: AJKDLSI412K4JSJ9D
출력예시2: ADDIJJJKKLSS20

리스트에 저장된 알파벳을 정렬해 출력, 숫자는 합계. isalpha()

s=input()
num=0
res=[]
for i in s:
    if i.isalpha():
        res.append(i)
    else:
        num+=int(i)
# 알파벳 정렬        
res.sort()

if num>0:
    res.append(str(num))

print(res)
# 리스트를 문자열로 반환하여 출력
print(''.join(res))

['A', 'B', 'C', 'K', 'K', '13']
ABCKK13

MUUU

데이터분석

코딩테스트 #01

코딩테스트

코테사이트

나동빈 강의

온라인 개발환경

라이브러리화 _ 팀노트

출제빈도

빅오

코테강의

자료형

리스트 초기화

리스트 컴프리헨션

리스트 관련 메소드

문자열 연산

튜플 특징 : 변경불가 , 해쉬

딕셔너리

셋 (집합) #딕셔너리랑 구분

집합과 딕셔너리 차이점: 순서가 없어 인덱싱불가

표준입력법 : input(), map()

연산자

반복문

PASS

break

반복문 예제

함수

글로벌 변수

람다

파이썬 라이브러리

순열과 조합

counter

gcd, lcm (최대공약수, 최소공배수)

그리디

거스름돈 예제 :

1이 될때까지: 제한시간 2초

무조건 나누면 된다고 생각하고 작성한 코드

제대로 된 풀이 : k가 2이상이면 무조건 나누기 우선 연산

곱하기 혹은 더하기

모험가 길드

구현

예시

상화좌우 문제

시각문제 : 완전탐색(Brute Forcing) :모든 경우의 수

왕실의 나이트

문자열 재정렬

0개의 댓글