[BOJ 1629][백준 1629번] 곱셈 (파이썬 풀이) 포스팅 썸네일 이미지

Algorithm/Baekjoon

[BOJ 1629][백준 1629번] 곱셈 (파이썬 풀이)

https://www.acmicpc.net/problem/1629 🤔 문제 설명 및 입출력 ✍ 접근 방법 눈에 보이는대로 풀면 이렇게 쉬운 문제가 없다. 그냥 A*B%C 하면 되는 문제니까 말이다. 근데 정답률을 보아하니 나처럼 생각했다간 큰 코 다치는 문제임이 확실하다. 괜히 S1 난이도를 단게 아닌거 같다. 그래서 구글링을 좀 해보니, O(N) 곱셈을 O(logN)으로 줄여주는 방법인, 분할정복을 이용한 방법으로 해결해야한다고 한다. 단순 곱셈에 어떻게 분할 정복을 적용하나 싶었는데, 생각보다 간단한 아이디어였다. 2^8 계산을 해야한다 해보자. 여태까지 우리는 컴퓨터에게 2*2*2*2*2*2*2*2 를 시켰다. 근데 이 식을 잘 살펴보자. 2^8은 2^4 * 2^4 가 아니던가??? 그럼 2^8 =..

2021.07.04 게시됨

[BOJ 16236][백준 16236번] 아기상어 (파이썬 풀이) 포스팅 썸네일 이미지

Algorithm/Baekjoon

[BOJ 16236][백준 16236번] 아기상어 (파이썬 풀이)

https://www.acmicpc.net/problem/16236 🤔 문제 설명 및 입출력 ✍ 접근 방법 문제의 핵심은 "상어가 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾아라" 이다. "가장 가까운 대상 찾기 + 입력이 행렬 꼴 " 이면 대부분의 문제는 BFS를 활용하여 풀이한다. 얼핏 보면 문제에 조건이 엄청 바리바리 달려있어서 복잡해보이지만, 상어의 크기가 커지는건 크게 어려운 부분이 아니라, 주어진 입력에 대해 다음 시퀀스를 반복하면 된다. 잡아먹을 수 있는 물고기를 찾는다 찾은 물고기들 중 가장 가까운 놈들 잡아먹는다 행렬을 갱신한다. ( 잡아 먹은놈 행렬에서 삭제) 크기를 키울 수 있으면 키운다 더 이상 잡아 먹을 수 없을 때까지 반복한다. 여기서 포인트는 잡아먹을 수 있는 "물고기 중..

2021.06.05 게시됨