고동치는고동

10진수를 2진수로 표현할 수 있는지 파악하는 문제이다 2019 * 2021 = 4080399이다. 10진수를 2진수로 바꿀 때는 1이 될때까지 2로 나누면서 나머지를 오른쪽 끝에 쌓아주면 된다. ex) 11 11/2 = 5...1 5/2 = 2...1 2/2 = 1...0 1 11은 이진수로 표현했을 때 1011이다. 4080399를 2진수로 표현하면 4080399/2 = 2040199...1 2040199/2 = 1020099...1 1020099/2 = 510049...1 510049/2 = 255024...1 255024/2 = 127512...0 ... 따라서 오른쪽 끝 1의 개수는 4개이다 답) 4 3부터 15의 합은 18*6+9 = 117이다. 따라서 빠진 수는 11 답) 11 첫번째 자리는..

1. 먼저 a와 b를 비교하여 더 큰수를 찾는다. (a라고 가정) 2. c와 a를 비교한다. (만약 c가 a보다 크다면 크기 순서는, c > a > b 이다) 3. c가 a보다 작다면 c와 b를 비교해서 크기 순서를 결정하면 된다. 이는 a와 b중 큰 수가 b일때도 마찬가지이다 답) 3 파란색 점은 사람이고 검정색 선은 친구간의 인사이다 총 합해서 10번의 인사가 진행되어야 하며, 1분에 두쌍식 인사를 한다고 해도 적어도 5분의 시간이 걸린다. 5분안에 모든 쌍이 인사를 하는 전략은 다음과 같다. 서로 평행하는 쌍끼리 인사를 진행하면, 1분에 2쌍식 5분안에 모든 쌍이 인사를 진행할 수 있다. 답) 5 두개의 서로 다른 주사위를 굴렸을 때 나올 수 있는 모든 경우의 수는 36가지이다. (6 * 6) 이렇..

문제 링크 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net bfs를 이용한 탐색 문제이다 기존의 탐색에서 벽을 한번 부수고 이동할 수 있다는 조건이 붙었기 때문에 구현하는데 어려움이 생겼다 이럴경우 각 좌표까지 최단거리를 두가지 상황으로 정리하면 쉽게 풀 수 있다 1. 벽을 뚫지 않고 격자까지 이동한 경우 2. 벽을 한번 뚫고 격자까지 이동한 경우 1번의 경우 벽이 없는 길로 1을 갱신하거나 벽을 뚫으면서 2의 ..

문제 링크 : https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파� www.acmicpc.net 주난이가 점프를 할 때마다 주난이를 둘러싸고 있는 친구들의 벽이 사라진다 즉, 주난이가 한번 점프를 하면 자신부터 탐색을 시작해서 탐색 경계를 제한하는 친구들이 사라지는 것이다 구현 방법은 bfs든 dfs든 상관없다. 중요한 것은 주난이부터 탐색을 시작해서 친구를 만나면 그 친구는 이번 점프로 제거된다는 것이다. 또한 친구가 제거되었으면 거기서는 탐색을 중지하고 돌아와야..

문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 익은 토마토가 중심이 되어서 bfs탐색을 하는 문제이다 대충 그림으로 표현하자면 다음과 같다 검정색 테두리는 토마토들이 담긴 격자이고 빨간색 동그라미가 초기 익은 토마토이다 초기 익은 토마토에서부터 파란색 -> 초록색 순서대로 bfs탐색을 하면서 안익은 토마토가 범위 안에 들어오면 익게 하고 모든 토마토가 익을때 까지 계속 탐색하면 된다. 물론 bfs는 진행할 수 ..

문제 링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 1번부터 dfs를 돌며 탐색한 노드의 수를 세는 문제이다 #include // 인접행렬 int map[101][101] = { 0 }; // 노드를 방문했는지 저장하는 visit 배열 int visit[101] = { 0 }; int computer_num, ans = 0; // 감염된 사람을 전부 찾아내는 dfs void dfs(int n) { ans++; // dfs 한번 돌때마다..

문제 링크 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 격자상에서 dfs를 활용하여 푸는 문제이다 dfs를 사용하는 방식은 아래의 문제와 매우 유사하다 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u,..

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 격자상의 그래프에서 bfs 탐색을 하는 문제이다 기존 bfs와 다른 점이라면 1. 그래프 이동을 격자상의 상하좌우로 한다. (dx, dy 배열) 2. 격자 한칸이 노드이므로 격자 정보가 x,y 두가지 정수로 다뤄진다 (node 구조체) #include #include #define n_ 100+5 using namespace std; int n, m; int arr[n_][n_]; int dp[n_][n_]; //..

문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 연결요소란 말 그대로 서로 연결되어 있는 요소의 개수이다. 이 그래프 같은 경우 한개의 그래프가 두개의 연결요소로 분리되어 있는 것이다 만약 두 연결요소를 간선을 통해 이었을 경우에는 그래프안의 연결요소가 하나로 통합된다 구현방법은 dfs를 기반으로 한다 1번부터 n번 노드까지 순회하며 탐색되지 않은 노드에서부터 df..

문제 링크 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 백준에 있는 예제를 통해 막대 개수를 세는 알고리즘을 짜 보자 확실한 것은 막대기를 자르는 레이저가 최종 막대의 개수를 결정하는 요소라는 것이다 레이저가 막대기를 관통하는 것은 하나의 막대기가 두개로 분할되는 것이 아니라 하나의 막대기의 일정 부분을 잘라서 새로운 막대기를 만들어내는 것이다 결국 똑같은 말이지만 관점을 다르게 해야 쉽게 막대의 개수를 셀 수 있는 방법이 보인다 먼저 모든 막대..