완전 탐색9

• 

  [BOJ_16955] 오목, 이길 수 있을까? 📌 문제 링크: https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 1차 시도) 2차원 배열의 크기가 10 * 10으로 크지 않기 때문에 완전 탐색으로 2중 반복문을 돌면서 '.'을 'X'로 바꾸고 해당 좌표를 기준으로 상, 하, 좌, 우 그리고 대각선을 2중 반복문으로 'X'의 개수가 5개인지 체크하고, 체크가 끝나면 다시 변환했던 'X'를 '.'으로 되돌려서 계속해서 반복문을 .. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 11. 23.

• 

  [BOJ_2531] 회전 초밥 📌 문제 링크: https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 1. 일단 문제에서 N의 수가 최대 30,000으로 꽤 크다. 이때는 입력을 받는 시간을 최대한 줄이기 위해 빠른 입출력을 사용하자. 2. 회전하는 벨트를 보고 데큐의 rotate() 함수를 떠올랐다. 3. 문제에서 구하고자 하는 값은 '최대한 많은 종류의 초밥을 먹고, 그 수를 반환하는 것'이다.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 7.

• 

  [프로그래머스] 대충 만든 자판 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/160586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: - 딕셔너리만 이용한다면 풀 수 있는 쉬운 문제였다. - 두 번째 for문에서 anwer 배열에 값을 바로 append 하지 않고, count를 변경하고, append() 함수를 한 번만 이용하도록 코드를 작성했다면 두 개의 else 문을 사용하지 않고 코드를 작성할 수 있을 것 같다. - 문제를 푸는 것도 중요하지만, 풀이를 제.. 알고리즘 문제 풀이: 파이썬/Programmers 2023. 4. 23.

• 

  [프로그래머스] 피로도 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: 던전의 최대 길이는 8로 최대 8개의 던전을 순서에 상관있게 나열한다고 했을 때 가능한 경우의 수는 8! = 40,320이고, 각 경우에 대해 최대 8개의 원소를 갖기 때문에 시간 복잡도는 최대 322,560이다. 따라서 던전의 순서를 나열할 수 있는 경우의 수를 모두 따져봐도 문제를 해결할 수 있다. 파이썬에서는 순열을 구하는 함.. 알고리즘 문제 풀이: 파이썬/Programmers 2022. 10. 29.

• 

  [BOJ_1057] 토너먼트 📌 문제 링크: https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 배열에서 원소를 2개씩 구간을 나눠 뽑고, 뽑은 원소 중에서 a와 b가 있는지 확인한다. - a와 b가 둘 다 없다면, 원소중에 하나를 임시 배열(tmp)에 넣는다. - a와 b가 둘 다 있다면, 현재 라운드의 수(game)를 출력하고, 프로그램을 종료시킨다. - a만 있다면, tmp에 a를 추가한다. - b만 있다면, tmp에 b를 추가.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 31.

• 

  [BOJ_1051] 숫자 정사각형 📌 문제 링크: https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 두 번째 for문에서 len(rectangle[i])을 m으로 변경하는 것이 좀 더 깔끔한 코드가 될 것 같다. 🚩 Idea: - n과 m의 길이가 50이하의 수로 완전 탐색을 이용해 모든 경우의 수를 확인해도 시간 초과가 발생하지 않을 것 같다. - 정사각형의 최소 크기(넓이)는 1이므로 area에 해당 값을 넣고 시작한다. - .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 9.

• 

  [BOJ_2798] 블랙잭 문제 링크: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 내 풀이: Idea: N의 최대값이 100으로 삼중 반복문을 돌려 합계를 구한다고 해도 최대 연산 횟수는 1,000,000 이라서 가능한 모든 경우의 수에 대해 탐색이 가능하여 완전탐색으로 해당 문제를 풀 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 5. 30.

• 

  [BOJ_1107] 리모컨 문제 링크: https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 내 풀이 (Fail): 참고용 풀이 (Success): Review: 처음 문제를 접했을 때 완전 탐색이 아닌 N을 바로 만드는 경우에 대해서만 생각했고 그 결과가 위의 첫 번째 코드이다. 하지만 몇몇 테스트 케이스에서 실패하는 경우를 확인하고 어떻게 해결해야 할지 감이 잡히지 않아 구글링을 통해 다른 사람의 코드를 확인하며 문제를 다시 이해하려고 했다. 이 문제의 풀.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 1. 14.

• 

  [BOJ_8892] 팰린드롬 문제 링크: https://www.acmicpc.net/problem/8892 8892번: 팰린드롬 팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다. 상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC www.acmicpc.net 내 풀이: Review: 아이디어 구현까지는 짧은 시간에 완료했다. 처음에는 조합이 아닌 for 반복문 2개로 풀이할까 생각했지만, 시간이 더 걸릴 거 같아서 조합을 이용해서 풀이했다. 조합의 원소 a, b 중 어느 것이 먼저 나오느냐에 팰린드롬이 될 수도 안될 수도 있으므로 위의 코드처럼 모든 경우를 다 확인했다. 또, 팰린드롬을 리턴하지 못할 때는 다음 .. 알고리즘 문제 풀이: 파이썬/BOJ 2021. 10. 27.