Algorithm/Algorithm Problem

백준 1326 폴짝폴짝(BFS)

https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net DP문제라고 생각했지만 bfs적으로 바로 생각이 나서 그래프로 풀었다. ● 지금 서있는 발판 숫자의 배수만큼 뛰어야하니까 for에서 간격을 data값으로 해준 것 ● a to b로 이동해야하는데 a와 b의 크기비교가 문제에 제시하지 않았기 때문에 반대 상황도 고려해야함 방문하지 않았던 곳은 큐에 넣어주고 그 곳으로 가기위한 점프수는 popleft한 값에 1번 점프된 곳이니까 +1을 해..

백준 16112 5차 전직(그리디)

https://www.acmicpc.net/problem/16112 16112번: 5차 전직 메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아 www.acmicpc.net 익숙한 메이플 얘기가 나와서 반가웠당 아케인스톤 활성화 시키고 경험치 많이 먹으려고 하는거 같은데 여러개 활성화가 가능하다고 한다(k개 만큼) 가장 경험치를 많이 먹기 위해선 제일 경험치통이 작은 아케인스톤부터 하나씩 활성화 해야한다 3 2 100 300 200 100 활성 (200 + 300) 200 활성 (300) 4 2 100 300 200 400 100 활성 (200 + 300 + 400) 2..

백준 9421 소수상근수(소수)

https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 소수(prime)에 대해서 구현할 줄 알면 쉬운 문제였다. '에라스토테네스의 체'를 이용하여 소수를 구하고 구현해주면 되는 문제였다. 에라스토테네스의 체 연습문제 재밌는점은 각 자리수를 제곱하고 더해주는 기법을 map()으로 표현할 수 있다는 점이다. tmp = sum(map(lambda x: int(x) ** 2, temp)) map(적용시킬함수, 대상변수) 각 자리수에 대해..

백준 2872 우리집엔 도서관이 있어(그리디)

https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 개인적으로 어려웠던 문제였다. 여러 케이스들을 직접 돌려보면서 규칙을 찾는데 애를 먹었다. 여러번 시도 끝에 찾은 규칙은 list를 순차적으로 탐색하면서 std보다 작은 값은 무조껀 앞으로 빼줘야된다는 것이다. ex) 3 1 4 2 5 std = 3 3보다 작은 수는 1,2인데 얘내는 무조껀 앞으로 빼줘야됨. 이런 규칙을 찾고 처음에 list,remove, list 이어붙이기 이런걸 썻지만 ..

백준 16926 배열 돌리기 1(구현) ★

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net ● 배열을 돌리기 위한 다양한 방법 중에 deque.rotate()를 사용하는 방법을 택했다. ● 2차원의 배열을 1차원으로 바꿔준다음에 rotate()를 돌리면 된다. ● 반시계 방향이기때문에 순서에 유의하며 1차원으로 바꿔주고 몇번 회전을 시킬껀지 rotate(r) 해준다. ● 똑같은 순서에 맞춰서 ..

백준 1461 도서관(구현, 그리디)

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 규칙을 찾는게 중요한 문제였다. 시작점 0에서 음수, 양수 편을 나누고 m만큼 left[m * i] , right[m * i] 간다음에 제일 큰 수에서는 0으로 다시 돌아오지 않고 그 자리에서 끝나면 된다. 유의할점은 left, right의 길이가 m으로 나누어 떨어지지 않을 경우 나머지 k만큼 먼저 간다음에 k에서 시작하여 m*i 만큼 계속 더해주는게 핵심이였다. n,m = list(map(int,i..