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

백준 3190 뱀

문제 : https://www.acmicpc.net/workbook/view/1152 서론 시뮬레이션 문제이며 큐를 활용했다. 풀이 입력받으면서 회전은 큐에 저장하고 사과는 지도에 표시한다. 그리고 문제에 적혀진 매 초가 지날때마다 일어나는 행위들을 반복문에 쓴다. 뱀은 큐에도 저장하고 지도에도 위치를 표시했는데, 큐에 저장한것은 꼬리를 제거하기 위함이고 지도에 표시한건 자기 몸과 부딫히거나 벽과 닿는지 확인하기 위해서다. int dy[4] = { 0, 1, 0, -1 }; // 우하좌상 int dx[4] = { 1, 0, -1, 0 }; while (++time) { // 이동방향으로 한칸 이동 y = y + dy[dir]; x = x + dx[dir]; // 자기 몸과 부딫히거나 벽과 닿으면 끝 if..

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

백준 2206 벽 부수고 이동하기

문제 : https://www.acmicpc.net/problem/2206 서론 크게 어렵게 생각 안했는데 시간초과를 연타로 맞았다. DFS로 구현했다가 시간초과 같은 아이디어를 BFS로 구현했다가 시간초과 방문배열을 3차원으로 만들었는데 시간초과 큐에서 꺼낸 후 방문체크에서 꺼내기 전 방문체크로 수정해서 통과 많은걸 얻어가는 문제다. 풀이과정 기존의 이동할 곳이 0이면 방문하고 1이면 방문하지 않는것에서 조건을 하나 추가해준다. 1이더라도 내가 지금까지 벽을 뚫은적이 없다면 벽을 뚫은 후 다시는 벽을 뚫지 않겠다고 공표하고 방문한다. 따라서 방문할때마다 내가 기존에 벽을 뚫었는지 안뚫었는지 확인을 해야하므로 확인할 수 있는 변수를 큐에 좌표와 함께 넣어준다. 여기까지가 내 아이디어였는데 그 후 수많은 ..

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

백준 1697 숨바꼭질

문제 : https://www.acmicpc.net/problem/1697 서론 bfs 문제. 풀이 bfs인데 탐색시간을 출력해야한다. 보통 bfs 문제는 2차원 배열을 만들기 때문에 한칸씩 옮겨질때마다 이전칸의 값에서 +1을 해줘서 최종 칸에서의 값을 탐색시간으로 출력해줬는데 이 문제는 배열을 만들지 않는다. (안만들려고 했는데 방문 확인 배열이 없으니 메모리초과를 출력해서 방문 확인 배열은 만들었다.) 그래서 반복문 반복 횟수를 체크했다. 그러나 큐의 반복 횟수를 전부 체크하면 안된다. int cnt = 0; while(q.empty()){ int qSize = q.size(); while(qSize--){ ... } cnt++; } cout n >> k; int cnt = 0; q.push(n); ..

2019. 8. 25. 22:02
알고리즘/문제풀이 - 백준

백준 2075 N번째 큰 수

문제 : https://www.acmicpc.net/problem/2075 서론 메모리 제한이 잡혀있다. 입력값을 전부 배열에 넣거나 큐에 넣으면 메모리초과가 발생할 것이다. 일부만 넣어야 한다. 아이디어 최소힙을 가지는 우선순위 큐를 만든 다음 큐에는 입력값 중 가장 큰 수 n개만 들어가도록 한다. 그럼 큐의 루트 힙이 정답이 될 것이다. 큐의 사이즈가 n개가 될때까지는 그냥 채워주고 n개가 되면 큐의 루트 힙보다 큰 값만 큐에 집어넣고 큐의 루트힙은 빼주면 된다. 그럼 입력값 중 가장 큰 수 n개가 들어있는 큐가 유지된다. 구현 //c++ #pragma warning(disable:4996) #include #include int main() { std::priority_queueq; int n; s..

2019. 8. 22. 11:49
알고리즘/문제풀이 - 백준

백준 1655 가운데를 말해요

문제 : https://www.acmicpc.net/problem/1655 서론 상당히 오래 걸린 문제. 반나절은 푼것 같다. 우선순위 큐는 내부 힙이 완벽히 정렬이 되지는 않지만 큐에서 빼낼때마다 배열에 저장하면 완벽히 정렬이 된다. 그래서 입력 한번 받을때마다 큐를 비웠다 채웠다를 반복해봤는데 시간초과 트리에서 수식으로 얻을 수 있는게 있는지 고민해봤으나 찾을 수 없었다. 엑셀에서 예상되는 결과를 표로 그려봤는데 시프트레지스터가 떠올라서 아이디어를 얻을 수 있었다. 아이디어 입력값이 들어올때마다 예상되는 중앙값을 표로 나타내봤다. 각 행의 노란색 셀이 중앙값인데, 노란색 셀이 두개면 둘 중 최소값이다. 우선순위 큐에선 입력될때마다 위와 같이 완벽히 정렬이 되지는 않지만 일단은 정렬이 된다고 가정하고 ..

2019. 8. 21. 20:29
알고리즘/문제풀이 - 백준

백준 11279 최대 힙

문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 인한 문제였다. printf, scanf 를 사용하여 해결했다. 구현 // c++ // max heap #pragma warning (disable:4996) #include #include typedef struct pq { int heap[100003] = { 0, }; int index = 0; }pq; void push(pq *q, int item) { q->index++; q->heap[q->index] = item; int index = q->index; whi..

2019. 8. 20. 20:20