개인사

[G3] 백준 14442번 벽 부수고 이동하기 2 C++ 너비 우선 탐색, 우선순위 큐

리뷰 https://www.acmicpc.net/problem/14442어우 AC를 받긴 했는데 메모리는 둘째 치고 시간이 꽤나 올래걸려서 놀랐다. 유사 문제 [G2] 백준 16946번 벽 부수고 이동하기 4 C++ BFS, FloodFill, 너비 우선 탐색리뷰 일반적인 BFS를 사용하니 바로 시간 초과가 출력되었다!!벽을 의미하는 1을 보기 보단, 0부터 본 후에 1을 체크하는 방식이 효율적인 문제였다. 위에서부터 차례대로 group정보를 배열, 벡터,zzzz955.tistory.com  전역 변수n : 맵의 세로 길이를 저장하기 위한 변수m : 맵의 가로 길이를 저장하기 위한 변수k : 부술 수 있는 벽의 개수를 저장하기 위한 변수Pos : 시뮬레이션 시 사용하기 위한 구조체, x, y좌표와 걸린 ..

[G3] 백준 2638번 치즈 C++ 너비 우선 탐색, 해시맵, 구현, 시뮬레이션

리뷰 https://www.acmicpc.net/problem/2638적어도 2번 이상 외부 공기에 노출되면 치즈가 녹는 문제, 유사 치즈문제보다 살짝 더 조건이 까다로웠다.  유사 문제 [G4] 백준 2636번 치즈 C++ 너비 우선 탐색, 플러드 필, BFS, Flood Fill리뷰 https://www.acmicpc.net/problem/2636매 시간이 지날 때 마다 공기 근처에 있는 치즈가 녹는 전형적인 플러드 필 문제  전역 변수n : 맵의 세로 길이를 저장할 변수m : 맵의 가로 길이를 저장할 변수rzzzz955.tistory.com  전역 변수n : 맵의 세로 크기를 저장할 변수m : 맵의 가로 크기를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열lst : 맵 정보를 저장하기 위..

리뷰 https://www.acmicpc.net/problem/1600방향 배열을 두개 사용하고, 방문 배열을 3차원으로 사용하여 푼 문제  전역 변수k : 말의 움직임을 할 수 있는 횟수를 저장할 변수w : 맵의 가로 길이를 저장할 변수h : 맵의 세로 길이를 저장할 변수lst : 맵 정보를 저장하기 위한 2차원 배열v : 말의 이동을 한 횟수를 기준으로 방문 처리를 하기 위한 3차원 배열hx, hy : 말의 이동을 진행할 방향 배열dx, dy : 4방향 이동을 진행할 방향 배열Pos : 맵 상에서의 이동을 기록할 구조체, 이동 횟수 t를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra()  너비 우선 탐색을 통해 시작점에서 목표지점까지 걸리는 최소 거리를 리턴하기 위한 함수..

리뷰 https://www.acmicpc.net/problem/2146섬을 그룹화 한 뒤 섬끼리 이을 수 있는 가장 짧은 경로를 구하는 문제그룹화 후 거리를 구하는 함수에서 일반 큐를 사용했더니 AC를 받지 못했다.디버깅 후 우선순위 큐를 사용하여 AC를 받은 문제, 디버깅의 중요성을 새삼 깨달았다.함수를 나누어 구현을 하다 보니 생각보다 로직이 길어진 문제, 100줄까지 갈지는 몰랐다.  전역 변수n : 맵의 한 변의 길이를 저장할 정수형 변수g : 각 섬을 그룹화 하기 위해 사용할 정수형 변수ans : 각 섬을 잇기 위한 최소한의 거리를 저장할 정수형 변수lst : 맵 정보를 저장하기 위한 정수형 2차 배열v : 그룹화 및 거리를 구할 때 사용할 방문 배열vg : 그룹 번호로 방문 표시를 하기 위한 ..

리뷰https://www.acmicpc.net/problem/1963에라토스테네스의 체... 오랜만에 접했더니 소수 판정에서의 엣지 케이스를 제대로 잡지 못했었다.그 외에는 소수를 문자열로 변환시켜 해시맵의 key로 활용하면 금방 풀 수 있는 문제  전역 변수t : 주어지는 테스트 케이스의 개수를 저장할 정수형 변수sosu : 초기 소수 정보를 저장하기 위한 정수형 배열s : 각 테스트 케이스 마다 주어지는 시작 소수를 저장할 문자열 변수e : 각 테스트 케이스 마다 주어지는 목표 소수를 저장할 문자열 변수Cur : 시뮬레이션 시 사용할 현재 문자열과 시간을 정의하기 위한 구조체dic : 소수 정보를 문자열로 파싱하여 저장하기 위한 해시맵 함수1. bfsint bfs() 시작 소수로부터 도착 소수로 까지..

리뷰 https://www.acmicpc.net/problem/11559게임 뿌요뿌요와 동일한 로직을 시뮬레이션 해서 몇 번 연속으로 연쇄반응 하는지를 구하는 문제매번 연쇄 반응 시마다 중력을 적용해 줘야 하는 구현도 진행해야 한다.  전역 변수lst : 맵 정보를 입력 받을 문자열 타입 배열v : 각 시뮬레이션 단계마다 사용할 방문 배열dx, dy : 4방향 탐색을 하기 위한 방향 배열n, m : 맵의 세로와 가로 크기를 지정할 변수ans : 몇 번 연쇄 반응 했는지를 저장하기 위한 변수Pos : 시뮬레이션 시 x, y좌표를 저장하기 위해 정의한 구조체 함수1. getDownvoid getDown() 중력을 적용하여 공중에 떠있는 뿌요들을 아래로 내리기 위한 함수m개의 열을 탐색하는 반복문을 수행해 준..

리뷰 https://www.acmicpc.net/problem/5427불을 피해 맵의 가장자리로 대피하는 시뮬레이션을 진행하는 문제 유사한 문제유사한 문제로 불! 문제가 있다, 해당 문제는 아래에 풀이 내용이 있으니 공유한다. 백준 4179번 불! C++리뷰어차피 불에 닿으면 타죽으니 범위를 지정해 주지 않아 OutOfBounds 에러가 떴다. 다시 생각해 보니 범위는 꼭 지정해 줘야 했다.기존의 BFS문제와 같지만 지훈이와 불의 입장에서 모두 생각해zzzz955.tistory.com  전역 변수t : 테스트 케이스의 개수를 저장할 변수w : 각 테스트 케이스의 맵의 가로 길이를 저장할 변수h : 각 테스트 케이스의 맵의 세로 길이를 저장할 변수lst : 각 테스트 케이스의 맵 정보를 입력 받아 저장할 ..

리뷰 https://www.acmicpc.net/problem/2636매 시간이 지날 때 마다 공기 근처에 있는 치즈가 녹는 전형적인 플러드 필 문제  전역 변수n : 맵의 세로 길이를 저장할 변수m : 맵의 가로 길이를 저장할 변수remain : 남아 있는 치즈 조각의 개수를 저장할 변수last : 치즈가 완전히 녹기 전 남아있던 치즈 조각의 개수를 저장할 변수ans : 치즈가 완전히 녹기 까지 걸린 시간을 저장할 변수lst : n * m크기의 맵 정보를 저장할 정수형 2차 배열v : 방문 처리를 체크하기 위한 정수형 2차 배열dx, dy : 4방향 탐색을 하기 위한 방향 배열Pos : 시뮬레이션에 사용하기 위한 좌표를 정의할 구조체h : 구멍 정보를 저장하기 위한 Pos타입의 큐c : 이번에 녹을 치..

리뷰 https://www.acmicpc.net/problem/2251세 물통의 상태를 체크하며 정답이 될 수 있는 모든 값에 대해 완전 탐색을 하는 문제물통의 상태를 관리하는 부분이 DFS를 사용하는 것이 좀 더 직관적이고 편해보이긴하다.  전역 변수A : A물통의 최대 부피를 저장할 정수형 변수B : B물통의 최대 부피를 저장할 정수형 변수C : C물통의 최대 부피를 저장할 정수형 변수v : 각 물통에 물이 차있는 경우를 방문처리할 3차원 정수형 배열ans : 정답을 저장하기 위한 set자료구조Status : 시뮬레이션에 사용할 각 물통의 정보를 정의할 구조체 함수1. bfsvoid bfs() 너비 우선 탐색을 통해 각 물통의 상태를 시뮬레이션 하고 정답을 저장하기 위한 함수Status타입의 큐 q를..

리뷰 https://www.acmicpc.net/problem/2295해시맵과 브루트포스 알고리즘을 통해 풀이한 문제수열 U의 원소가 2억보다 작거나 같은 자연수 이기 때문에 일반 배열로는 사용이 불가능하다.브루트포스 말고 이분 탐색으로도 접근 해봤는데 왠지 모르겠지만 AC를 받지 못해 그냥 완탐을 돌렸다.  전역 변수n : 수열의 길이를 저장할 정수형 변수U : 수열을 저장하기 위한 정수형 벡터dic : 임의의 두 원소의 값을 key로, 존재 여부를 value로 저장하기 위한 해시맵 함수없음  문제풀이n값을 입력 받고, U를 n만큼 크기를 resize해준다.U에 n개의 원소를 입력 받은 뒤에 오름차순으로 정렬해준다.수열 U를 2번 참조하여 중복이 가능하도록 임의의 두 원소를 더한 값을 key로 dic에..