Algorithm/Algorithm Problem

백준 11571 분수를 소수로(구현)

https://www.acmicpc.net/problem/11571 11571번: 분수를 소수로 입력의 첫 번째 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 15,000)가 주어진다. 이후 각 테스트 케이스에 대해 한 줄에 분자와 분모 (0 ≤ 분자 < 1024, 0 < 분모 < 1024)가 공백으로 구분되어 정수로 주어진 www.acmicpc.net 개인적으로 엄청 어려운 문제였다. 처음에 접근한 방법은 소수점 아래의 숫자들을 문자열이라고 치고 반복적으로 나타나는 패턴을 찾기 위해 브루트포스를 이용하거나 한번 나온 숫자가 뒤에 다시 나올 떄 조건을 두는 방식으로 했는데 잘못된 생각이였고 잘 풀리지 않았다. 분수를 소수로 바꾸는 과정은 위의 사진처럼 나눗셈을 하면서 나머지에 대해 처리를 해주면서 진행이..

백준 7662 이중 우선순위 큐(Heapq)

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제는 간단하게 데이터를 삽입하고 최대값, 최소값을 삭제 해주면서 데이터를 관리하는 작업이였다. list를 선언하고 list.index, list.remove 등 list 연산을 쓰면 무조껀 시간초과가 나기때문에 최소힙, 최대힙을 사용하여 최소, 최댓값에 대한 처리를 해야겠다고 생각했다. 여기서 유의할점은 단순히 우선순위큐 모듈인 PriorityQueue()을 사용하려고 했지만 최소, 최대를 ..

백준 16928 뱀과 사다리 게임(BFS)

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀과 사다리의 좌표가 주어진 것을 활용하기 위해 list의 in 개념을 이용하려고 했지만 비효율적인 것 같아 Dict의 key, value를 이용해서 접근 하기로 했다. 주사위를 굴려서 1~6을 이동하면서 좌표의 cnt를 기억해두는 dp배열을 하나 만들고 저장하기로 했다. 유의할점은 뱀과 사다리로 이동하는 것은 주사위를 굴리는 것이 아닌 행동이기 때문..

백준 14500 테트로미노(Brute-Force, DFS)

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net N x M의 보드에 우리가 알고있는 테트리스 블록을 넣었을 때 최대가 되는 값을 구해주는 것이 문제다. 1. 5가지 블록을 회전, 뒤집기 모두 가능하기 때문에 모든 경우의 수를 따져서 직접 board에 일일이 해보는 Brute-Force 2. DFS 1번 같은 경우가 바로 생각난 풀이법인데 이렇게 하면 풀리겠지만 별로 하고싶은 문제는 아니였다. 그래서 고민을 해본결과 ㅗ형 블록을 제외하면 나머지도..

백준 9019 DSLR(시간복잡도, BFS)

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 이해하기에는 어렵지 않았다. D,S,L,R에 따른 연산을 하고 연산결과가 B랑 같으면 어떤 연산을 했는지 출력한다 최소한의 연산을 해야하기 때문에 그리디, BFS적으로 접근을 했고 한 경우가 계속 4가지로 나가는 완전 트리의 형태를 생각해서 그래프 문제라고 생각하고 BFS적으로 접근했다. 여기까지의 생각은 어렵지 않았는데 python으로 풀다보니 시간초과에서 많이 애를 먹었다...

백준 7569 토마토(3차원배열, BFS)

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 상자에 있는 토마토가 근접해있는 다른 토마토에 영향이 가게 하는 것이니까 BFS로 접근하면 좋겠다는 생각을 했다. 여기서 첫번째 고려할점은 2차원이 아닌 3차원 방향이기 때문에 dx,dy,dz를 설정해줘야 한다는 것 dx = [-1, 1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0, 0, 0, -1, 1] 그 후 그래프를 돌면서 토..