코딩테스트 수업

1주차

소갱 2021. 12. 1. 13:18

1) 기업 코딩테스트 유형

2) 시간복잡도

백준이나 프로그래머스 문제를 풀다 보면 심심치 않게 시간 초과 오류가 뜨는 것을 볼 수 있다.

왜 그럴까? 연산속도에 관련된 문제다. 일반적으로 1초에 1억 개의 연산을 할 수 있다. 물론 각 언어마다 같은 연산 횟수여도 시간은 다르지만 시험에선 이를 고려하기 때문에 결국 1억 이라는 연산 횟수가 중요합니다.

 

1억 번의 연산을 기준으로 잡고 문제를 해석한다면 해당 문제를 손쉽게 풀 수 있는 경우도 생길 수 있다.

예를 들어서 문제에서 조건으로 주어진 n의 범위가 1이상 100000이하라고 해보자 최악의 경우를 가정한 빅오 표기법으로 생각해 봤을 때 시간복잡도가 O(N^2)일 경우 연산횟수가 100억 번이 된다. 따라서 O(N^2)으로는 절대 풀 수 없다는 것을 의미한다. 그렇다면 이 문제는 O(N)이나 O(NlogN)으로 풀어야 한다는 이야기가 되고, 그러한 시간복잡도를 가진 알고리즘 풀이 방법을 좁힐 수 있게 된다.

 

경험상 n의 값이 10만 이상일 경우 이분탐색으로 푸는 문제가 90%였다.

 

3) 문제 풀이

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

n,m = map(int,input().split())
array = list(map(int,input().split()))

def binary_search(start,end):
    if start > end:
        return start-1
    
    mid = (start+end) // 2
    sm = 0
    for i in array:
        if i - mid >= 0:
            sm += i-mid
    if sm > m:
        return binary_search(mid+1,end)
    elif sm == m:
        return mid
    else:
        return binary_search(start,mid-1)

print(binary_search(0,max(array)))

우선 이번 나무자르기 문제는 문제에서 조건이 1<=N<=1,000,000 입니다. 위에서 설명했듯이 N의 값이 10000이 넘어간다면 완전탐색 (일반적으로 시간복잡도 O(N^2)) 으로는 풀 수가 없습니다. 따라서 문제를 보자마자 이분탐색 혹은 정렬이라고 어느정도 예측을 하고 문제를 풀기 시작해야 합니다.

 

이분탐색 함수는 많이 사용되니 이해가 먼저고, 그 다음에 암기 하시면 좋습니다.

sm 은 자른 나무의 합을 넣는 sum 값을 넣는 변수입니다.

 

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

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

import math

def prime_number(num):
    if num == 2:
        return True
    elif num == 1:
        return False
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

M = int(input())
N = int(input())
sm = 0
mn = N+1
for i in range(M,N+1):
    if prime_number(i):
        sm += i
        mn = min(mn,i)
if sm == 0:
    print(-1)
else:
    print(sm)
    print(mn)

소수문제는 에라토스체네스의 체 알고리즘을 이용합니다. 지난 카카오 블라인드 1차 코테에서 나온 적이 있으니 선 이해후 암기하시면 됩니다!

여기서도 마찬가지로 sm은 소수의 sum을 나타내는 변수입니다. mn 은 min을 뜻하는 변수입니다.

만일 sm이 0이라면 소수가 발견되지 않았다는 말과 같으므로 -1을 출력했습니다.

 

 

2667번: 단지번호붙이기 (acmicpc.net)

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int,input())))

visit = [[False for _ in range(n)] for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
num = 1
def DFS(x,y):
    global num
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<n:
            if visit[nx][ny] == False and array[nx][ny] == 1:
                visit[nx][ny] = True
                num += 1
                DFS(nx,ny)
total_num = 0
answer = []
for i in range(n):
    for j in range(n):
        if visit[i][j] == False and array[i][j] == 1:
            visit[i][j] = True
            total_num += 1
            DFS(i,j)
            answer.append(num)
            num = 1
answer.sort()
print(total_num)
for i in answer:
    print(i)

여기서 num (각 구역마다 집의 개수) 를 함수 밖에서 선언해서 global로 받아오는게 중요합니다. DFS는 기본적으로 재귀를 통한 알고리즘이기때문에 함수 안에 선언할 경우 초기화되기 때문입니다. 또 여기서 사용하는 dx dy의 값은 0번째 인덱스부터 기준으로 북,동,남,서 를 의미합니다. 예를 들어서 북쪽으로 이동할경우 x는 x(기존 값) + dx[0] 이 되고 y는 y(기존값) + dy[0]입니다. x는 2차원 배열에서 위, 아래 / y는 2차원 배열에서 왼,오 를 뜻합니다.

DFS 알고리즘은 기본적으로 저런 형태로 기억하시면 좋습니다.

 

결과를 출력할 땐 오름차순으로 출력하기 때문에 answer.sort()를 해주고 이때 sort는 퀵소트와 버블소트를 합친 알고리즘으로 시간복잡도는 O(nlogn)입니다. 따라서 파이썬 내에서 정렬할 때 시간복잡도 상관없이 sort 쓰시면 됩니다.

 

코딩테스트 연습 - 오픈채팅방 | 프로그래머스 (programmers.co.kr)

 

코딩테스트 연습 - 오픈채팅방

오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오

programmers.co.kr

def solution(record):
    # 아이디 : 이름
    dic = {}
    for i in record:
        if 'Enter' in i or 'Change' in i:
            str1, str2, str3 = i.split(" ") # ex) Enter, uid1234, Muzi
            dic[str2] = str3
    answer = []
    for i in record:
        if 'Enter' in i:
            str1, str2, str3 = i.split(" ")
            answer.append(dic[str2]+"님이 들어왔습니다.")
        elif 'Leave' in i:
            str1, str2 = i.split(" ")
            answer.append(dic[str2]+"님이 나갔습니다.")
            
    return answer

우선 이 문제는 아이디에 따른 이름이 중요하므로 해쉬 테이블 (파이썬에서는 dict)를 사용했습니다.

이 문제에서 중요한건 파이썬 내에 있는 split이라는 내장함수인데, 만약 i = "Enter id1234 Muzi" 였다면

i.split(" ") 는 i를 " "로 구분한다는 의미 입니다. i안에 공백이 2개 있으므로 split으로 나누게 되면 총 3개로 나누어집니다. 따라서 3개의 변수로 이를 받아줘야하고 str1, str2, str3 = i.split(" ")에서

str1 = "Enter" , str2 = "id1234", str3 = "Muzi"가 됩니다.