알고리즘/문제풀이 - 백준

백준 7576 토마토

문제 : https://www.acmicpc.net/problem/7576 아이디어 BFS를 풀이하는 일반적인 방식을 이용 1. 토마토 행렬을 배열에 입력하고, 토마토가 1이면 1인 토마토의 좌표를 큐에 푸시 2-0. 큐의 사이즈를 기억하고 큐에서 하나를 빼낸다. 빼낸 좌표가 (y,x)면 2-1. 빼낸 좌표의 (y,x+1) 값이 0이면 토마토를 1로 바꾸고 (y,x+1) 좌표를 큐에 푸시 2-2. 빼낸 좌표의 (y,x-1) 값이 0이면 토마토를 1로 바꾸고 (y,x-1) 좌표를 큐에 푸시 2-3. 빼낸 좌표의 (y+1,x) 값이 0이면 토마토를 1로 바꾸고 (y+1,x) 좌표를 큐에 푸시 2-4. 빼낸 좌표의 (y-1,x) 값이 0이면 토마토를 1로 바꾸고 (y-1,x) 좌표를 큐에 푸시 3. 2-0에서..

2019. 6. 26. 13:36
알고리즘/문제풀이 - 백준

백준 1780 종이의 개수

문제 : https://www.acmicpc.net/problem/1780 서론 이 문제는 분할정복문제. 그러나 시간초과가 날것같은 예감에 다른풀이가 있는지 생각해보았으나 떠오르지 않았다. 결국 일반적인 재귀를 이용한 분할정복으로 풀었더니 통과. 아이디어 재귀함수, 분할정복에 대한 사전이해가 필요 계산의 편의를 위해 +2한 입력변수를 전부 n*n배열에 넣고 n*n범위내의 수가 전부 같은 수이면 종이의 개수를 +1 하고 아니라면 종이를 9등분하는 재귀함수를 생성 재귀함수는 9등분된 종이가 배열 한칸의 크기가 될때까지 반복 구현 // c++ #pragma warning (disable:4996) #include #include using namespace std; int n; int paper[2188][2..

2019. 6. 12. 15:19
알고리즘/문제풀이 - 백준

백준 3163 떨어지는 개미

문제 : https://www.acmicpc.net/problem/3163 서론 모든 개미를 일일이 옮겨서 풀었으나 시간초과. 시간복잡도를 최대한으로 줄였으나 또 시간초과. 결국 구글링을 했는데, 위의 방식으로는 풀수가 없는듯하고 선지자들의 코드는 이해가 안가서 끙끙대다 이틀걸린 문제 풀이 https://www.acmicpc.net/board/view/28512 위의 댓글에서 충돌을 무시하라는 내용을 보게되었으나 이해가 가지 않았다. 그래서 시간초과가 난 코드에서 충돌을 계산하는 부분을 주석처리하고 돌려보았다. 개미가 낙하할때마다 ID, 경과시간, 낙하위치를 출력하는데 충돌이 포함된 결과 ID 6 4 -2 5 3 -1 경과시간 6 20 23 23 25 26 낙하위치 오른쪽 왼쪽 오른쪽 왼쪽 왼쪽 오른쪽 ..

2019. 6. 9. 22:14
알고리즘/문제풀이 - 백준

백준 1547 공

문제 : https://www.acmicpc.net/problem/1547 아이디어 컵 컵1 컵2 컵3 시작 위치 1 2 3 31스왑 후 위치 3 2 1 23스왑 후 위치 3 1 2 31스왑 후 위치 2 1 3 32스왑 후 위치 2 3 1 위 표와 같이 컵의 위치를 이동 후 마지막 행의 1이 있는곳의 열번호(1의 위치에 있는 컵)를 출력 문제의 -1 출력은 있을 수 없는 일이므로 무시 구현 // c++ #include using namespace std; int cup[3] = { 1,2,3 }; int main() { int m; cin >> m; while (m--) { int a, b; cin >> a >> b; swap(cup[a-1], cup[b-1]); } for (int i = 0; i < ..

2019. 6. 8. 12:11