개인사

[G3] 백준 1600번 말이 되고픈 원숭이 C++ 너비 우선 탐색, 우선순위 큐, 시뮬레이션

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

[G3] 백준 2146번 다리 만들기 C++ 너비 우선 탐색, 플러드 필, 우선순위 큐

리뷰 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에..

리뷰 https://www.acmicpc.net/problem/2230투 포인터를 사용하여 O(N)의 시간 복잡도로 풀 수 있는 문제  전역 변수n : 수열의 길이를 저장할 변수m : 두 수의 최소 차이를 저장할 변수ans : 정답을 저장하기 위한 변수lst : 수열의 정보를 저장하기 위한 정수형 배열 함수없음  문제풀이n, m값을 입력 받고, n개의 원소를 lst배열에 입력 받아준다.lst배열을 오름차순으로 정렬해 준다.두개의 포인터 l, r을 각각 0으로 초기화 해준다.l이 n - 1보다 작다면 반복하여 루프를 실행해 준다.정수형 변수 diff에 lst의 r번 인덱스값에서 l번 인덱스 값을 뺀 값을 저장해 준다.만약 diff가 m이상이라면 ans와 diff를 비교하여 더 작은 값을 ans에 저장해 준..

리뷰 https://www.acmicpc.net/problem/1744처음엔 백트래킹을 통한 완전 탐색을 통해 구현하였지만 N값이 50이라 당연하게도 시간 초과가 났다.이후 우선순위 큐를 사용해 그리디하게 구현하였고, 음수끼리 묶은 경우 양수가 나오는 점을 그리디하게 수정하였더니 AC를 받게 되었다.  전역 변수n : 수열의 길이를 저장할 변수ans : 정답을 저장하고 출력하기 위한 변수p : 1이상의 수를 저장하기 위한 우선순위 큐m : 0이하의 수를 저장하기 위한 우선순위 큐 함수없음  문제풀이n을 입력받고 n개의 원소를 정수형 변수 num에 입력 받아준다.만약 num이 0이하라면 m에, 1이상이라면 p에 push를 해준다.p가 빌 때까지 루프를 돌며 정수형 변수 num에 p의 top인 요소를 뽑아준..