[week01/03.19]TIL

하루 한줄 요약

하루도 짧고 일주일도 짧아요...

오늘 공부한 내용

• N-Queen
• 백준 종이자르기, 외판원 순회,
• JS 입출력, 조건문, 반복문

새로 배우게 된 내용

N-Queen 2회차

N = int(input())
count = 0
pos = [0] * N
flag_col = [False] * N
flag_diagonal_up = [False] * (2 * N - 1)
flag_diagonal_down = [False] * (2 * N - 1)

def put():
    global count
    count += 1

def solve(row):
    if row == N:  # 모든 행에 대해 퀸을 놓았으면 카운트 증가
        put()
        return
    
    for col in range(N):
        if not flag_col[col] and not flag_diagonal_up[row + col] and not flag_diagonal_down[row - col + (N - 1)]:
            pos[row] = col
            flag_col[col] = flag_diagonal_up[row + col] = flag_diagonal_down[row - col + (N - 1)] = True
            solve(row + 1)  # 다음 행으로 이동
            flag_col[col] = flag_diagonal_up[row + col] = flag_diagonal_down[row - col + (N - 1)] = False  # 백트래킹

solve(0)
print(count)

일단 큰 그림은 그릴 수가 있게 되었다.
3개의 큰 규칙을 매 열에 퀸을 두면서 확인한다 고 한줄 요약 할 수 있겠다.

1. 같은 열/행에 퀸이 있으면 안됨.
2. 같은 대각선 ↗️ 에 퀸이 있으면 안됨.
3. 같은 대각선 ↘️ 에 퀸이 있으면 안됨.

따라서 1열에서 1행에서 N행 까지 퀸을 놓아보고
2열에 넘어갔을 때 위의 3가지 규칙을 어기지 않는 곳에 퀸을 놓고
3열로 넘어갔을 때 위의 3가지 규칙을 어기지 않는 곳에 퀸을 놓는 식이다.

이해가 안되었던 부분은 그럼 만약 규칙을 만족하는 곳이 없다면? 이었다.
이때 등장하는 개념이 바로 백트래킹!

• 백트래킹
  쉽게 말해서 조건을 만족하지 않으면 되돌아 가는 것!

1. (0,1) 퀸 배치 ✅
2. (1,3) 퀸 배치 ✅
3. (2,0) 불가능 ❌ (같은 열에 퀸 있음)
4. (2,2) 불가능 ❌ (대각선 충돌)
5. (2,3) 불가능 ❌ (같은 열에 퀸 있음)
6. 되돌아가기 🔄 (1,3) 제거 ❌
7. (1,2) 퀸 배치 ✅

이런 flow로 간다고 이해했다.

백준 - 종이자르기, 외판원 순회

• 종이자르기

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

나는 이전에 푼 문제였던 직사각형에서 탈출(1085번) 문제처럼 풀려고 자르는 선들의 교점을 찾았는데
애초에 접근 방식이 틀렸었다.

그림을 그려보니 내가 구해야할 것은 결국 사각형의 변의 길이 였고
그 변의 길이로 만들 수 있는 사각형 중 가장 큰 값을 리턴하면 되는 간단한 문제...였다.

• 외판원 순회
  일단 순열을 통해 방문하는 모든 경로를 완전탐색으로 찾고
  각 경우마다 비용을 더해서 최솟값을 갱신해가며 정답을 맞히긴 했다.

from itertools import permutations
import sys
input = sys.stdin.readline

# 1. 입력받기
N = int(input())
permut = list(permutations(range(1, N)))   # 도시 방문 순서 순열로 완전탐색
cities = []

for i in range(N):
  city_list = list(map(int, input().split()))
  cities.append(city_list)
# 2. 최소값 할당할 변수 선언
min_cost = float('inf')

# 출발지, 리스트를 인자로 받는 함수
# Cycle 도는 모든 경로 계산(순열로) => 각 경로마다 가격을 리턴
# Cycle => 출발지 => 출발지 + 모든 노드 방문

for perm in permut:
  total_cost = 0 # 각 경로별 비용
  valid = True
  
  # 출발점은 0 
  start = 0
  for next_city in perm:
    if cities[start][next_city] == 0:
      valid = False
      break
    total_cost += cities[start][next_city]
    start = next_city
  
  # Cycle 이니 마지막 방문도시에서 다시 돌아가야함
  if valid and cities[start][0] != 0:
    total_cost += cities[start][0]
    min_cost = min(min_cost, total_cost)

print(min_cost)

다만, 완전탐색의 순열이 시간복잡도가 O(N!)이기 때문에,
N이 20, 30만 되어도 연산횟수가 어마무시 해진다.
따라서 이를 더 빠르게 풀 수 있는 방법을 찾아보니
DFS 와 백트래킹을 조합하여 풀면 가능하다고 한다.
DFS도 크게 보면 완전탐색이기에 공부하려 했으나 3주차에 배우기에...^^

JS로도 백준 시작

파이썬으로 푼 문제들을 JS로도 풀기 시작했다.
입출력부터 다시 차근차근 배운다는 마음으로 찾아보고 문제를 풀고 있다.

• fs모듈

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

• readline 모듈

/* readline Module */

// 문제 풀이
function solution(input) {
	

  // 답변 출력
	console.log(input);

}



/* readline Module */
const readline = require("readline");
const rl = readline.createInterface({

	input: process.stdin,
    output: process.stdout,

});

 
let input;

rl.on("line", function (line) {
    
    input = line;           // 입력받은 문자열, line
    input = parseInt(line); // 형변환, parseInt
    rl.close();             // 입력 종료

}).on("close", function () {

    solution(input); // 문제 풀이 함수 호출
    process.exit();  // 프로세스 종료

});

switch문엔 조건식을 쓸 수 없다

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

이 문제에서 처음에는

switch (score) {
  case score >= 90:
    console.log("A")
    break
  case score >= 80:
    console.log("B")
    break
  case score >= 70:
    console.log("C")
    break
  case score >= 60:
    console.log("D")
    break
  default:
    console.log("F")
    break
}

이렇게 switch문으로 풀려고 했는데 switch문은 조건식 검사가 불가능하고
그냥 if~else 문으로 풀어야 했다.

const fs = require('fs');
const input = fs.readFileSync('input.txt').toString().trim();

score = parseInt(input);

if (score >= 90) {
  console.log("A")
} else if (score >= 80) {
  console.log("B")
} else if (score >= 70) {
  console.log("C")
} else if (score >= 60) {
  console.log("D")
} else {
  console.log("F")
}

배열 요소 반복하는 방법

만약 아래와 같은 배열이 있다면

arr = [[[1, 1], [2, 3], [3, 4], [9, 8], [5, 2]]

• for...of

for (let cases of arr) {
  let A = cases[0]
  let B = cases[1]
  console.log(A + B)
}

• forEach

arr.forEach(pair => {
   let A = pair[0]
   let B = pair[1]
   console.log(A + B)
})

위 두가지 방법으로 배열의 요소를 반복하면서 사용 가능하다

• for...in?
  for in 문은 객체를 반복할때 사용한다.
  다만 배열도 객체이기 때문에 배열을 돌때 돌아가기는 하나 필요한 value값이 나오는게 아니라
  Index 값을 리턴한다는 것에 주의하자.

공부하면서 어려웠던 점

백준을 풀때 입출력을 확인하고,
어떤 과정을 거쳐야 입력에서 출력이 나오는지 고민해보자.
의외로 이걸 많이 놓쳐서 많은 문제를 풀지 못했던 것 같다.

알고리즘은 아래 네모에 들어갈 말이니까!