글쓰는공대생의 IT블로그

출처 => https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 첫째 줄에 A/B를 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다. 예제 입력 1 복사 1 3 예제 출력 1 복사 0.33333333333333333333333333333333 10-9 이하의 오차를 허용한다는 말은 꼭 소수 9번째 자리까지만 출력하라는 뜻이 아니다. 예제 입력 2 복사 4 5 예제 출력 2 복사 0...

문제 길이가 n인 배열에 1부터 n까지 숫자가 중복없이 한 번씩 들어 있는지를 확인하려고 합니다. 1부터 n까지 숫자가 중복없이 한 번씩 들어있는 경우를 true, 아닌 경우를 false를 반환하도록 함수 solution을 완성해주세요. 제한사항 배열의 길이는 10만 이하입니다. 배열의 원소는 0이상 10만 이하인 정수입니다. 입출력 예 arr=[4,1,3,2] result=true arr=[4,1,3] result=false 소스코드 및 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; bool solution(vectorarr) { bool a..

출처 => https://www.acmicpc.net/problem/1920 문제 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 사고의 흐름 ▶ 선형탐색을 통해 쉽게 구현할 수 있지만 그렇게 하게 되면..

출처 => https://www.acmicpc.net/problem/2178 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. ..

출처 => https://www.acmicpc.net/problem/2667 문제 사고의 흐름 ▶ 전형적인 깊이우선탐색 알고리즘을 이용한 문제이다. ▶ 크게 2가지의 포인트를 잡아야 한다. >> 첫 번째 포인트! 1이 발견되면 그 점을 중심으로 왼쪽 오른쪽 위 아래를 조사하는 것. ▶ 나의 풀이에서는 dx[]와 dy[] 배열을 이용하였다. 주위에 있는 x좌표와 y좌표를 nx와 ny로 설정하고 nx=x+dx[i] ny=y+dy[i]로 선언한다. i가 증가할 때마다 x와 y에 값을 더해준다. ▶ 여기서 중요한 것은 아래의 소스코드처럼 i번째의 숫자는 dx[i]와 dy[i]가 달라야 한다. 만약 0으로 같거나 1,-1로 둘이 같게 된다면 이동하지 않거나 대각선으로 이동하기 때문이다. dfs에서의 움직이는 방향..

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)] 문제 문제 분석 문제의 의도: 단순 비선형 탐색이 아니라, 두더지 굴을 나타내는 숫자인 1을 중심으로 상,하,좌, 우에 1이 있다면 이 부분에 간선이 있는 것으로 생각한다. (0,0)에서 순차 탐색을 하여 그 값이 1이라면 그 점을 중심으로 깊이우선탐색을 하여 모든 연결된 점을 방문한다. 풀이 이런 식으로 마지막 칸까지 진행을 한다면 다음과 같은 결과가 나온다. => 따라서 각 굴의 크기는 7, 8, 9라는 사실을 알 수 있다. 소스코드 & 결과 #include #include using namespace std; int n, A[101][101], cnt, Size[101]; void input() { cin >> n; for (int ..

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)] 문제 문제 분석 문제의 의도 : k를 초과하는 가장 첫 번째 원소의 위치를 구하는 것 ① 먼저 구간을 설정한다. ([s, e]) ② 이 구간의 중간위치의 값을 m이라고 하면, A[m-1]k 인 최소 m을 찾아야 한다. 풀이 => 예시로 주어진 배열 A는 1,2,7,7,7,7,11,15이다. k의 값은 7이다. 따라서 출력값은 7이 나와야 한다. => 주어진 배열은 [0,8]이고 이에 따라 중간값의 위치인 m은 4이다. 우리가 원하는 것은 찾으려는 값의 위치가 아니라 k값보다 큰 수가 처음으로 등장하는 위치이다. A[4]=7이므로 우리의 위치와 일치하지 않다. => A[6]>7 이므로 그보다 아래로 범위를 설정하여 재탐색 =>A[5]=7이므..

문제 출처입니다. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 사고의 흐름 2x1 타일링을 할 때부터 차례대로 하여 규칙을 찾아내보록 한다. 그 결과, 2x1일때는 1, 2x2 일때는 2, 2x3 일때는 3, 2x4 일때는 5, 2x5 일대는 8이라는 결과가 나온다. 그런데 2x5 타일링을 분석하면 다음 그림과 같다. 즉, 5번째 타일링은 3번째와 4번째 타일링을 더한 값이다. 즉 피보나치 수열로 나타낼 수가 있다. 해결방법 1 2 3 4 5 6 7 8 9 10..

문제 출저 입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사고의 흐름 일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다. 모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다. 다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 해결방..

문제 출저 입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사고의 흐름 일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다. 모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다. 다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 해결방..