[코딩테스트] 이것이 취업을 위한 코딩테스트다 1

GGG·2022년 8월 11일
코딩테스트
0

이것이 취업을 위한 코딩테스트다

목록 보기
1/3
post-thumbnail

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법 → 정렬 알고리즘과 일반적으로 같이 사용됨
특별한 사용 방법을 알고 있지 않아도 풀 수 있는 문제
문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토하는 것이 필요

문제

  • 거스름돈 https://www.acmicpc.net/problem/5585
    import sys

def solution(money):
    money = 1000 - money
    coin_list = [500, 100, 50, 10, 5, 1]
    ans = 0

    for coin in coin_list:
        ans += money // coin
        money %= coin

    return ans

if __name__ == "__main__":
    print(solution(int(sys.stdin.readline())))
  • 큰 수의 법칙
    import sys

def solution(n, m, k, list_):
    list_.sort(reverse=True)
    max1, max2 = list_[0:2]

    ans = m // (k+1) * (k*max1 + max2) + m % (k+1) * max1
    return ans

if __name__ == "__main__":
    n, m, k = map(int, sys.stdin.readline().split())
    list_ = [int(x) for x in sys.stdin.readline().split()]
    print(solution(n, m, k, list_))
  • 숫자 카드 게임
    import sys

def solution(n, m, cards):
    ans = - float('inf')
    for card_ in cards:
        ans = max(ans, min(card_))
    return ans

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    cards = [[] for _ in range(n)]
    for idx in range(n):
        cards[idx] = list(map(int, sys.stdin.readline().split()))
    print(solution(n, m, cards))
  • 1이 될 때까지
    import sys

def solution(n, k):
    count = 0
    while n != 1:
        if n % k == 0:
            n //= k
        else:
            n -= 1
        count += 1
    return count

if __name__ == "__main__":
    n, k = map(int, sys.stdin.readline().split())
    print(solution(n, k))

구현

머리속에 있는 알고리즘을 소스코드로 바꾸는 과정으로 별도 알고리즘으로 보기는 어려우나 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제됨.

C/C++에서는 정수형 종류에 따른 범위를 고려해야 한다.

문제

  • 상하좌우
    import sys

def solution(n, directions):
    pos = (1, 1)
    dic = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
    for direction in directions:
        nx, ny = pos[0] + dic[direction][0], pos[1] + dic[direction][1]
        if nx > n or nx < 1 or ny > n or ny < 1:
            continue
        pos = (nx, ny)
    return pos

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    directions = list(sys.stdin.readline().split())
    print(*solution(n, directions))
  • 시각
    import sys

def solution(n):
    count = 0
    for hour in range(n+1):
        for min in range(60):
            for sec in range(60):
                if '3' in str(hour) + str(min) + str(sec):
                    count += 1
    return count

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    print(solution(n))
  • 왕실의 나이트
    import sys

def solution(input_):
    directions = [(-2, 1), (-2, -1), (2, 1), (2, -1),
                  (1, 2), (1, -2), (-1, 2), (-1, -2)]

    x = ord(input_[0]) - ord('a')
    y = int(input_[1]) - 1
    count = 0

    for direction in directions:
        nx, ny = x + direction[0], y+direction[1]
        if 0 <= nx < 8 and 0 <= ny < 8:
            count += 1
    return count

if __name__ == "__main__":
    input_ = sys.stdin.readline().rstrip()
    print(solution(input_))
  • 게임 개발
    import sys

def solution(n, m, x, y, head, graph_):
    count = 1
    dic_heading = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
    turn_count = 0
    graph_[y][x] = -1

    while True:
        turn_count += 1
        head = (head - 1) % 4
        ny, nx = y + dic_heading[head][0], x + dic_heading[head][1]
        if graph_[ny][nx] == 0:
            x, y = nx, ny
            graph_[y][x] = -1
            count += 1
            turn_count = 0
        elif turn_count == 4:
            ny, nx = y - dic_heading[head][0], x - dic_heading[head][1]
            if graph_[ny][nx] == 1:
                break
            else:
                x, y = nx, ny
                turn_count = 0

    print(*graph_, sep="\n")
    return count

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    x, y, head = map(int, sys.stdin.readline().split())
    graph_ = [[] for _ in range(n)]
    for idx in range(n):
        graph_[idx] = list(map(int, sys.stdin.readline().split()))
    print(solution(n, m, x, y, head, graph_))

DFS/BFS

자료 구조

데이터를 표현하고 관리하고 처리하기 위한 구조
Stack: FILO, Queue: FIFO
→ python에서는 collections 모듈의 deque 사용

Recursive function
종료 조건을 명시!
재귀함수는 점화식을 코드로 옮기는 경우에 용이하며 코드가 간결해짐.

Graph

Node와 edge로 표현되는 구조.
두 node가 edge로 연결되어 있을 때 두 node는 인접하다라고 말한다.

INF = float('inf')
# adjacent matrix
[[0, 7, 5],
[7, 0, INF],
[5, INF, 0]]

# adjacent list
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

Adjacent matrix는 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨. 노드 간 연결 확인은 빠르다.
Adjacent list는 메모리가 비교적 적게 사용되지만, 특정 노드 간 연결 확인은 비교적 느리다.

DFS(Depth-First Search)

스택 자료구조 / 재귀함수 이용해 구현

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 2번의 과정을 더 수행할 수 없을 때까지 반복
def dfs(graph, v, visited):
	visited[v] = True # 현재 노드 방문 처리
	print(v, end=' ')
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

# graph는 adjacent list
# v는 시작 노드
# visited는 방문 처리 여부

BFS(Breadth First Search)

가까운 노드부터 탐색. 큐 자료구조 이용.

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드 인접 노드 중 방문하지 않은 노드 방문처리 및 큐에 삽입
  3. 2번의 과정을 더 수행할 수 없을 때까지 반복

일반적인 경우 BFS가 DFS보다 수행 시간이 좋은 편.

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		print(v, end=' ')
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

문제

  • 음료수 얼려먹기

    • BFS

      import sys
from collections import deque

def solution(n, m, graph):
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                fill(graph, i, j, n, m)
                count += 1

    return count

def fill(graph, i, j, n, m):
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([])
    graph[i][j] = 1
    queue.append((i, j))
    while queue:
        y, x = queue.popleft()
        for dir in dirs:
            ny, nx = y+dir[0], x + dir[1]
            if 0 <= ny < n and 0 <= nx < m:
                if graph[ny][nx] == 0:
                    graph[ny][nx] = 1
                    queue.append((ny, nx))
    return graph

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n)]
    for idx in range(n):
        graph[idx] = [int(x) for x in sys.stdin.readline().rstrip()]
    print(solution(n, m, graph))

    • DFS

      import sys

def solution(n, m, graph):
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                fill(graph, i, j, n, m)
                count += 1
    return count

def fill(graph, i, j, n, m):
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    graph[i][j] = 1
    for dir in dirs:
        ny, nx = i + dir[0], j + dir[1]
        if 0 <= ny < n and 0 <= nx < m:
            if graph[ny][nx] == 0:
                fill(graph, ny, nx, n, m)
    return graph

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n)]
    for idx in range(n):
        graph[idx] = [int(x) for x in sys.stdin.readline().rstrip()]
    print(solution(n, m, graph))
  • 미로 탈출

    • BFS

      import sys
from collections import deque

def solution(n, m, graph):
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([])
    queue.append((0, 0))

    while queue:
        y, x = queue.popleft()
        for dir in dirs:
            ny, nx = y + dir[0], x + dir[1]
            if ny < 0 or ny >= n or nx < 0 or nx >= m:
                continue
            if graph[ny][nx] <= graph[y][x] + 1 and graph[ny][nx] != 1:
                continue
            else:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((ny, nx))
    return graph[n-1][m-1]

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n)]
    for idx in range(n):
        graph[idx] = [int(x) for x in sys.stdin.readline().rstrip()]
    print(solution(n, m, graph))

    • DFS

      import sys

def solution(n, m, graph):
    dfs(0, 0, n, m, graph)
    return graph[n-1][m-1]

def dfs(x, y, n, m, graph):
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dir in dirs:
        ny, nx = y + dir[0], x + dir[1]
        if ny < 0 or ny >= n or nx < 0 or nx >= m:
            continue
        if graph[ny][nx] <= graph[y][x] + 1 and graph[ny][nx] != 1:
            continue
        else:
            graph[ny][nx] = graph[y][x] + 1
            dfs(nx, ny, n, m, graph)

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n)]
    for idx in range(n):
        graph[idx] = [int(x) for x in sys.stdin.readline().rstrip()]
    print(solution(n, m, graph))
profile
GGG
GGG
다음 포스트

[코딩테스트] 이것이 취업을 위한 코딩테스트다 2

0개의 댓글