Problem Solving/백준 (80) 썸네일형 리스트형 [백준/C++] 1166번 선물 풀이 (탐색 횟수 설명) 문제 해석문제 풀이문제 알고리즘 선택우선 최대 박스의 크기와 갯수가 모두 10억개 이상이니 int 범위로는 overflow가 날 수 있다.단순 수학 문제로 생각했으나 정수가 아닌 실수 정답을 가지고 있어 추가적인 방법을 고민이분 탐색을 생각했고, 제출했으나 소수점 자리에서 무한 루프가 발생최대 실행 횟수를 고려하게 됨실행 횟수 풀이 과정정답은 1~109 까지 값을 가지고 소수점 역시 최대 9자리까지이므로 이분 탐색으로 log2(1018)이다.대략 18/0.3xx으로 59.x회최대 탐색횟수는 60으로 제한하고 실행하면 된다! (계산 어렵고 귀찮으면 100정도 잡아도 될 것 같다) 코 드#include using namespace std;int main() { long long int N, L, .. [백준/Python] 3687번 성냥개비 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 각 숫자별 필요한 성냥개비의 갯수는 아래와 같다 1 2 3 4 5 6 7 8 9 0 2 5 5 4 5 6 3 7 6 6 최대값 2개(1)와 3개(7)이 최소 갯수이며 모든 성냥을 1과 7을 통해 소진 시킬 수 있으며 가장 많은 자리수를 가질 수 있도록 유도할 수 있다. 따라서 최대값은 1과 7을 이용해 단순한 탐욕법 (그리디)로 풀어낼 수 있다. 최소값 브루트 포스로 3,5,9와 같은 숫자를 제외한 모든 숫자로 만들어낸 성냥의 갯수를 이용하려고 했으나 최대값을 고려했을 때 시간 초과가 난다 다시 한 번 17까지 모든 숫자를 계산해보았더니 이전 값에 새로운 자리수(0~9)를 추가하는 형태임을 발견했다. (그러나 6개일 때와 13개일 때와 같이 앞자리에 0이 올 수 .. [백준/Python] 16639번 괄호 추가하기3 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 중복된 괄호가 가능하며 괄호의 갯수 제한이 없다 모든 경우의 수를 계산하여도 수식의 길이가 19라 충분할 것처럼 보인다. 브루트포스로 풀이 풀이 과정 숫자와 연산자를 분리하여 저장한다. 연산자의 index를 기준으로 각각의 연산자가 먼저 계산되는 permutation을 구한다 구한 값과 기존 식을 결합시킨다 (연산자의 경우 사용한 연산자를 제외시킨다) 숫자 배열이 1개만 남았을 때 값을 정답배열에 추가시킨다 정답 배열에서 값을 도출한다 코 드 import re import sys import operator from itertools import permutations length = int(sys.stdin.readline()) expression = sys.s.. [백준/Python] 16637번 괄호 추가하기 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 중첩된 괄호는 사용할 수 없고, 괄호의 갯수는 제한이 없다 괄호는 (a+b)+c 형식이거나 a+(b+c)의 형태로 3개의 숫자 중 12번을 묶거나 23번을 묶는 경우의 수만 존재한다. 재귀함수를 이용해 두 형태로 가지 뻗어 브루트포스로 풀어내기 풀이 과정 식에서 숫자와 연산자를 분리하여 저장한다. 숫자의 맨 앞 값을 빼내 연산자와 갯수를 맞춰준다. index 숫자를 기준으로 재귀함수를 작성한다. 괄호를 12번을 묶는 경우와 13번을 묶는 경우로 하여 계산한다. index가 끝에 도달하면 정답 배열에 값을 추가한다. 정답 배열의 최대값을 도출한다. 코 드 import sys import operator import re s_length = int(sys.stdin... [백준/Python] 1446번 지름길 풀이 1. 문제해석 2. 풀이 과정 문제 알고리즘 선택 지름길을 타지 않았을 때 이전 값과 지름길을 탄 경우의 값을 비교하는 형태로 이전 값에서 다음 값을 쌓아올리기 가능 최대 거리가 1만이며 최대 지름길의 경우의 수가 12개로 모든 경우의 수를 dp로 제한 시간 내에 해결 할 수 있다. dp로 풀이 풀이 과정 현재 값에서 지름길을 탈 수 있다면 현재 거리에서 지름길을 탄 값과 지름길을 타고 난 후 값을 비교하여 최소값을 넣는다 현재 값과 바로 직전 값에 + 1을 한 값의 최소값을 비교한다. 3. 코드 import sys route, distance = map(int, sys.stdin.readline().split()) shortPath = [list(map(int, sys.stdin.readline().s.. [백준/Python] 1238번 파티 풀이 문제 해석 문제 풀이 이 문제는 벨만포드 풀이와 다익스트라 풀이가 있으며 다익스트라 2번 만으로도 풀어낼 수 있다. 벨만포드의 경우 C++에서는 통과하였으나 pypy, python 모두 불통과를 받았다... 모든 순서쌍의 거리를 계산하는 방식이니 아래 코드에서만 설명하고 생략하자 다익스트라 2회로 문제를 풀어낼 수 있다는 것이 너무나도 흥미로웠는데 이유는 아래와 같다. 모든 마을(노드)에서 특정 마을로 가는 길(간선)이 존재한다고 하면 간선을 뒤집어서 특정 마을에서 출발하면 모든 마을로 가는 최소 거리를 알 수 있다. (너무나도 충격적인 발상이다..... 대체 뭘 해야 이런 발상이 가능하지) 그리고 기존 순서쌍을 이용해 특정 마을에서 모든 간선으로 돌아가는 거리를 계산하면 총 2번만에 계산할 수 있다. .. [백준/Python] 2579번 계단 오르기 풀이 문제 설명 문제 풀이 dfs를 통해 하나 또는 두 계단을 밟으며 세 개의 계단을 연속해서 밟는 경우를 가지치면 어떨까? 라는 생각을 하였지만 생각보다 조건처리가 번거롭고 2300 은 생각보다 너무 큰 숫자가 될 것 같아 포기하고 dp를 생각했다. 점화식을 세우려고 패턴을 찾다가 그냥 규칙을 이용하기로 했다. 최대 2번 연속된 계단을 이용할 수 있으니 ONE,TWO를 통해 state로 구별해 연속된 계단을 몇칸 밟았는지 확인한다. (ONE에는 1칸 연속된 계단을 이용한 값, TWO에는 2칸 연속된 계단을 이용한 값) ONE의 경우 2칸 이전 계단에서 값을 받아오고 TWO의 경우 바로 이전과 두칸 이전 계단 중 ONE state에 있는 값만 가져와 비교한다. N까지 쌓아 N번째 계단에 도달한 경우의 최고 값.. [백준/C++] 9663번 N-Queen 풀이 문제 설명 문제 풀이 처음 시도에는 N이 15밖에 되지 않으므로 브루트포스가 당연한 것은 알고 있었고 2차원 배열로 가로 세로 대각선에 있는 값을 true로 변경하며 dfs(재귀)로 풀어나가려고 했으나 코드를 작성하다보니 가로 세로 대각선의 값을 계속 변경하는 불편함이 있고 굳이 2차원으로 풀어나가는 비효율성을 유지할 필요가 없다고 느끼게 되었다. 이후 바로 가로배열, 세로배열을 생성하였고 대각선 값을 어떻게 변경할까 고민하게 되었다. 과거 수업에서 배운 자료를 참고하였고 / 방향 대각선은 현재 행과 열의 합이 같다는 것과 열과 행 중 하나의 값만 뒤에서부터 값을 세어보면 \ 방향 대각선도 해결되는 것을 알게 되었다. 위 그림과 같이 row와 col의 합이 대각선의 값임을 알 수 있다. 코 드 #incl.. 이전 1 2 3 4 ··· 10 다음
