본문 바로가기

전체 글270

[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.
[BOJ] 파이프 옮기기 1 (17070, G5) 문제 내용  풀이 과정도착 상태가 가로인지, 세로인지, 대각선인지를 나눠서 모두 합쳐주면 된다. 즉, 이를 기억하는 dp를 만들면 된다.위의 7가지 이동 상황을 모두 각각을 점화식으로 만들면 되는데, 몇 가지 주의사항이 있다.1. 맨 첫번째인  0행의 경우 가로줄 이동만 가능하다. 벽을 만나기 전까진 1, 벽을 만난 다음부터는 무조건 02. 두 번째 행부터는 세로, 대각선 이동도 가능하다.  단, 대각선은 0열, 1열에서는 움직일 수 없다. 파이프는 2칸이다.3. 맨 첫번째 열은 그냥 경우가 0이다.이를 바탕으로 최종 마지막 칸에서 가로 + 세로 + 대각선 하면 되는 문제.import sysinput = sys.stdin.readline# 가로로 도착하냐, 세로로 도착하냐, 대각선으로 도착하냐를 나눠서 .. 2024. 11. 24.
BOJ Gold 1 달성 약 3주 정도, 집중적으로 PS를 하고 있는 중입니다. 재미도 있고, PS로 코딩에 흥미를 되찾고 있으므로, 긍정적이라고 생각합니다.Class는 4+를 달성했습니다. 현재 공부 방향Class 4~5에 집중하며 핵심적인 알고리즘들을 습득하는 데에 집중하고 있습니다. 처음 보는 알고리즘의 대표문제의 경우는 해당 알고리즘을 먼저 간단하게 개요를 확인하고 해당 문제를 예제로 생각하며 실제로는 어떻게 풀어야 하는지를 익히는 데에 집중하고 있는 단계입니다. 우선은, 지금은 배울 알고리즘 자체가 많습니다. 빠르게 적응하는 데에 집중하고 있습니다.추가로, 구현력을 키우는 데에 집중하고 있습니다. 삼성 문제라던가, 어느정도 구현을 많이 필요로 하는 문제들에 많이 도전하고 있습니다.  앞으로의 방향당분간은, PS 학습 +.. 2024. 11. 24.
[BOJ] 텀 프로젝트 (9466, G3) DFS로 풀 수 있는 문제. 좀 까다로운 문제이다.문제의 핵심은 "사이클"을 찾아 내는 것이다. 하나의 원소를 넣고, 돌면서 방문 여부를 체크하게 된다. 이 때, 이동한 경로를 넣고, 이미 방문했는데, 사이클 리스트에 있다면 사이클이라고 판단, 반환하는 것이다.문제는, 사이클에서 일부 삐져나온 상황이다. (2 4 7 3 4 7 3.... 이렇게 도는 상황) 이를 주의해서 구현한다.import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(cur_std, cur_result): visited[cur_std] = True cur_cycle.append(cur_std) next_std = std_list[cur_std] .. 2024. 11. 24.
[BOJ] 귤나무 (31005, G1) 이번 문제는 상당히 어려운 문제입니다. 어려운 알고리즘을 쓰진 않지만, 최적화를 잘 해야 합니다.문제 내용 풀이 과정우선 문제를 이해해 봅시다. 순서대로, 귤을 가져갑니다. 못 가져가면 아무것도 못하고 다음 애가 가져갑니다... 반복합니다.아무도 귤을 못 가져가는 순간이 옵니다. 그 대로 저 날짜까지 가면 됩니다. 대략 숫자 범위를 보면, 최악의 케이스여도 대충, 20만 * 10^18 * 10^12 잡아도  10^100보다는 확실히 작습니다. 따라서 10^100은 크게 고려하지 않아도 될 거 같습니다.즉 문제는, 마지막에 몇 개가 남을 것인가? 에 집중하면 됩니다. 이를 역으로 생각해 봅시다.곰곰이들 중, 과일을 가장 적게 원하는 애가 있을 것입니다. 그 애가 원하는 것보다 과일이 더 적게 남는다면? 남.. 2024. 11. 22.

티스토리툴바