전체 글127 백준 알고리즘 1037번: 약수 (Python) 문제 정보 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 핵심 간단한 수학적 지식이 있다면 풀 수 있는 문제이다 예를 들어 8의 약수를 생각해 보면, 1, 2, 4, 8 다음과 같은데, 1과 8이 한 쌍을 이루고 2와 4가 한 쌍을 이룬다 (두 수를 곱하면 8이 되는 것이다) 여기서 1과 8은 진짜 약수가 아니므로 해당 문제에서 주어지지 않고 2와 4가 주어진다 이 두 수를 곱해주면 되는데 이 경우 주어진 진짜 약수들 중 가장 작은 수와 가장 큰 수를 곱하면 우리는 N을 알 수 있는 것이다 다만 9의.. 알고리즘/Python 2023. 6. 18. 백준 알고리즘 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. 이전 1 ··· 12 13 14 15 16 17 18 ··· 26 다음
