알고리즘 & PS69 [BOJ] 퍼즐 (1525, G2) 아이디어는 BFS를 활용한 빡구현. 처음에 퍼즐판에 나올 수 있는 경우를 확장하여 9!로 visited를 생성하고,최단 턴 수 이므로, 한 번 나온 배열은 다시 나오지 않게 처리한다.이 때, 퍼즐의 이동을 2차원 배열이 아닌 문자열로 처리.더불어, 명백하게 풀이가 불가능한 케이스로 예외 처리를 하여 조금 속도 이득을 보려고 했는데... 비효율 풀이 같다...import sysfrom collections import dequeinput = sys.stdin.readlinedef dfs(level, ans): if level == 9: puzzle_dict[ans] = False return else: for i in range(0, 9): .. 2024. 12. 15. [BOJ] 814-1 (16972, B1?) 문제 설명주어진 조건에 맞는 814개의 점을 찾아야 합니다. 주의사항은, 가장 가까운 두 점의 쌍이 여러개여서는 안 된다. 입니다..즉, 단순히 직사각형으로 점들을 배치했다가는 가장 가까운 두 점의 쌍이 여러개이므로 오답! 입니다. 생각의 단계1단계. 일단 풀기먼저 가장 쉽게 생각할 것은, 임의로 점을 뿌리면 두 점의 거리가 같은 쌍이 두 개 이상 나올 가능성이 매우 적습니다. 이렇게 하면 일단 정답은 맞힐 수 있습니다.import randomfor i in range(814): a=random.randint(-8140,8140) b=random.randint(-8140,8140) print("%d %d"%(a, b)) 하지만 이대로는 고득점을 맞기는 어렵겠죠? 점수를 더 높혀봅시다. .. 2024. 12. 2. [BOJ] 성냥개비 (3687, G2) 문제풀이 아이디어각 숫자마다 쓰이는 성냥개비가 달라서, 명백하게 어떤 일반항을 찾기는 어렵지만 어느 정도 통제가 가능합니다.같은 개수가 사용된 성냥개비 중 최댓값을 만들기 위해서는 가장 큰 숫자, 최솟값을 만들기 위해서는 가장 작은 숫자가 필요합니다.단! 최솟값의 경우 맨 앞에 0이 와서는 안됩니다. 따라서 6으로 대체하고, 맨 앞이 아닌 6은 모두 0으로 대치하는 별도의 추가 과정이 필요합니다.근데 이걸 그냥은 알기가 어렵습니다. 최초 2~7획에서도 최대/최소의 케이스가 달라지므로 다음과 같이 생각합니다.먼저 2, 3개는 그냥 초항으로 계산합니다.4개째부터는 2~7획이전의 결과를 살펴보아, 그냥 자체로 최대/최소인지, 이전의 결과에 특정 숫자를 앞뒤로 붙여 최대/최소인지 모두 확인합니다. 그리고 가장 .. 2024. 12. 2. [BOJ] 욕심쟁이 판다 (1937, G3) https://www.acmicpc.net/problem/1937 이 문제, 보기와 다르게 절대 쉽지 않습니다. 생각해본 방향우선 가장 쉽게 생각해볼 수 있는 풀이는 다음과 같습니다."이거 그냥 DFS나 BFS 모든 점에서 하면 되는거 아님?"저는 조금 더 현명하게 하기 위해 다음과 같이 약간 그리디하게 생각해 보았습니다.시작점의 후보는 더 큰쪽으로 나가게 방향 그래프로 그리면 indegree =0 인 지점이다.그렇게 dfs를 돌리면 된다! 선언을 하고 코드를 작성합니다.# 아예 그래프를 만들어서 indegree가 0인 애를 찾아줘야 한다.import sysfrom collections import dequesys.setrecursionlimit(10**6)input = sys.stdin.readli.. 2024. 11. 28. [BOJ] 가장 큰 정사각형 (1915, G4) 문제 풀이 과정간단한 DP 문제입니다. 순서대로 점을 탐색하며, 현재 위치에서 만들 수 있는 가장 큰 정사각형을 찾습니다.정사각형은 4개의 꼭지점이 만들고.. 이는 현재 점의 좌측, 위측, 왼쪽 위측에서 정사각형을 만들어주고 있나?로 탐색합니다.import sysinput = sys.stdin.readlinerows, cols = map(int, input().split())maps = []for _ in range(rows): cur_row = list(str(input().rstrip())) cur_row = [int(x) for x in cur_row] maps.append(cur_row)dp = [[0 for _ in range(cols)] for _ in range(rows)]m.. 2024. 11. 25. [BOJ] n제곱 계산 (12728, P1) 추천받은 수학 문제를 풀어 보았습니다. 구현의 난이도 보다는 수학 자체에 치중된 난이도로수학 값으로 플래티넘1이 나온 것 같습니다. 1, 2차 시도 / 실패처음 든 생각은, (3+루트5)^n을 계산해보면 되겠다는 생각이 들었습니다.(a+b루트5)(3+루트5)를 계산한 뒤, 이를 행렬표현 하는 생각을 했고, 행렬의 거듭제곱이니, 수가 커지니 분할제곱 합니다.수가 너무 커지므로 modulo...? 실패!네, 실패한 사유는 정수 부분은 1000으로 나눠도 되겠지만 루트5는 무리수 파트임을 간과한 풀이로 실패했습니다.그렇다고 modulo를 풀어주면 시간 초과로 실패입니다. 루트5를 확정적으로 없애줄 방법이 필요할 것 같습니다. 컴퓨터는 루트를 정확하게 계산 할 수 없을거니까요. 잘 왔지만, 조금 다.. 2024. 11. 25. 이전 1 2 3 4 ··· 12 다음
