NISSO

체스를 모르는 나에겐 문제 내용이 너무 부족했다. 서로 공격할 수 없는다는 게 어떤 건지 몰랐다. 체스도 모르고 백트래킹도 잘 모르니 유튜브에 검색하다가 좋은 강의 영상을 봤다. 자세하게 알려주고 기본 설명과 구현, 두가지 영상으로 나뉘어있다. 주니온TV아무거나연구소 - 파이썬으로 배우는 알고리즘 기초: 18. 백트래킹과 n-Queens 문제 문제 설명을 간단히 하자면, 크기가 N*N인 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 구하는 문제다. 이 때, 퀸은 다른 걸 공격할 수 없도록 같은 행, 열, 대각선 외의 위치에 놓아야 한다. (x1,y1), (x2,y2)가 있을 때 |x1-x2| = |y1-y2| 면 같은 대각선상에 있다. 풀어본 결과, 내 결론은 파이썬으로 푸는 건 거의 불가능..

나의 첫 백트래킹 문제.. 내 힘으로 못 풀었다. 검색을 통해 공부하면서 이해하고 두가지 방법을 알게 됐다. > 1번째 방법 a,b = map(int, input().split()) l = [0 for _ in range(b)] def back(a,b,i=0): if b==i: print(*l) return for j in range(a): l[i] = j+1 back(a,b,i+1) back(a,b) 이게 처음 푼 코드 재귀를 이용해 해결하는 방법이다. 6번째줄 print(*l)은 처음 알게 된 건데, 반복문을 쓰지 않고 리스트 내 모든 원소를 공백으로 구분해서 출력할 수 있다. 다른 사람들 답을 보면서도 항상 나왔던 건데, 찾아보지 않다가 이제야 알게 됐다. a = [1,2,3,4] for i in ..

a,l = int(input()), [] for _ in range(a): l.append(int(input())) l.sort() from collections import Counter c = Counter(l).most_common() m = c[0][0] if len(c)

해당 문제는 재귀 카테고리에 있어서 재귀함수로 풀었다. 바로 전 문제가 팩토리얼 문제여서 재귀로는 쉽게 풀었다. def fibo(n=int(input()), i=1): if n>2: return fibo(n-1) + fibo(n-2) return 0 if n==0 else 1 print(fibo()) 그리고 다른 코드를 구경(?)하는데 변수를 dp로 설정했더라. 알진 못해도 들어본 적은 있어서 바로 검색해봤다. DP는 동적계획법 (Dynamic Programming)으로 상향식 접근법이며 실행시간이 현저히 줄어든다는 장점이 있다. 이전에 계산한 값을 메모리에 저장해 다시 계산하지 않도록 하는 Memoization 기법을 사용한다. n = int(input()) dp = [j for j in range(n..

for문을 사용해 구현할 수도 있지만 백준 문제 카테고리가 재귀라서 재귀함수를 사용해봤다. 간단한 코드인데 혼자 힘으로는 못했고 서치로 알아냈다... 봤던 건데 실제로 안 써보니 까먹은 것 같다. def factorial(n=int(input())): if n>1: return n*factorial(n-1) return 1 print(factorial()) 최종 출력할 값을 fct로 놓고 곱할 값을 i로 놓고 별 짓을 다 해봤지만 시간 낭비였다. 재귀함수에 n을 곱할 생각을 못했다. 아무튼 간단하고도 필수적으로 알아야할 코드니 다신 잊어먹지 않겠다. + 재귀나 for문 외에 더 쉬운 방법이 있다. import math n = int(input()) print(math.factorial(n)) 파이썬 표준..

처음으로 백준 문제를 풀어보려고 쉬운 것부터 도전해보는데 이 문제에만 20분을 쏟았다. 예제 답도 완벽했는데 도대체 뭐가 문제였을까. 문제 1. 프로그래머스만 이용해본 입장에서, 함수 형식이 아니라 input()으로 그 때 그 때 입력받는 방식인 걸 몰랐다. 특히 예제 첫줄만 a로 받고 아래를 모두 b로 한 번에 받았는데, 서치해보니 한 줄씩 받고 바로 출력하는 것이었다. 문제 2. 반례가 있다. 1 1 0 답은 0.000% 인데 100.000%가 나왔다. 정말 작은 실수였다.. 반복문에 b 전체를 받은 것. b[0]은 학생 수라서 b[1:]로 계산해야 맞는 거다. 뒷부분은 b[1:]로 잘해놓고 여기선 생각도 못했다. 다음은 수정한 내 코드다. a = int(input()) for _ in range(a..