본문 바로가기

Algorithm

 (71)
백준/ 바킹독님의 문제집/ 재귀함수가 뭔가요?(17478) 문제 설명 문제 해결 띄어쓰기 한 글자라도 틀리면 아예 틀렸다고 판정할만큼 까다롭다. 함수의 정의는 void func(int count)으로 해줬다.재귀 함수의 base condition은 count == N으로 설정했다.재귀식은 func(count + 1)로 설정하여 count를 차근차근 증가시키면된다. mask라는 함수를 만들어줬는데 count가 증가함에 따라서 "____"를 더 출력해주는 함수다. #include #include #include #include #include #include #include #include #include using namespace std; int N; void mask(int count) { for (int i = 0; i
백준 / 바킹독님의 문제집 / Z(1074) 문제 설명 문제 해결 일단 시간 제한이 0.5초로 매우 짧다.배열을 선언하여 재귀적으로 Z 모양으로 순회한다면 시간 제한에 걸릴 것 같다.N이 15라면 배열의 크기는 215×2152^{15} \times 2^{15}215×215 정도까지 커지기 때문이다. 저 정도 시간 제한이라면 순회가 아니라 단순 연산 정도로 끝나야 알맞을 것 같다.그렇다면 순회하지 않고도 r행 c열을 몇 번째로 방문했는지 알 수 있을까? N이 2인 배열을 탐색하려고 하고, r이 1, c가 2라면 6이라는 숫자를 어떻게 만들 수 있을까?2N−1×2N−1+f(N−1,r,c−2N−1)2^{N-1} \times 2^{N-1} + f(N-1,r,c - 2^{N-1})2N−1×2N−1+f(N−1,r,c−2N−1) 요런 형태로 재귀해주면 될 ..
백준 / 바킹독님의 문제집 / 안전 영역(2468) 문제 설명 문제 해결 해당 문제도 BFS를 이용하여 풀었다. 일단 비에 양에 따라 달라지는 안전 지역의 개수를 계산하기 위해서 맵에 입력된 지역의 높이 중, 최대 높이가 얼마인지 구했다. 그리고 0부터 시작하여 최대 높이 직전까지 비가 내렸을 때 최대 얼마나 많은 안전 지대가 나오는지 확인했다. #include #include #include #include #include #include #include #include #include #define x first #define y second using namespace std; int N, max_height = 0; int map[101][101]; queue q; pair direction[4] = { make_pair(1,0), make_pai..
백준 / 바킹독님의 문제집 / 영역 구하기(2583) 문제 설명 문제 해결 통상적으로 우리가 배열을 사용할 때, 아래쪽로 y값이 증가하고, 오른쪽으로 x값이 증가한다. 하지만 문제에서 사용하는 좌표계는 인간에게 맞춰져 있다. 일단 입력은 그대로 받고, 연산할 때 인간 기준으로 맞춰서 BFS를 실행하면 문제를 해결할 수 있다. #include #include #include #include #include #include #include // 문제에서 사용하는 좌표 시스템이 기존에 사용하던 방식이랑 다르다. // 기존은 아래, 오른쪽으로 숫자가 커졌다면 지금은 위, 오른쪽으로 숫자가 커지는 형태 // 입력은 기존에 사용하던 방식을 그대로 쓰고, BFS 탐색할 때는 좌표를 뒤집어 사용하면 된다. #define x first #define y second usi..
백준 / 바킹독님의 문제집 / 단지 번호 붙이기(2667) 문제 설명 문제 해결 테스트 케이스를 하나 더 늘렸다. 4 4 0101 1010 0101 1010 잘못된 결과가 나와서 코드를 삼항 연산자를 이용하여 살짝 수정했다. #include #include #include #include #include #include #include #define x first #define y second using namespace std; queue q; pair direction[4] = { make_pair(1,0),make_pair(0,1), make_pair(-1,0), make_pair(0,-1) }; vector house_count_list; int map[30][30]; int visit[30][30]{ 0 }; int apt_comp_count = 0; ..
백준 기록-7 토마토 익히는데 BFS, 배추 심는데 BFS, 그림 세는데 BFS, 숨바꼭질하는데 철수 순간이동이라는 특수능력도 쓴다. 그래도 문제를 보면, "엇 이거 BFS 또는 DFS 써서 푸는 문제일 것 같아!"라고 추측까지 할 수 있게 됐다. 몇 일만에 다 풀기엔 문제가 너무 많아서 천천히 진도를 나가야겠다.
백준 / 바킹독님의 문제집 / 불!(4179) 문제 설명 문제 해결 불에 대한 BFS를 돌려서 불이 어떤 좌표에 얼마나 많은 시간이 지나서야 붙는지 저장하고 거기서 구한 데이터를 이용해 지훈이로 BFS를 돌려서 탈출에 얼마나 시간이 걸리는지 계산한다. 지훈이로 BFS를 돌릴 때 어떤 조건을 줘야 잘 돌아갈지 많이 고민했다. #include #include #include #include #include using namespace std; #define x first #define y second string map[1000]; int fire[1000][1000]; int human[1000][1000]; int main(int argc, char* argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr)..
백준 / 바킹독님의 문제집 / 미로 탐색(2178) 문제 설명 문제 해결 방문 했는지 안했는지 검사하고 current의 값 + 1 값을 다른 좌표에다가 옮기는 형태로 문제를 해결했다. #include #include #include #include #define x first #define y second using namespace std; int N, M; int map[100][100]; int visit[100][100]{ 0 }; int result[100][100]{ 0 }; int min_ = 1; queue q; pair udlr[4] = { {1,0},{0,1},{-1,0},{0,-1} }; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(nullpt..
백준 / 바킹독님의 문제집 / 그림(1926) 문제 설명 문제 해결 아직 그래프 자료구조는 잘 모르는 상태이지만 BFS 관련 강의는 어느 정도 들었으므로 문제를 풀어봤다. 바킹독님의 강의에서 BFS 구현의 정석으로 제공해주신 코드를 변수 이름만 나에 맞게 바꿨다. 그림의 개수나 최대 크기 등의 정보를 추가로 알아내야 하는데 기존의 BFS 코드의 이중반복문을 따로 추가하여 검사하고 중간중간 그림의 크기를 비교하는 코드를 넣어서 문제를 해결했다. #include #include #include #define x first// first를 x로 별칭 #define y second// second를 y로 별칭 using namespace std; int N, M;// 세로, 가로 길이 int board[500][500];// 도화지의 색칠 정보 int vi..
백준 기록-6 스택의 활용을 해봤다. 쇠막대기까지는 그나마 괜찮았지만 괄호의 값, 탑부터 난이도가 많이 어려워졌다. 아직 알고리즘에 대해서 모르는 것이 많다. 일단 다시 한 번 정리할 필요성이 존재하겠다. 실버로 승급했다. 빠르게 나아서 골드까지 가보자.

티스토리툴바