반응형 전체 글580 [BFS, 난이도 중] 백준 14502번 연구소 내 접근 법은 연구실 지도에서 빈칸인 좌표를 모두 v벡터 안에 넣고 벽을 세울 3곳의 좌표를 고르는 모든 경우의 수를 탐색하는 것이다. 브루트포스와 짬뽕인 문제인것같다. 지도의 크기가 최대 8x8 이라 순열을 이용하여 모두 탐색해도 시간 초과는 나지 않는다. 모든 케이스마다 casemap 배열을 초기 map과 같게 해주고 바이러스가 들어있는 좌표를 모은 큐도 다시 채워줘야 한다. a=v.size()-3 b=v.size()-2 c=v.size()-1 일 때는 모든 경우를 탐색했다는 뜻이므로 break문으로 빠져나와서, 안전 구역의 넓이의 최댓값을 출력하면 된 문제가 해결된다. #include #include #include #include #include #include #include using name.. 2020. 8. 11. [BFS, 난이도 중하] 백준 2468번 안전 영역 Case(물에 잠기는 최대 높이)별로 안전 지역이 모두 다르기 때문에 casemap이라는 임시 배열을 두었다. map배열의 각각 요소에 물에 잠기는 최대 높이를 빼준 배열이 casemap이 된다. 즉 casemap배열의 요소가 1이상이면 그 좌표는 안전 영역이 되는 것이다. 이 casemap 배열로 BFS를 수행하여 while문을 탈출할 때마다 group변수에 1을 추가하여 몇 개의 안전 영역 그룹이 생기는지 계산한다. 물에 잠기는 최대 높이를 1부터 99까지 99가지 경우에 대해 탐색하여 케이스별 group을 구해내면 된다. 케이스가 종료 될 때마다 ans의 최댓값을 업데이트 해나가며, 모든 케이스를 다 탐색 했을 때 최종 ans 값이 이 문제의 해답이 된다. #include #include #incl.. 2020. 8. 11. [BFS, 난이도 상] 백준 2206번 벽 부수고 이동하기 정답율 23%의 다소 까다로운편인 문제이다. 아무리 고민해도 해결하지 못한 비슷한 유형의 문제가 있었다. 그 문제는 백준 13460번의 구슬 탈출2 이였다. 주어진 예제는 다 돌아가는데.. 반례가 생기고 그 반례까지 돌아가게 하니 또 다른 반례가 생기고... 나 자신과의 혈전이었다. 구슬 탈출 2의 해결법이 정말 궁금했던 나는 Google Chance를 썼다. 이 유형의 문제는 구조체 와 모든 방문경우 를 다뤄야 한다는 사실을 깨닫고 내가 깨달은 해당 유형의 문제 풀이법을 4줄 요약해보았다. 한 map 안에 여러 물체가 동시에 움직여야 하는 경우 구조체 이용 2개 이상의 물체가 겹칠 수 없는 경우의 처리 -> 겹침의 여부에 상관없이 일단 논리적으로 모두 이동시켜놓은 후에 조건에 맞게 2차 처리 수행 노드.. 2020. 8. 10. [BFS, 난이도 중상] 백준 2573번 빙산 지금까지 BFS를 풀어왔듯이 빙산이 몇 개의 덩어리로 되어있는지는 bfs의 while문이 끝날 때마다 1씩 추가하는 group변수의 최종 값으로 알 수 있다. bfs의 while문을 다 돌았다는 것은 덩어리 하나를 모두 방문했다는 의미다. BFS를 수행하기 전에 빙산이 녹을 때마다 즉, 1년마다 빙산이 녹은 상태로 map배열을 바꿔주어야 한다. 문제 해결 흐름은 1. map배열입력 2. 1년이 지난 후의 빙산상태로 map배열을 업데이트 3. BFS로 몇 덩어리인가 계산 4. 여전히 1덩어리일 경우 과정2번으로 이동, 2덩어리 이상일 경우 정답 출력 이런 흐름으로 이루어 진다. adjacent 배열은 주변에 인접한 바닷물칸의 수를 나타내는 배열이다. map 배열에서 빙산의 높이가 0보다 작아졌을 경우에는 .. 2020. 8. 10. [BFS, 합집합] 백준 11724번 연결 요소의 개수 (2가지 방법) BFS 기준으로는 난이도 하, 합집합 기준으로는 난이도 중하를 주고싶다. 1. BFS 알고리즘 꼬지 않은 평범한 BFS 문제이다. 평균 BFS 알고리즘 문제 정답율보다 높은 편인 46%의 정답율을 가지고 있는데 연결 요소가 몇 개인지, 다른 말로 몇 개의 연결그룹으로 되어있는지 계산하는 문제이다. FOR문으로 모든 정점을 탐색하여 방문하지 않은 노드에 대해서만 BFS를 수행하고, while문이 끝날 때 그룹 수를 1씩 더해주면 해결 된다. #include #include #include #include #include #include #include using namespace std; vector a[1001]; bool visited[1001]; int main() { ios_base::sync_wi.. 2020. 8. 9. 초보자가 하기 쉬운 서버 운영 실수 2가지 1. 127.0.0.1 ip주소 사용하지 않기 유튜브 웹서버 실습 강의 채널에 이런댓글을 많이 보았다."제 컴퓨터에서는 잘 뜨는데 모바일로는 안떠요" (예를 들어 댓글이 컴퓨터 ,모바일 따로 뜨는 문제에 해당)"다른 컴퓨터에서는 접근이 안되는데요?" "분명 그대로 따라했는데..." 결론부터 말하자면 클라이언트는 127.0.0.1(localhost) 라는 주소만으로 내 서버의 ip주소를 알지 못한다. 127.0.0.1 은 특수한 ip주소이며, 개인기기의 ip 주소를 뜻한다.아래 사진처럼 USER 마다 각자 IP주소 A,B,C,D가 있을텐데 이 유저들 개개인의 컴퓨터IP를 127.0.0.1로도 표기할 수 있다. 웹/앱 통신을 할 때 서버로 데이터를 전송하는데 이때 사용되는 파일 중 하나인 php 파일을 예로.. 2020. 8. 8. [BFS, 난이도 중] 백준 1697번 숨바꼭질 정답율은 약 24%로, 쉬운 문제는 아니다. 하지만 이 문제가 왜 BFS 알고리즘을 요하는지 이해한다면 그렇게 복잡한 문제는 아니다. 개인적으로 이 문제의 정답율이 낮은 이유는 주어진 예제가 하나 뿐인 이유도 있겠지만, x좌표의 범위에 대한 처리가 헷갈려서 그렇다고 생각한다. 예를 들어 x좌표가 0일 경우에는 뒤로 갈 수 없고 x좌표가 50000을 초과하는 경우에는 순간 이동을 할 수 없다. 이에 대한 처리를 부가적으로 해줘야 한다. 이 문제는 1차원 BFS 문제이다. 수빈이의 초기 x좌표를 큐에 넣고 시작한다. 방문 여부는 time배열의 값이 0인지 아닌지를 따졌다. (0 -> 아직 방문 안함) 본인은 초기 시간을 1로 설정했기 때문에 time배열의 k(동생좌표)인덱스값 time[k] 에서 1을 뺀 값.. 2020. 8. 8. [BFS, 난이도 중하] 백준 7576번 토마토 https://kimcoder.tistory.com/16 [BFS, 난이도 하] 백준 2178번 미로 탐색 이제 BFS 응용문제다. 이 문제를 풀면 대충 BFS가 뭔지 감이 잡힐 것이다. BFS의 원리와 소스코드를 모른다면 이 글을 읽고 오는 것을 추천한다. https://kimcoder.tistory.com/15 [BFS, 난이도 하] 백준 1260번 D kimcoder.tistory.com 미로 탐색 문제처럼 time 배열을 쓸것이다. 다시 한번 설명 하지만, time배열은 각 좌표의 토마토가 언제 익게 되었는지의 시각을 의미 한다. 미로 탐색 문제와 다른 점은 시작점이 꼭 하나는 아니라는 것이다. 즉, BFS의 while문을 수행하기 전에 큐에 여러 좌표를 넣고 시작할 수도 있다는 것이다. 이 것 .. 2020. 8. 8. [BFS, 난이도 중하] 백준 1012번 유기농 배추 https://kimcoder.tistory.com/17 [BFS, 난이도 중하] 백준 2667번 단지번호붙이기 이 문제 같은 경우에는 1의 그룹이 몇개인가를 찾으면 된다. 이중 for문으로 방문되지 않은 '1' 요소를 찾아 그 좌표를 큐에 넣고 BFS를 수행해주면 된다. 맨 먼저 (0,1) 좌표를 중심으로 bfs가 수행되 kimcoder.tistory.com 단지번호붙이기 문제와 풀이법이 비슷하다. 약간 차이점이 있다면 테스트 케이스가 있으며, 가로와 세로의 길이가 따로 주어진다는 것이다. 가로, 세로 따로 주어진다는 사실을 못보고, 단지번호붙이기 소스코드를 그대로 복붙해서 테스트케이스 반복문만 추가해줬다가 이유도 모른채 틀렸습니다 라는 문구를 보게 되는 피해자는 발생하지 않기를 빈다. 마치 나처럼 그.. 2020. 8. 8. 이전 1 ··· 60 61 62 63 64 65 다음
