파이썬32

• 

  백준 알고리즘 9663번: N-Queen (Python) 문제 정보 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 핵심 1. 백트래킹을 사용하되, 시간복잡도를 고려할 것 퀸을 놓을 수 있는 경우의 수는 어마무시하기 때문에, 시간복잡도를 고려해주지 않으면 엄청난 실행시간이 소요된다 2. 2차원 배열을 사용하지 말것 2차원 배열을 사용하면 직관적으로 퀸이 놓을수 있는 위치를 파악할 수는 있지만 매우 비효율적인 방법이다. 2차원 배열을 사용하지 않고도, 1차원 배열로 문제를 풀이할 수 있다 (아래에서 설명) 3. Python으로 굳이 제출하지 말것 이건 백준 알고리즘 질문게시판에서 본.. 알고리즘/Python 2023. 6. 17.

• 

  백준 알고리즘 9095번: 1,2,3 더하기 (Python) 문제 정보 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 핵심 1, 2, 3 총 3개의 정수로 0 알고리즘/Python 2023. 6. 15.

• 백준 알고리즘 1182번: 부분수열의 합 (Python) 문제 정보 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 핵심 풀이과정은 크게보면 두가지가 있는것 같다 첫번째는 정수 배열을 두개로 나눠서 백트래킹 두번째는 안나누고 한 배열로 백트래킹 확실히 정수 배열을 두개로 나누고, 백트래킹을 한 첫번째 풀이가 더욱 간단하고 실행시간도 짧았다 하지만 첫번째 풀이는 아직까지 완벽하게 이해하기 힘들었고, 두번째 풀이는 내가 직접 풀이했기 때문에 설명할 수 있을것 같다. 그냥 사실 간단한 문제이다. 중복을 고려하지 않은 조합을 찾는 것이지.. 알고리즘/Python 2023. 6. 15.

• 백준 알고리즘 6603번: 로또 (Python) 문제 정보 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 핵심 백트래킹, DFS를 사용하여 풀이할 수 있는 문제이다 조합 문제기 때문에, 파이썬의 라이브러리인 combinations 을 사용하여 풀이할 수 있지만 대부분의 코딩 테스트에서 이와 같은 라이브러리를 허용해 주지 않을 확률이 높기 때문에 정석적인 풀이로 풀어보았다 풀이 시간은 조금 걸렸고, DFS 문제가 거의 처음이거나 풀이한 지 많이 오래 되었기 때문에 그런 것 같다 풀이 import sys def DFS(L, startWith): i.. 알고리즘/Python 2023. 6. 13.

• 백준 알고리즘 5430번: AC (Python) 문제 정보 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 핵심 R(뒤집기) 와 D(버리기) 함수를 사용자가 입력한 순서대로 수행 후 배열의 결과 출력하기 여기서 R 작업을 수행할 때 배열을 직접 reverse 하는 건 절대 안된다고 생각,, (엄청나게 비효율적임) 나는 cur 변수를 사용하여 현재 커서의 위치를 표현하고, lcur(left cur), rcur(right cur) 을 사용하여 뒤집지 않은 상태에서의 D(버리기) 작업과 뒤집은 상태에서의 D 작업을 다음과 같이 수행하였다 if isReverse: rcur -= 1 else: lcur += 1 R(뒤집기.. 알고리즘/Python 2023. 6. 13.