방구석프로의 이야기

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

문제 해결을 위한 과정

구현 유형에 해당하는 문제 입니다. 조건 자체는 복잡할 수 있으나, 조건에 유의하여 소스코드를 작성하면 해결할 수 있었습니다. (저의 경우 possible.append()를 graph[nx][ny] == 0 즉 비어있을 때만 해줘야하는데 실수로 그렇지 않은 경우에도 append할 수 있게 작성하여 여러번 시도하여 해결했습니다.)

소스코드

a = int(input())
n = a * a
graph = [[0] * a for _ in range(a)]
friend = []
happy = [0, 1, 10, 100, 1000]
for _ in range(n):
  friend.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(len(friend)):
  main = friend[i][0]
  bestFriend = friend[i][1:5]
  possible = []
  
  for j in range(a):
    for k in range(a):
      cnt = 0
      emptyCnt = 0
      if graph[j][k] == 0:
        for l in range(4):
          nj = j + dx[l]
          nk = k + dy[l]
          if nj < 0 or nk < 0 or nj >= a or nk >= a:
            continue
          if graph[nj][nk] in bestFriend:
            cnt += 1
          elif graph[nj][nk] == 0:
            emptyCnt += 1
            
        possible.append((cnt, emptyCnt, j, k))
  possible.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
  j, k, x, y = possible[0]
  graph[x][y] = main
  
ans = 0
for i in range(a):
  for j in range(a):
    for k in range(len(friend)):
      if graph[i][j] == friend[k][0]:
        bestFriend = friend[k][1:5]
        cnt = 0
        for l in range(4):
          nx = i + dx[l]
          ny = j + dy[l]
          if nx < 0 or ny < 0 or nx >= a or ny >= a:
            continue
          if graph[nx][ny] in bestFriend:
            cnt += 1
        ans += happy[cnt]
print(ans)

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

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 해결할 수 있는 문제였습니다. 먼저 문제를 잘 보시면 리스트에서 가장 작은 값 2개를 빼온 후 그 둘의 합을 구합니다. 그 후 합들을 리스트에 넣어줍니다.

문제 해결을 위한 팁

이때 가장 작은 값을 두 개 빼오는 과정은 sort()를 이용하여 구할 수도 있고 우선순위 큐를 이용할 수 있습니다. 파이썬의 우선순위 큐는 최소합으로 구현이 되어있기 때문에 단순히 우선순위 큐에서 빼내기만 하면 가장 작은 값을 빼올 수 있습니다.

소스코드

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

문제 해결을 위한 과정

이 문제는 제가 예전에 포스팅한 BFS의 코드를 암기하고 숙지하고 있다면 쉽게 해결할 수 있는 문제였습니다. (https://bgspro.tistory.com/15?category=981927) 먼저 문제에서 입력으로 주어진 그래프를 생성합니다. 그 후 1번 노드에 대해서 BFS를 수행합니다. 이렇게 BFS를 수행하면서 방문하는 노드마다의 개수를 하나씩 센 후 그 결과를 출력하면 됩니다. 

소스코드

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

문제 해결을 위한 과정

이 문제의 경우 난이도는 실버 1티어 이지만 DFS, BFS의 개념만 정확하게 알고 있으면 쉽게 해결할 수 있는 문제였습니다. 상, 하, 좌, 우 4가지 방향으로 움직일 수 있기 때문에 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]로 방향 리스트를 생성합니다. 그 후 bfs함수를 구현합니다. 

소스코드 - python

소스코드 - c++

https://programmers.co.kr/learn/courses/30/lessons/42889

문제 해결을 위한 과정

이 문제의 경우 그다지 어렵지 않은 문제였고 파이썬의 내장 함수인 count를 이용하여 쉽게 해결을 할 수 있었습니다. 

for문을 이용해서 단계의 사람의 수를 구하고 리스트에 튜플의 형태로 (단계의 사람 수 /전체 사람 수, 전체 사람 수) 추가합니다. 그 후 전체 사람 수에서 단계의 사람 수를 빼줌으로써 다음 단계에서는 이전 단계에서의 사람의 수를 제외시켜 줍니다. 이렇게 리스트에 추가를 해 준 후 문제에서의 조건처럼 다음과 같이 정렬해줍니다. 

1. 실패율의 내림차순대로

2.. 실패율이 같으면 스테이지의 번호를 오름차순으로 

문제 해결을 위한 팁

이 문제의 경우 테스트 케이스중에 만약 5단계라면 3단계에서 모두 실패하고 4단계, 5단계에 도달하지 못하는 경우가 있습니다. 따라서 count를 이용하여 해당 단계에 도전하는 사람이 없는 경우 분모가 0인 divide by zero가 발생하지 않도록 실패율을 0으로 해당 리스트에 추가해줍니다.

소스코드

개념

사이클 판별 알고리즘은 앞선 포스팅인 서로소 집합 알고리즘을 이용한 알고리즘입니다. 그림과 같이 노드 1, 2, 3이 있고 각각의 연결이 서로를 가리키게 되어있다고 가정합시다.

이 경우 앞선 서로소 집합 알고리즘의 find_parent를 이용하면 노드1의 부모는 노드 1, 노드 2의 부모는 노드 1, 노드 3의 부모는 노드 1로 모든 노드의 부모가 각각 노드 1 임을 확인할 수 있습니다. 따라서 사이클이 발생을 했다는 것을 알 수 있습니다. 그러므로 사이클 판별 알고리즘의 경우 두 노드를 확인한 후 부모 노드가 다르다면 union_parent 함수를 수행해주고 부모 노드가 같다면 사이클이 존재한다는 것을 출력한 뒤 함수를 종료하면 되는 것입니다. 소스코드는 다음과 같습니다.

소스코드

개념

서로소 집합 알고리즘은 말 그대로 어떠한 숫자들의 서로소인지 아닌지의 관계를 나타내는 알고리즘이라고 생각하시면 될 것 같습니다. 먼저 1, 2라는 집합과 3, 4라는 집합이 있다고 가정합시다. 이 두 집합은 교집합이 없기 때문에 서로소 관계라고 할 수 있습니다. 우리가 구현할 서로소 집합 알고리즘의 경우 부모를 확인하는 함수, 합치기 연산을 수행하는 함수로 크게 두 부분으로 나눌 수 있습니다. 단 부모를 확인하는 함수에서 경로 압축 기법을 사용하게 되면 보다 빠른 시간 복잡도로 문제를 해결할 수 있기 때문에 외워주는 것이 좋을 것 같습니다. 

소스코드

본 소스코드는 나동빈님의 이것이 취업을 위한 코딩테스트이다. 를 참조하였습니다.

개념

플로이드 와샬 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로를 구할 때 사용하는 알고리즘입니다. 그러나 한 지점에서 다른 특정 지점까지 최단 거리를 구하는 다익스트라 알고리즘과 달리 플로이드 와샬 알고리즘은 모든 지점에서 다른 모든 지점까지의 경로를 구하는데 사용하는 알고리즘입니다. 플로이드 와샬 알고리즘은 어떠한 지점에서 다른 지점으로 갈 때 거쳐 가는 노드를 탐색한 후 distance 리스트를 갱신하는 식으로 구현합니다. 플로이드 와샬 알고리즘의 경우 구현이 다익스트라에 비해 쉽다는 단점이 있지만 O(ElogV)의 시간 복잡도를 가지는 다익스트라 알고리즘과 달리 O(N^3)의 시간 복잡도를 가지기 때문에 사용할 수 있는 조건이 매우 한정적입니다. 따라서 문제에서 주어진 N의 범위를 잘 확인한 후 어떤 알고리즘을 사용할지 결정을 해야 합니다.  그럼 그림을 통해 알아봅시다.

먼저 이차원 리스트를 만든 후 모든 원소에 대해서 무한으로 초기화를 합니다. 그 후 자기 자신의 노드로 가는 최단 경로는 0 이기 때문에 0을 대입해 줍니다. 또한 각각의 노드에서 이동할 수 있는 노드들에 거리를 대입해 줍니다. 그러면 다음과 같은 표가 만들어 집니다. 

그 후 거쳐가는 노드들을 고려해 줍니다. 예를 들어 1번 노드에서 3번 노드로 가는 경우를 봅시다. 위의 표에서 해당 하는 칸은 즉 1행 3열은 INF로 초기화가 되어있습니다. 그러나 1번 노드에서 4번 노드를 거친 후 3번 노드로 가면 8 이라는 경로가 나오게 됩니다. 따라서 이런 식으로 어떠한 노드에서 다른 노드로 갈 때 거쳐가는 노드를 확인한 후 최솟값으로 대입을 해주면 다음과 같습니다. 

소스코드