[Python/파이썬] 백준 14888번 - 연산자 끼워넣기

문제 설명 입력과 출력 입출력 예제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 코드 이 문제는 푸는 방법이 2가지가 있다. 바로 파이썬의 라이브러리인 permutations(순열)과 DFS로 푸는방법이 있다. 여기서 순열로 풀게 되면 pypy3는 제출 통과하지만 python3으로 제출 시 시간초과가 발생하게 되고 시간복잡도가 높다. 그러므로 나는 DFS로 푸는 방식을 선택하여 이 문제를 풀었다. 주어진 숫자들을 처음부터 시작하여, 주어진 부호..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 7. 10.
• textsms

[Python/파이썬] 백준 9663번 - N-Queen

문제 설명 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 코드 이 문제는 가능한 모든 경로를 탐색하되, 조건을 만족하지 않는 경로는 중간에 가지치기하여 더 이상 탐색하지 않는 백트래킹 알고리즘을 사용하여 풀 수 있었다. 문제에 대해 설명하자면, 체스에서 퀸은 상하좌우 대각선 모든 방향으로 원하는 만큼 이동할 수 있다. 그렇기 때문에 퀸을 서로 공격할 수 없도록 놓기 위해서는 체스판위의 행, 열 마다 하나의 퀸이 존재해야한다. 처음에는 2차원 배열로 푸는 방법이 더 이해가 쉬울것 같아서 2차원 배열로 문제를 풀고 제출해..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 7. 6.
• textsms

[Python/파이썬] 백준 1436 - 영화감독 숌

문제 설명 입출력 예제 풀이 코드 이 문제는 완전탐색 탐색 문제로 완전 탐색 답게 무식하게 숫자를 하나씩 더해가면서 해당 숫자가 몇번째 종말의 수인지 찾아야 한다. 그래도 반복문을 덜 타게 규칙이 있지 않을까?했지만 그런 규칙을 찾긴 힘들었다 다만 반복문을 덜타도록 탐색하는 수 num을 1부터가 아닌 종말의 수인 "666"부터 시작하도록 하였다. 정답 코드 import sys input = sys.stdin.readline n = int(input()) cnt = 0 # 몇 번째 종말의 수인지 카운팅 num = 666 while True: if "666" in str(num): # 666이 num에 포함되어 있다면 cnt = cnt + 1 if cnt == n: # 구하자고 하는 n번째 종말의 수와 같다..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 6. 23.
• textsms

[Python/파이썬] 백준 1065 - 한수

문제 설명 입출력 예제 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 코드 처음에는 문제 설명을 이해하는게 어려울 것이다. (문제 설명이 좀 많이 아쉽;) 왜 110을 입력했을 때 결과가 99가 나오는지 이해할 수가 없었다. 하지만 왜 그러한 결과가 나오는지 이해만 한다면 문제는 실버난이도 답게 쉽게 풀 수 있을 것이다. 일단 "한수"라는 것은 각 자리수의 차이가 일정한 수이다. 111 이라는 수가 주어진다면 이 수는 각 자리수 차이가 0이므로 ㅠ이다. 그렇다면 5는 어떨까? 자리수를 비교할 대상이 없지만..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 6. 17.
• textsms

(javascript) 알고리즘 문제 - 완전탐색 (가장 많은 문제를 맞춘 수포자 찾기)

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. ( 수포자들의 답안 패턴을 찾기 쉽도록 글자색으로 나누었습니다. ) 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2022. 9. 18.
• textsms