본문 바로가기

전체

 (156)
[백준/C++] 2636번: 치즈 로봇청소기도 어려웠는데 이 문제도 어려웠다. 초등부문제라니 정말..^^ 풀이과정을 머릿속으로 떠올려보니, 1) while문을 돌리는데 종료조건은 2) initial함수: visit배열은 사이클을 돌 때마다 초기화해줘야 한다. 3) outAir함수: 외부공기와 내부공기를 구분해줘야 하는데 이는 dfs를 0,0칸에서 돌려주면 자동으로 구분된다. 그 이유는 치즈에 맞닿아있으면 dfs가 탐색을 못하기 때문에 자동으로 못들어간다. 외부공기를 새로운 visit배열에 표시를 해주었다. 4) melt함수: 모든 위치를 돌며 그 위치의 동서남북에서 visit배열의 표시가 하나라도 있으면 외부공기와 맞닿은 부분이 된다. 그래서 이부분을 녹이고, 기존 치즈 갯수에서 1을 빼준다. 5) 출력 만들기: 시간같은 경우 while..
[백준/C++] 9205번: 맥주 마시면서 걸어가기 맥주 마시면서 걸어가는게 참 힘든 일이라는 것을 깨닫게 된 날이다.. 이문제 뭔데 어렵냐ㅠㅠㅠ이해하는데 너무 오래걸려서 자괴감이 들지만 모르는 걸 하나 알게 되었다는 것에 감사하도록 하자. 이 문제의 경우 그래프가 주어지지 않았다. 그래서 직접 그래프를 만들어야 하는데 어떻게 만들어야 할 지 감이 잘 안왔다. 노드의 배열에 이런식으로 간선을 추가해본 적이 없어서 더 어려웠다. 결론적으로 정석풀이들을 참고하여서 코드를 완성했고 따라 쓰면서 이해한 정도다. 1) 메모리초기화 2) pair자료형의 벡터로 집 , n개의 편의점, 페스티벌 이렇게 n+2개를 입력으로 받는다. 3) 그래프를 생성한다. - 현재 노드로 부터 앞으로 갈 수 있는 노드에 대해서 모두 버틸 수 있는 거리라면 연결된 노드로 추가한다. - 여..
[C++ STL] algorithm헤더의 유용한 함수들(정렬, 최댓값, 최솟값) 코딩테스트 준비하면서 쓰고있는 함수들을 정리하려고 한다. 굳이 직접 짜서 쓰지 말고 STL을 잘 활용하는게 더 빠르고 편리하다. 배열과 벡터에 모두 적용하는 방법을 소개한다. (또 새로운 함수를 사용하면 추가로 작성할 예정이다.) 정렬하기: sort함수 그냥 사용하면 오름차순으로 정렬한다. (작은 것 -> 큰 것) #include using namespace std; int main() { int a[10] = { 9,3,5,4,1,10,8,6,7,2 }; sort(a, a + 10); for (int i = 0; i < 10; i++) { cout
[백준/C++] 5014번: 스타트링크 비교적 쉬운 문제이다. 최단경로!!!! 이기 때문에 고민없이 BFS로 풀이를 시작했다. 1) 이 문제는 1차원 bfs문제이다. 2) bfs의 종료조건은 원하는 층에 도달했을 때 3) queue에 담는 조건은 최저층~최고층사이 이면서 방문한 적이 없는 애들 #include #include using namespace std; int F, S, G, U, D; int dx[] = {0, 0}; int visit[1000001]; void bfs(int x, int d) { queue q; visit[x] = 1; q.push(make_pair(x, d)); while (!q.empty()) { int cx = q.front().first; int depth = q.front().second; q.pop();..
[백준/C++] 2468번: 안전영역 까다롭지 않은 문제였다. 나도 쉬우니 다들 잘 풀듯,,, 핵심은 비가 아예 안올지도 모른다는 것을 주의해야 한다는 점. 나도 첫제출때 이거땜시 틀렸다. 글고 문제도 약간 이해가 잘 안됐는데 그냥 비오는 높이를 1씩 늘려가면서 연결된 뭉탱이 갯수만 세면 된다. 비 온 높이를 계속 올리다가 4가 되었을 때 map: 비 온 높이를 계속 올리다가 6이 되었을 때 map: 반례는 하나만 보면 되는데 3 3 1 1 1 1 1 1 1 1 1 답: 1 풀이는 아래와 같이 했음 1) 비오는 높이가 0부터 제일높은 건물의 높이까지이다. 2) 높이를 0~최대높이까지 while문으로 돌렸다. 3) while문 내부에서 현재 높이에 대한 - DFS를 돌려서 뭉탱이의 갯수를 찾는다. - 걔를 vector에 push한다. 4) 모..
[백준/C++] 2573번: 빙산 (지저분쓰한 DFS풀이) 쉬워보여서 금방 풀 줄 알았으나 나는 난독증에 걸려있었다... 빙하가 녹을 때 1년이 지나면 1씩 녹는 줄 알았는데 알고보니 주변에 빙하가 아닌 부분이 있는 만큼 녹는 것이었다. 그래서 좀 오래걸렸고 좀 지저분하게 푼 것 같다.. (반례모음) https://www.acmicpc.net/board/view/19033 입력 빙산: 1년 지난 빙산: 2년 지난 빙산: 내가 풀었던 과정을 설명해보면, 1) while문 내부에서 2) 방문했는지 확인하는 visit배열과 몇개의 빙하의 높이를 얼마 빼야되는지 계산하는 cnt_0배열을 초기화 3) 종료조건1: 만약 얼음이 없다면 0을 출력하고 break 4) dfs함수를 통해 전체를 돌려서 몇덩이인지 센다. 5) 종료조건2: 만약 1덩이보다 많다면 년수 출력하고 br..
[백준/C++] 7579번: 토마토 토마토가 모두 익는 최단시간을 계산하는 문제이다. 최소비용 문제이고, 간선의 가중치가 1이고 정점과 간선의 개수가 적으면 BFS로 푸는 문제라고 한다... input 순서를 바꾸면 틀리는데 이유를 모르겠다.... (반례모음) www.acmicpc.net/board/view/43699 #include #include using namespace std; int ans; int M, N, H; int map[101][101][101]; int noToma; queue q; int dx[] = { 1, 0, 0, -1, 0, 0, }; int dy[] = { 0, 1, 0, 0, -1, 0, }; int dz[] = { 0, 0, 1, 0, 0, -1 }; bool allRipe(void) { for (int..
[백준/C++] 2644번: 촌수계산 코드는 간단하지만 나는 이해하는데 한참 걸린 것 같다. 1) 촌수는 결국 시작점에서 끝점으로 갈때까지 몇 개의 열을 거치느냐(depth)/거리가 있느냐를 따지는 문제와 같아진다. 2) map구성하기: 방향 역시 양방향 모두 같은 결론에 도달한다. 3->7을 가는 경로나 7->3을 가는 경로나 같은 결과를 낸다. 그러므로 map을 구성할 때 양방향 모두 똑같이 길을 만들어 주면 된다. 3) 또한 기존 2D map이 상하좌우로 이동할 수 있는 것과 달리 이 문제의 경우 한방향으로만 탐색을 진행해야 한다. 시작점이 7이기 때문에 7번째 행부터 탐색하기 시작한다. 처음엔 (7,2)에 방문한다(방문:2로 표시함). 주의할 점은 (2,7)에도 방문했다고 체크를 해줘야 된다.(둘이 같은 관계이므로) 그 다음엔 2번째..

티스토리툴바