병원 갔다온 이후 일주일간 약 안 먹고 살다가 감기가 더 심해졌다.. 그래서 일주일간 내 맘대로 살았다가 다시 문제 풀어 봤는데 뭔가 코드 치는게 어색하다. 이래서 꾸준함이 중요한건가 백준 풀이 - BFS 연습문제 문제리뷰 2573 빙산 : 얼음을 한꺼번에 녹여야 하는데 녹이는 순서를 줘서 처음에 틀림 2573 빙산 #include using namespace std; #define X first #define Y second int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int n, m; int iceberg[300][300]; int vis[300][300]; int melt[300][300]; int GetSplitNum() { for(int i = 0..
백준 풀이 - BFS 연습문제 (응용) 문제리뷰 2206 벽 부수고 이동하기 : 벽을 안 부순 거리와 부순 거리 둘다 저장하기 >> 계속 시간 초과 나서 결국 답 봤다 ㅠㅠ [std::tie tuple로 저장된 정보를 변수에 한번에 할당하기 ] queue q; q.push({1, 2, 3}); int x, y, z; tie(x, y, z) = q.front(); 13549 숨바꼭질 3 : 숨바꼭질 1 모범 코드를 많이 참고해서 다시 풀어보면 좋을듯 >> 2X가 X+1, X-1보다 시간이 적게 걸리므로 먼저 처리해야 최단 시간을 구할 수 있음 2206 벽 부수고 이동하기 초기 코드 (시간초과) 벽 하나하나를 '0' 으로 바꿔서 BFS 돌리기 N > n >> m; for(int i = 0; i < n; i+..
백준 풀이 - BFS 연습문제 문제리뷰 1012 유기농 배추: 테스트 케이스가 하나의 입력에 여러 개이기 때문에 초기화를 map과 vis 둘 다 해줘야 함. 7569 토마토 : Tuple 사용방법 익히기 // tuple 생성1 tuple t = make_tuple(1, 2, 3)l // tuple 생성2 - C++11 tuple t = {1, 2, 3} // tuple 값 가져오기 int i = get(t); int j = get(t); int k = get(t); 5427 불 : BFS 두번 돌리는거 헷갈려.. 상근이의 이동 시간이랑 불 시간 비교할 때 변수 잘못 써서 헤맴. >> (dist2[cur.X][cur.Y] + 1 >= dist1[nx][ny] 랑 비교해야하는데 dist2[nx][ny]랑 비..
백준 풀이 - BFS 예제 문제리뷰 2178 미로 탐색 : 초기화 - fill함수 / dist를 -1로 초기화해서 vis 변수를 없앨 수 있음 7576 토마토 : 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구해야한다는 관점 >> (최단 거리 구하는거랑 연결지을 수 있어야 함) 4179 불! : if(dist2[nx][ny] >= 0 || miro[nx][ny] == '#') continue; >> (조건 빼먹어서 메모리 초과 계속 발생함), 지훈이 이동 시간을 새로운 변수로 둬서 계산하는 방법 기억하기 1697 숨바꼭질 : 범위를 내맘대로 0 ~ 100,000로 잡았는데 넘어갈 수 있다! 단, *2를 하면 -1로 이동해야하므로 200,000까지 범위로 잡는게 적절하다. ..
백준 풀이 - BFS 기본 문제 문제리뷰 1926 그림 처음에는 시작점 위치 넣는 코드 위치 때문에 헤매고 두번째는 범위 설정을 잘못해서 헤맸다. 범위를 nx > n || ny > n 으로 작성했음 ㅋㅋ => 범위는 nx = n || ny = m 1926 그림 #include using namespace std; #define X first #define Y second int n, m; int canvas[500][500]; int vis[500][500]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; queue Q; int cnt; int maxArea = 0; int main(void) { ios::sync_wi..
참고 내용 https://blog.encrypted.gg/941 정의 그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 BFS(Breadth-First Search) : 너비 우선 탐색 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 BFS 과정 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 2번을 반복 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) 주의할 점 시작점에 방문했다는 표시를 남기지 않는다. 큐에..
백준 풀이 - 스택의 활용 문제리뷰 10799 쇠막대기 2504 괄호의 값 : 숫자를 스택에 넣어서 구현함. 아스키코드 고려해서 음수를 넣어야 함. => 정답 코드를 보니 훨씬 간단하지만 내가 떠올릴 수 있을지는 잘 모르겠음. 10799 쇠막대기 #include using namespace std; int result; string str; stack S; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> str; int stick = 0; char prev = str[0]; for(char c : str) { if(S.empty() || c == '(') S.push(c); else if (c == ')' && c == prev) { S.pop(); ..
참고 내용 https://blog.encrypted.gg/936 정의 수식의 괄호쌍이란? EX) (()) ()(), > 괄호의 쌍이 예시와 같이 올바른지 판단하는 문제 괄호 쌍이 올바른지 판단하는 방법 주인장의 생각 열린 괄호 = '(' 닫힌 괄호 = ')' 열린 괄호가 닫힌 괄호보다 먼저 나와야 함 열린 괄호가 있으면 닫힌 괄호가 반드시 따라와야 함 타인의 방법 안쪽부터 짝 맞추기 열린 괄호의 개수 = 닫힌 괄호의 개수 구현 배열 : 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2) 연결리스트 : O(N) 스택 : 닫힌 괄호는 가장 최근에 들어온 여는 괄호와 짝 지어 없애자 해결 방법 1. 여는 괄호가 나오면 스택에 추가 2. 닫는 괄호가 나올 경우 2-1 스택이 비어 있으면 올바르지 않은 괄..
