🍈 백준 6603. 로또

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

알고리즘 분류

• 수학
• 조합론
• 백트래킹
• 재귀

풀이

• 로또 번호 총 49개(1~49)
• 6개 뽑음
• 로또뽑기 최고전략
  • 집합으로 만들 로또 번호의 개수 = k (6이상의 수)
  • k개의 숫자중 6개를 뽑아 만들 수 있는 모든 경우의 수를 구함 = kC6
• 각 테스트 케이스 총 출력 행수는 = kC6
• 6개의 길이로 만들 수 있는 모든 경우의 수를 출력해보자.

코드

def cal(depth, idx):
    if depth == 6: # out의 길이가 6일때
        print(*out) # out 내의 값을 모두 출력
        return

    for i in range(idx, k): # idx부터 k까지 반복
        out.append(S[i])
        cal(depth + 1, i + 1) # 재귀함수
        out.pop() # out 리스트를 비움

while True: # 테스트 케이스에 대한 반복문
    # k와 S 입력받기
    array = list(map(int, input().split()))
    k = array[0]
    S = array[1:]
    
    # 각 테스트 케이스에 대한 경우의 수 반복문
    out = []
    dfs(0, 0)
    if k == 0: # 0을 입력받으면 탈출
        exit()
    print()

어려운 점

• 재귀함수와 반복내의 동작원리를 이해하는데 어려움을 겪었다.

---

🍈 백준 6603. 외판원 순회 2 (미해결)

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력 1

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1

35

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹
• 외판원 순회 문제

풀이

• 도시 = 1~N
• 도시 사이는 길로 이어져 있다. (길 없을 수도 있음)
• 한 도시를 출발하여 맨 마지막에 다시 원래 도시로 돌아오는 순회 여행 경로 계획
• 각 도시는 한번만 경유할 수 있다.
• 최소 비용 여행 계획
• W[i][j] = 도시 i에서 도시 j로 가는데 드는 비용 (비용 대칭 X)

---

🍈 백준 16198. 에너지 모으기

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
x번째 에너지 구슬을 제거한다.
Wx-1 × Wx+1의 에너지를 모을 수 있다.
N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.
N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.
둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

예제 입력 1

4
1 2 3 4

예제 출력 1

12

예제 입력 2

5
100 2 1 3 100

예제 출력 2

10400

예제 입력 3

7
2 2 7 6 90 5 9

예제 출력 3

1818

예제 입력 4

10
1 1 1 1 1 1 1 1 1 1

예제 출력 4

8

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

• 에너지 구슬 개수 = N
• i번째 에너지 구슬의 무게 = Wi
• 에너지 모으는 방법
  • 처음과 마지막 구슬을 제외한 x번째 구슬을 골라 제거한다.
  • (x-1번째 구슬) x (x+1번째 구슬)만큼 에너지 축적
• 에너지 최댓값 구하기
• 최댓값 주변의 구슬을 우선적으로 제거한다.
• 구슬이 2개일 때까지 재귀적으로 탐색
• i번째 구슬을 제거했을 때 나오는 에너지를 가지고 재귀적으로 탐색
• 재귀적 탐색을 통해 에너지를 모을 수 있는 모든 경우의 수를 탐색한다.

코드

def cal(x):
    global answer

    # 에너지를 모았다면 answer와 비교하여 초기화
    if len(w) == 2:
        answer = max(answer, x)
        return

    # 반복문을 통해 에너지 구슬을 확인
    for i in range(1, len(w) - 1):
        target = w[i - 1] * w[i + 1] # i번째 구슬을 제거했을 때 나오는 에너지

        # 백트래킹
        v = w.pop(i) # 에너지 구슬 제거
        back_tacking(x + target) # 제거된 구슬로 에너지를 재귀적으로 탐색
        w.insert(i, v) # 제거한 에너지 구슬 추가


N = int(input())
w = list(map(int, input().split()))
answer = 0
cal(0)
print(answer)

---

🍈 백준 14888. 연산자 끼워넣기 (미해결)

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1

2
5 6
0 0 1 0

예제 출력 1

30
30

예제 입력 2

3
3 4 5
1 0 1 0

예제 출력 2

35
17

예제 입력 3

6
1 2 3 4 5 6
2 1 1 1

예제 출력 3

54
-24

힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.

• 최댓값: 1-2÷3+4+5×6
• 최솟값: 1+2+3÷4-5×6

---

🍈 백준 2002. 추월

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'-'Z')와 숫자('0'-'9')로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

예제 입력 1

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1

예제 입력 2

5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

예제 출력 2

3

예제 입력 3

5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN

예제 출력 3

2

알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵

풀이

• 추월한 차량을 구하는 문제
• 차의 대수 = N
• 2 ~ N+1행 = 들어간 차(대근)
• N+2 ~ 2N+1행 = 나오는 차(영식)
• 들어간 차와 나오는 차를 비교했을 때 나가는 차의 순번이 빨라진 경우

코드

n = int(input())
in_car = {}
out_car = []
cnt = 0

# 반복문을 통해 들어간 차를 딕셔너리로 입력 받음
for i in range(n):
    in_car[str(input().rstrip("\n"))] = i

# 반복문을 통해 나간 차를 리스트에 입력 받음
for _ in range(n):
    out_car.append(str(input().rstrip("\n")))

# 반복문을 통해 먼저 들어갔다 나온 차량보다 더 빨리 나온 차량이 있는지 확인
for j in range(n - 1):
    for k in range(j + 1, n):
        # 제일 먼저 나간 차의 들어간 순번 > 그 다음으로 나간 차의 들어간 순번 -> 추월했다는 뜻
        if in_car[out_car[j]] > in_car[out_car[k]]:
            cnt += 1
            break
print(cnt)

---

🍈 백준 16457. 단풍잎 이야기 (미해결)

문제

리유나와 라가는 메이플스토리라는 노동을 즐겨 한다. 메이플스토리에서는 키셋팅을 할 수 있는데, 키셋팅을 하면 원하는 키를 눌러서 원하는 스킬을 쓰게 할 수 있다.

리유나와 라가는 원래 좋은 친구였다. 리유나는 레벨이 225인데, 라가는 레벨이 202밖에 되지 않는다. 라가는 리유나를 질투해서 메이플 레벨을 따라잡으려고 했다. 그래서 리유나가 메이플을 하지 못하도록 키보드에 있는 키를 n개만 빼고 모두 망가뜨려버렸다!

하지만 리유나는 메이플에 이미 인생을 팔아버렸기 때문에, 키가 망가져도 일간 퀘스트를 계속해야만 했다! 그래서 2n개의 스킬들 중에서 n개를 적절히 키에 배치해서 어떻게든 일간 퀘스트를 해야만 했다!

일간 퀘스트는 다음과 같이 진행된다. m개의 퀘스트들이 주어진다. 각각의 퀘스트에서는 k개의 스킬을 사용해야 한다. 만약 스킬을 사용할 수 없다면 그 퀘스트는 수행할 수 없다고 본다.

리유나는 n개의 키에 스킬들을 배치하려고 한다. 실제 게임에서는 키셋팅을 마음대로 할 수 있고, 키셋팅을 하지 않아도 더블 클릭으로 스킬을 사용할 수 있지만, 여기서는 키셋팅을 한번 설정하면 그 날은 키셋팅을 다시 바꿀 수 없고 더블 클릭으로 스킬을 사용할 수 없다고 가정하다. 이 때 어떤 스킬들을 배치해야 가장 많은 양의 일간 퀘스트를 깰 수 있는지 구하여자.

입력

첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다.
둘째 줄부터 m개의 줄에는 각각의 퀘스트에서 사용해야 하는 스킬들이 나온다. 스킬들의 이름은 1에서 2n까지의 정수로 주어진다.

출력

첫째 줄에 가장 최적의 키배치를 했을 때 최대로 깰 수 있는 퀘스트의 개수를 출력한다.

예제 입력 1

3 4 2
1 3
1 2
2 3
3 6

예제 출력 1

3

3개의 키에 각각 1, 2, 3을 배치해면 '1 3'퀘스트와 '2 3'퀘스트, '1 2'퀘스트를 클리어 할 수 있기 때문에 최적의 배치이다. 따라서 최고로 클리어할 수 있는 퀘스트의 개수는 3개이다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

• 리유나가 쓸 수 있는 키의 개수 = n
• 스킬 개수 = 2n
• 퀘스트 개수 = m
• 퀘스트 만족을 위한 스킬 개수 = k
• 주어진 퀘스트에서 사용해야 하는 스킬들 중 가장 많은 빈도로 나온 스킬들을 위주로 배치

코드

---

🍈 백준 10597. 순열장난 (미해결)

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

출력

복구된 수열을 출력한다. 공백을 잊으면 안 된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

예제 입력 1

4111109876532

예제 출력 1

4 1 11 10 9 8 7 6 5 3 2

알고리즘 분류

• 백트래킹

풀이

• 순열이란 서로다른 n개의 수 중에서r개를 택하여 일렬로 배열하는 경우를 말한다.

• 순열의 개수 = N

• 한 자리수

  • 0이 아니여야 한다.
  • 리스트에 없어야 한다.

• 두 자리수

  • N보다 작거나 같아야 한다.
  • 리스트에 없어야 한다.
  • 10의 자리수가 0이 아니여야 한다.

---

❓ 백트래킹 알고리즘이란?

✅ 백트래킹 이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

• 최적화 문제와 결정 문제를 푸는 방법이 된다.

✅ 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.

• 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

  • 가지치기: 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다.

✅ 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 함로 처리가 불가능 할 수도 있다.

• 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

[요약]

• 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴본다.
• 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 한다.
• DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.