본문 바로가기

코딩) PS 공부 [백준]11

PS) 백준 퇴사 #include #include using namespace std; int dp[20][2]; int maxsum[20]; int main(){ int n; scanf("%d",&n); int a,b; for(int i=1;i 2021. 6. 24.
PS) 2178, 1697, 18870번 (미로 찾기, 숨바꼭질, 좌표 압축) 2178번 미로 찾기 bfs이므로 현재 방문할 수 있는 노드를 그냥 탐색하면서 탐색횟수를 저장해주면 된다. 탐색한 노드는 다시 방문하지 않아도 된다 (저장한 탐색 횟수가 1,1에서 현재 노드로 가는 최소 거리로 확정된다). 이후 탐색하는 과정에서 이미 탐색한 노드로 길이 이어질 수 있지만 그 경로는 다른 노드를 몇번 거쳐서 오는 것이므로(bfs이므로! ) 최소 거리가 아니고, 따라서 고려할 필요가 없다. 처음에는 최소 거리일 때, 저장한다라는 조건을 주어서 구현하였는데 굳이 이 조건은 필요가 없다. 탐색하면서 거리를 저장해주고, 방문을 기록해주고 반복하는 식으로 하면 된다. #include #include #include using namespace std; int arr[105][105]; int mi.. 2021. 5. 14.
PS) 1012, 2583, 2468, 2644번 (유기농 배추, 영역 구하기, 안전 영역, 촌수 계산) 1012 유기농 배추 //CC를 구해라 #include #include using namespace std; int m, n, k; int arr[55][55]; queue q; int tox[4] = {0,0,1,-1};int toy[4] = {1,-1,0,0}; void bfs(int x, int y) { //가로,세로,배추의 개수 q.push({ x,y }); pair node; while (q.empty()==false) { node = q.front(); arr[node.first][node.second] = 0; for (int i = 0; i < 4; i++) { int newx = tox[i] + node.first; int newy = toy[i] + node.second; if (new.. 2021. 5. 13.
PS) 백준 7569, 11724, 7562, 2667, 2606번 (토마토, 연결 요소의 개수, 나이트의 이동, 단지번호 붙이기, 바이러스) 백준 7569번 토마토 어제 토마토 (2차원)을 풀었다. 오늘 푼 문제는 거의 비슷한데 3차원으로 구현하는 문제다. 저번주에 dp를 공부할 때 dp문제인 줄 알고 열심히 하다가... 아님을 알고 울면서 ㅜ포기했다. 이 문제가 bfs인 이유는 기본적으로 토마토의 상태를 탐색해주어야 하기 때문이다. 토마토의 상태를 탐색하고, 바꾸어주는것이 관건이므로 토마토의 기본 상태에서 변화해가는 좌표를 기억해가며 탐색해야 한다. 일주일 전에 틀린 코드를 다시 보니 dp가 아니라 큐로 좌표를 저장해가며 대충 구현은 했다. 그러나 중간에 계속 dp인것에 신경이 쓰여(이 문제가 dp문제집에 있었거든......) 머리가 터져버렸다. 정작 코드에는 dp로 구현 안해놓고 왜 dp에 얽매인거지? 이전 코드의 문제점은 토마토가 다 칠.. 2021. 5. 12.
PS) 백준 12764, 7576, 1260번 (싸지방에 간 준하, 토마토, DFS와 BFS) in c++ 백준 12764번 싸지방에 간 준하 이전에 시간초과 난 이유 분석 -> 수정한 부분 설명 아이패드 p32 사용할 수 있는 컴퓨터를 다 빼주고 컴퓨터의 index를 고려하지 않고 사용자를 앉혀 주면 된다고 생각했다. 어짜피 이후의 사람들이 앞 컴퓨터를 앉으므로 => 마지막 컴퓨터일 경우 해결 ) 컴퓨터를 빼 주고, 컴퓨터의 index를 우선순위 큐에 담아 정렬시킨다. 우선순위가 높은 컴퓨터를 먼저 이용한다. 마지막 하나의 반례가 더 있었다. 이미 종료한 컴퓨터를 사용하는 경우, (computerq에 있는 컴퓨터) 다시 컴퓨터의 종료시간을 종료시간 큐에 넣어주어야 한다. 그런데 방금 사용한 컴퓨터가 다음 컴퓨터 시작 전에 종료하는 경우, 이 컴퓨터는 우선순위 큐에 담기지 않았기 때문에, 우선순위 큐에 담겨 .. 2021. 5. 11.
PS) 백준 1720번 (타일 코드) 너ㅓㅓㅓㅓㅓㅓㅓ무 하기 싫고 안풀리는날인데 짜증나아 백준 1720번 타일코드 계속 등장하는 타일 문제... 이번 문제는 중간에 헷갈려서 시간을 많이 허비했다. 처음에는 좌우 대칭인 코드의 수, 좌우 대칭이 아닌 코드의 수를 따로 계산하려고 했는데, 좌우 대칭인 코드를 구하는 것은 쉽다. 길이-2의 경우에 각각 앞뒤에 2*1사각형 추가, 길이-4인 경우에 각각 앞뒤에 2*2, 1*2*2인 사각형 추가해주면 된다. 반면에 좌우 대칭이 아닌 코드의 수를 어떻게 구할지 막막했다. 규칙도 없고 이전 상황을 저장할 수도 없고,,, 그러나 조금 더 생각해보니 그냥 전체 경우의 수에서 좌우 대칭인 경우의 수를 빼면 바로 나오는 것 아닌가.... 아 이걸 왜 크게 고민한걸까 ㅠㅠ 좌우 대칭인 코드는 전체에서 하나만 존재하고, 좌우 대칭이 아닌 코드는 뒤집을 시 짝이 하나.. 2021. 5. 6.

티스토리툴바