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

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 통해 해결할 수 있는 문제였습니다. Queen의 경우 같은 열 혹은 같은 행에 있거나 같은 대각선에 있는 곳을 이동할 수 있습니다. 따라서 다음 그림과 같이 퀸을 놓을 수 있습니다. (단, n이 4 인 경우)

같은 행에는 다시 queen을 위치할 수 없고, 시간복잡도를 위해 2차원 배열을 1차원 배열로 단순화해서 표시할 수 있습니다. 위 그림의 경우는 다음과 같습니다. arr = [1, 3, 0, 2] 해석하면 0번째 인덱스(행)의 1번째 인덱스(열), 1번째 인덱스(행)의 3번째 인덱스(열), 2번째 인덱스(행)의 0번째 인덱스(열), 3번째 인덱스(행)의 2번째 인덱스(열)에 위치했다는 뜻입니다. 이를 완전탐색 식으로 표현하면 아래의 코드와 같습니다. 중요한 검사 로직은 같은 열에 있는지(check함수의 첫 번째 if문), 대각선에 있는지(check 함수의 두 번째 if문)으로 검사합니다. 이때 같은 행인 경우는 존재할 수 없는데 배열의 인덱스 자체가 행을 의미하기 때문에 같은 행에는 queen이 무조건 없습니다.

소스코드

n = int(input())
arr = [0] * n
count = 0

def dfs(depth):
  global count
  if depth == n:
    count += 1
    return

  for i in range(n):
    arr[depth] = i
    if check(depth):
      dfs(depth + 1)

def check(col):
  for i in range(col):
    if arr[i] == arr[col]:
      return False
    elif abs(i-col) == abs(arr[i]-arr[col]):
      return False
  return True

dfs(0)
print(count)

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

문제 해결을 위한 과정

이 문제의 경우 역시 마찬가지로 구현 문제이므로 차분하게 조건을 작성하면 해결할 수 있었다. 돌리게 되는 톱니를 기준으로 좌측 영역, 우측 영역을 분리하여 각자 맞게 회전을 시켜주었다. 다만 이때 flagLeft(왼쪽에 맞물리는 부분) flagRight(우측에 맞물리는 부분)을 for문 내부에 그대로 넣어서 덮어진 값을 사용하게 되어 틀렸습니다. 를 받게 되었다. 따라서 tempFlagLeft, tempFlagRight로 분리하여 덮어씌워짐을 방지 하였다.

소스코드

arr = [[] for _ in range(4)]
for i in range(4):
   tempArr = input()
   for j in range(len(tempArr)):
       arr[i].append(int(tempArr[j]))
k = int(input())
moves = []
for _ in range(k):
    a, b = map(int, input().split())
    moves.append((a, b))

def turn_right(array):
    right = array[7]
    for i in range(6, -1, -1):
        array[i + 1] = array[i]
    array[0] = right

def turn_left(array):
    left = array[0]
    for i in range(0, 7):
        array[i] = array[i + 1]
    array[7] = left

for x in range(k):
    num, dir = moves[x]
    num -= 1 # index 맞추기 위함
    flagLeft = arr[num][6]
    flagRight = arr[num][2]
    if dir == 1:
        turn_right(arr[num])
    else:
        turn_left(arr[num])
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num-1, -1, -1):
        if tempFlagLeft != arr[i][2]:
            if tempDir == 1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
        else:
            break
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num + 1, 4):
        if tempFlagRight != arr[i][6]:
            if tempDir == -1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
        else:
            break

ans = 0
for i in range(len(arr)):
    if arr[i][0] == 1:
        if i == 0:
            ans += 1
        elif i == 1:
            ans += 2
        elif i == 2:
            ans += 4
        else:
            ans += 8
print(ans)

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

시간 복잡도는 속도에 관한 것이며 공간 복잡도는 메모리 사용량에 관한 것이다. 시간 복잡도는 연산 횟수로 구한다.

데이터의 개수가 n이하는 알고리즘 A가 유리하고 n이상은 알고리즘 B가 유리한것을 확인할 수 있다.
따라서 상황에 맞게 적절한 알고리즘을 택해야 한다. 다음의 코드를 살펴보자.

이 경우 최악의 시간복잡도는 O(N)이다. 최선, 평균, 최악이 있지만 최악을 기준으로 잡는다.
이번에는 이진 탐색(Binary Search)알고리즘을 보자. 순차 탐색에 비해 좋은 성능을 내지만 정렬이 되어있어야 한다는 제약 조건이 존재한다.

이진탐색 (Binary Search)

이진탐색을 먼저 그림으로 나타내면 다음과 같다.

이진탐색의 코드는 다음과 같다.

이 경우 최악의 시간 복잡도는 O(logN)이다.

각 빅 - 오 표기법들의 성능 비교

각 빅-오 표기법들의 성능은 다음과 같다.

순서대로 O(1) < O(logN) < O(N) < O(NlogN) < O(𝑁^2) < O(2^N) < O(N!) 이다.

개념

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

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

소스코드

개념

편집거리 알고리즘이란 두 문자열이 주어졌을 때 문자열을 비교하는 알고리즘입니다. 여기서 비교한다는 것은 삽입, 삭제, 교체 즉 3가지의 액션이 주어졌을 때 두 문자열이 같게 하기 위해 취할 수 있는 액션의 최솟값을 구하는 알고리즘이라는 것입니다. 예를 들어서 str1 = python, str2 = pyytthon 라 가정하고 문제를 해결해보겠습니다. 이 알고리즘은 다이내믹 프로그래밍 즉 dp의 일종이기 때문에 dp 테이블의 형태로 이차원 리스트를 구현하면 쉽게 해결할 수 있습니다. 

다음의 표를 봅시다.

먼저 str1을 행으로 str2를 열로 넣고 각 행과 열에 숫자를 넣은 상태입니다. 여기서 만약 p, p를 비교하는 경우 즉 2행 2열의 경우는 두 문자가 같기 때문에 좌측 위의 0이 그대로 2행 2열에 대입됩니다.

그러나 p, y와 같은 두 문자열이 다른 경우 즉 2행 3열의 경우 좌측, 좌측 위, 위 의 3가지 경우 중 최솟값에 1을 더한 값이 대입됩니다. 여기서는 최솟값이 2행 2열 즉 0 이기 때문에 0에 1을 더한 1이 대입됩니다. 그 과정을 전부 다 하면 다음과 같습니다.

이 표의 최우 측 하단의 값이 두 문자열을 비교한 후 서로 같게 하는 최소의 액션의 수입니다. python에 y뒤에 혹은 y앞에 y를 삽입하는 1번의 과정으로 pyyhton을 만들 수 있기 때문입니다.

소스코드

DFS란?

DFS 즉 Depth-Frist-Search는 영어를 해석한 그대로 깊이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다.

깊이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들 중 한 방향의 노드에 대해서 계속 파고 들어간다는 뜻 입니다. 그림 1을 보시면 이해가 더욱 쉽습니다. 

그림 1에서 노드 1을 시작점으로 DFS를 수행해보겠습니다. (위 예시에서 설명을 용이하게 하기 위해 낮은 숫자부터 방문한다고 가정하겠습니다.)

1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이 있지만 낮은 숫자인 2를 탐색합니다.(탐색:  1, 2)

2번을 탐색하고 난 뒤 갈 수 있는곳은 9 가 있습니다. 9를 탐색합니다. (탐색: 1, 2, 9)

9번을 탐색하고 난 뒤 갈 수 있는곳은 3, 4가 있지만 낮은 숫자인 3을 탐색합니다. (탐색: 1, 2, 9, 3)

3번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 9로 돌아온 후 4를 탐색합니다. (탐색: 1, 2, 9, 3, 4)

4번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 1로 돌아온 후 7을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7)

7번을 탐색하고 난 뒤 갈 수 있는곳이 6, 8, 이 있지만 낮은 숫자인 6을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6)

6번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 7로 돌아온 후 8을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8)

8번을 탐색하고 난 뒤 갈 수 있는곳은 5가 있습니다. 5를 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8, 5)

모든 곳을 탐색하였으므로 탐색을 종료합니다.

탐색이 되는 순서는 위와 같이 1, 2, 9, 3, 4, 7, 6, 8, 5입니다. DFS는 구현을 스택을 이용하여 합니다만 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서는 재귀의 형태로 구현을 하였고 저도 해당 코드를 인용하기 때문에 재귀를 이용하여 구현하겠습니다.

소스코드

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

문제

문제 해결을 위한 과정

이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.

from itertools import combinations

이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.

문제 해결을 위한 팁

None

소스코드

town.append(list(map(<span

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

문제

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answersreturn

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

문제 해결을 위한 과정

Level 1 문제로서 쉬운 문제였습니다. 단순하게 사람을 p1, p2, p3라 한다면 시험문제가 최대 10,000개 이므로 다음과 같습니다.

p1의 경우 [1, 2, 3, 4, 5] * 2000 

p2의 경우 [2, 1, 2, 3, 2, 4, 2, 5] * 2000 

p3의 경우 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000

여기서 p2의 경우 반복되는 숫자가 8 이므로 원래는 대략 1300을 곱해줘야 하지만 대략적인 값으로 2000번 반복을 시켰습니다. 그 후 입력으로 들어오는 answers 리스트와 비교하며 찍은 답이 정답이라면 각각의 카운트를 증가시켜 줍니다. 

문제 해결을 위한 팁

저의 경우는 정답자가 여러 명인 경우 오름차순으로 정렬을 하기 위해 임시 리스트 temp = []를 선언하였습니다. 그 후 각 사람별 맞힌 정답의 수와 각 사람(몇 번째 사람인지)에 대한 정보를 묶어서 temp리스트에 append 해주었습니다.

이 방법을 통해 문제를 많이 맞힌 사람별로 정렬이 가능하고 그 사람이 몇 번째 사람인지 조회도 가능합니다.

소스코드