본문 바로가기

백준 문제풀이18

1987 : 알파벳 (C++) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹기법을 사용하여 푼 문제이다. 백트래킹을 사용했기 때문에 visit배열을 따로 사용하지 않았다. #include #include using namespace std; int map[20][20]; bool check[26]; int R, C; int result = 0; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; void dfs(int x, int y, int cnt) { for(int i = .. 2021. 2. 9.
1934 : 최소공배수 (C++) 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 최소공배수는 먼저 최대공약수를 구한 후 A와 B를 곱한 값에 최대공약수로 나누어주면 최소공배수를 구할 수 있다. #include using namespace std; int gcd(int A, int B) { int temp = 0; while(B > 0) { temp = B; B = A % B; A = temp; } return A; } int lcm(int A, int B) { return (A * B) / gcd(A, B); } int .. 2021. 2. 9.
1010 : 다리 놓기 (C++) 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 > testCase; for(int i .. 2021. 2. 9.
2206 : 벽 부수고 이동하기 (C++) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 푸는데 오랜 시간이 걸렸던 문제. 결국 남의 코드를 보고 생각하며 다시 풀었다. 너무 어려오~ 더 많이 연습하고 문제 풀어서 열심히하자 #include #include #include #include using namespace std; #define MAX 1001 int map[MAX][MAX]; int visit[MAX][MAX][2]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1};.. 2021. 2. 9.
7569 : 토마토 (C++) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 백준 7576번 : 토마토의 3차원 버전인 문제이다. 3차원 배열을 처음 써봐서 조금 헷갈렸지만 그래도 금방 풀었다! 여러가지 C++에 내장된 함수들을 써보는듯. 다른 글들을 보니 pair이런 방법도 쓴 사람도 있었다. #include #include #include using namespace std; #define MAX 100 int map[MAX][MAX][MAX]; bool visit[MAX][MAX][MAX]; int dx[6].. 2021. 2. 8.
1697 : 숨바꼭질 (C++) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 전에 처음 이 문제를 봤을 때 문제에 어떻게 접근을 해야 할 지 몰라 안풀고 있었는데 오늘 그냥 한번 부딪혀 보자라는 마음으로 문제를 풀어봤다. BFS로 풀어봤다. #include #include using namespace std; int N, K; int map[100001]; bool visit[100001]; int dx[3] = {1, -1, 2}; void bfs(int x) { queue q; visit[x] = true;.. 2021. 2. 8.
1926 : 그림 (C++) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 전형적인 그래프 탐색 문제이며 단계별로 풀어보기에서 DFS와 BFS단계 문제를 풀어보면 쉽게 풀 수 있다. 총 그림의 개수와 가장 넓은 그림의 넓이를 저장할 변수를 만들고 DFS나 BFS를 실행 할 때마다 그림의 개수를 세고, 그림의 넓이를 센다. #include #include using namespace std; #define MAX 500 int map[MAX][MAX]; bool visit[MAX][MAX]; int N, M; int cnt = 0; int t.. 2021. 2. 8.
2576 : 홀수 (C++) 2576번: 홀수 7개의 자연수가 주어질 때, 이들 중 홀수인 자연수들을 모두 골라 그 합을 구하고, 고른 홀수들 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어, 7개의 자연수 12, 77, 38, 41, 53, 92, 85가 주어지 www.acmicpc.net 기본적인 구현문제. #include using namespace std; int main() { int arr[7]; int odd[7]; int cnt = 0; int total = 0; for(int i = 0; i > arr[i]; if(arr[i] % 2 == 1) { odd[cnt++] = arr[i]; total += arr[i]; } } int min = 100; for(int i = 0; i < .. 2021. 2. 5.
2583 : 영역 구하기 (C++) 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 알고리즘 문제 푸는데 있어서 2차원 배열과 수학에서 사용하는 그래프의 x축과 y축의 방향이 다르다 보니 헷갈렸었지만 이제는 거의 완벽하게 이해하고 문제를 풀 수 있는 것 같다. 먼저 크기 값과 직사각형의 갯수를 받고 좌표값들을 받은다음 직사각형 좌표들을 모두 방문처리 한다. 그다음 각각 DFS 또는 BFS를 실행하여 분리된 영역의 개수와 각 영역의 넓이를 vector에 입력받고 오름차순으로 정렬한 후 출력한다. #include #include.. 2021. 2. 5.

티스토리툴바