백준 알고리즘 1100번 하얀 칸 문제입니다.

(참고 - https://www.acmicpc.net/problem/1100 )

코드)

#include <stdio.h>

char arr[8][8];

int main() {

int i, j, k, l, cnt=0;

for(i = 0; i < 8; i++) {

gets(arr[i]);

}

for(i=0; i<8; i+=2)

for(j=0; j<8; j+=2)

if(arr[i][j] == 'F')

cnt++;

for(k=1; k<8; k+=2)

for(l = 1; l<8; l+=2)

if(arr[k][l] == 'F')

cnt++;

printf("%d\n", cnt);

return 0;

}

- 이번 문제는 정수형 데이터를 가지고 노는것이 아니라 문자를 상대해야하는 문제입니다.ㅎㅎ

저는 2차원배열 arr[8][8]을 만들어주어 해결하였습니다.

그리고 arr배열에 gets함수를 이용해서 '.' 과 'F'에 대해 입력받도록 하였습니다.

(저는 gets함수를 빠르게 이용해보았지만 실제 사용시에는 fgets나, 다른 로직을 사용해보는 것을 권합니다.. 

gets함수는 입력받을 때에 크기를 지정받지 않기 때문에 버퍼 오버플로우를 유발할 수 있습니다. 

즉, 배열크기를 넘어가는 값을 입력받게되면 메모리의 어느영역에 저장 될 지 알 수 없다는 뜻입니다.!!)

그리고 이중 for문을 두번 사용하여 홀수줄, 짝수줄로 구분하여 F라는 글자를 탐색하며 카운트를 세주는 방법으로 해결 하였습니다.

(문제는 풀었지만 비효율적인 방법입니다.(__) 더 좋은 로직으로 해결하시길 바랍니다.)

이번 문제는 2차원 배열을 사용할 수 있는가, 문자에 대한 입력과 비교정도를 할 수 있는가 정도로 생각해봅니다.

+) 추가 -> 위의 로직을 아래와 같이 입력을 받는 순간부터, 비교구문을 이용하여 바로 Count를 해주면 좀 더 효율적으로 풀 수 있겠습니다.

for(i=0; i< 8; i++) {

for(j =0; j<8; j++) {

scanf(" %c", &a[i][j]);

if(((i % 2 == 0) && ( j % 2 == 0) || (i % 2 == 1) && (j % 2 == 1)) && (a[i][j] == 'F'))

cnt++;

}

}

백준 알고리즘 - 1085번 직사각형에서 탈출 문제입니다.

(참고 - https://www.acmicpc.net/problem/1085 )

코드 )

#include <stdio.h>

int main() {

int x, y, w, h, i, min;

int arr[4];

scanf("%d %d %d %d", &x, &y, &w, &h);

arr[0] = x;

arr[1] = w-x;

arr[2] = y;

arr[3] = h-y;

for(i=0; i<3; i++) {

if(arr[i] <= arr[i+1]) {

min = arr[i];

arr[i+1] = min;

}

else

min = arr[i+1];

}

printf("%d\n", min);

return 0;

}

- 단순한 문제입니다. 배열 arr에 크기 4를 지정하여 인덱스 0~3까지 (0,0)으로부터 상대적으로 떨어진 위치의 x와 y좌표, (오른쪽위 꼭지점-x, y) 각각의 값을 넣어줍니다.

즉 직사각형의 경계선까지의 최소 거리를 구하는 문제이므로 이 4가지의 값들 중 최소값만 구해주면 되는 것입니다.

직사각형이라는 도형에 대해 생각해보게 되는 문제로, 대각선의 경우에는 무조건 직선거리에 비해 최소값이 나올 수 없는 도형이기 때문에 대각선은 생각해 볼 필요도 없는 문제입니다.

그 후, 배열값을 비교해가며 최소값 min을 추출해주면 됩니다.

백준 알고리즘 1057번 토너먼트 문제입니다.

(참고 - https://www.acmicpc.net/problem/1057 )

코드)

#include <stdio.h>

int main() {

int n, J, H, temp, cnt=0;

scanf("%d %d %d", &n, &J, &H);

if(J>H) { //항상 H가 J보다 크다고 가정!

temp = J;

J = H;

H = temp;

}

for(; n>0; n/2) {

cnt++;

if(((H-J) == 1) && ((((H+1)/2) - ((J+1)/2)) == 0))

break;

J = (J+1) / 2;

H = (H+1) / 2;

}

printf("%d\n", cnt);

return 0;

}

- J와 H변수는 각각 지민과 한수 라고 표현하겠습니다. 위 문제는 어떠한 '규칙'을 찾아내야 하는 문제입니다. 또한 문제를 간편화 하기 위해 H가 J보다 항상 크다는 가정을 if문을 통해 정리해주었습니다.

이제 H는 J보다 항상 큰 상태가 되며, for문안에서 규칙을 통해 언제 만날 수 있는지를 구해내야 합니다.

J와 H가 만나는 경우는, 

(J와 H의 위치가 1차이가 나고) + 

(J의 위치를 절반으로 나눈 값(현재보다 바로 한 단계 상위 위치)과 H의 위치를 절반으로 나눈 값(현재보다 바로 한 단계 상위 위치)이 같을 때)

이 두가지 조건이 맞은 경우 지민과 한수가 만났다고 가정 할 수 있습니다.

하나라도 조건이 맞지 않을 경우에는 아직 만나지 않은 상태라고 가정하여 계속 J와 H를 반으로 나누어주며 조건이 성립할 때까지 cnt(카운트)를 더해주면 됩니다.

J와 H에 각각 (J+1), (H+1)을 해준 이유는 J나 H가 홀수일 경우를 염두에 둔 것입니다.

이렇게 하여 cnt를 최종출력해주면 몇 번만에 만나게 되었는 지 알 수 있게 됩니다.

위 문제는 규칙을 찾지못하면 풀기 힘든 문제라고 생각됩니다.

+Java)

import java.util.Scanner;

public class algo1057 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int[] arr = new int[3];

for(int i=0; i<3; i++) {

arr[i] = sc.nextInt();

}

if(arr[1] >= arr[2]) {

int min;

min = arr[1];

arr[1] = arr[2];

arr[2] = min;

}

int cnt=0;

for(; arr[0]>0; arr[0] = arr[0]/2) {

cnt++;

if(((arr[2]- arr[1]) == 1) && (((arr[2]+1)/2 - (arr[1]+1)/2)) == 0)

break;

arr[1] = (arr[1]+1)/2;

arr[2] = (arr[2]+1)/2;

}

System.out.println(cnt);

sc.close();

}

}

아, 더하여. 추가적으로 보여드리고 싶은 점이 있어서 사진 하나 첨부하도록 하겠습니다.

물론, 자바코드를 급하게 작성하며 배열을 사용하였고, 라이브러리도 사용하였음은 참고로 알아두시기 바랍니다.

백준 알고리즘 1037번 약수 문제입니다.

(참고 - https://www.acmicpc.net/problem/1037 )

코드 )

#include <stdio.h>

#include <stdlib.h>

int main() {

int cnt, i, j, result;

int *num = (int *)malloc(sizeof(int) * 50);

int *temp = (int *)malloc(sizeof(int) * 50);

scanf("%d", &cnt);

for(i = 0; i < cnt; i++) {

scanf("%d", &num[i]);

}

if(cnt == 1)

result = num[0]*num[0];

else {

for(i = 0; i < cnt; i++) {

for(j = 0; j < cnt-1; j++) {

if(num[j] < num[j+1]) {

temp[j] = num[j];

num[j] = num[j+1];

num[j+1] = temp[j];

}

}

}

result = num[0] * num[cnt-1];

}

printf("%d\n", result);

return 0;

}

- 이번에는 기본 stdio.h 외에 stdlib.h 를 추가해 사용해보았습니다.

int형 포인터를 사용하여 malloc을 이용해 메모리할당을 해줍니다. 

변수 cnt는 약수의 갯수이며, 약수의 갯수만큼 num배열에는 진짜 약수의 값을 입력받아 저장해줍니다.

만약 원래의 어떤 수 N의 약수의 갯수가 1개라면, N은 '그 약수의 제곱인 수' 라고 할 수 있습니다. 따라서 num에 입력받은 약수의 값을 제곱하여 N을 구해줍니다.

만약 약수의 갯수가 2이상이라면, 입력받은 num 배열의 값들을 전부 정렬해 준 뒤,

0번째의 값(약수의 가장 최소 값) 과 cnt-1번째의 값(약수의 가장 최대 값) 을 곱해주면 N의 값을 구해 줄 수 있습니다.

해당 문제는 약수란 무엇이고, 어떻게 구해야 하는 지가 포인트라고 할 수 있습니다.

따라서 약수중 최소값과 최대값을 곱해 준 값이 원래의 수 라는 것만 발견해낸다면 문제는 푼것이나 다름없다고 할 수 있습니다. 

정렬하는 과정은 프로그래머의 방법에 따라 다양할 수 있겠죠.

+Java)

import java.util.Arrays;

import java.util.Scanner;

public class algo1037 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int loop = sc.nextInt();

int[] arr = new int[loop];

for(int i=0; i<loop; i++) {

arr[i] = sc.nextInt();

}

if(loop == 1) {

System.out.println(arr[0] * arr[0]);

}

else {

Arrays.sort(arr);

int s = arr[0] * arr[loop-1];

System.out.println(s);

}

sc.close();

}

}

백준 알고리즘 1026번 보물문제 입니다.

(참고 - https://www.acmicpc.net/problem/1026 )

코드)

#include <stdio.h>

int main() {

int i, j, testcase, temp, S=0;

int arr_A[101];

int arr_B[101];

scanf("%d", &testcase);

for(i=0; i<testcase; i++) {

scanf("%d", &arr_A[i]);

}

for(i=0; i<testcase; i++) {

scanf("%d", &arr_B[i]);

}

for(i=0; i<testcase; i++) {

for(j=0; j<i; j++) {

if(arr_A[j] < arr_A[i]) {

temp = arr_A[i];

arr_A[i] = arr_A[j];

arr_A[j] = temp;

}

}

}

for(i=0; i<testcase; i++) {

for(j=0; j<i; j++) {

if(arr_B[j] > arr_B[i]) {

temp = arr_B[i];

arr_B[i] = arr_B[j];

arr_B[j] = temp;

}

}

}

for(i=0; i<testcase; i++)

S += arr_A[i] * arr_B[i];

printf("%d\n", S);

return 0;

}

- 먼저 말씀드리면, 해당 문제에서 함정이 하나 있습니다. 

바로   단, B에 있는 수는 재배열하면 안된다. 라는 글귀입니다.

물론 재배열 하지 않고 쉽게 할 수있는 방법을 빠르게 찾을 수 있다면, 그 방법이 가장 좋을 것같습니다..^^

다만 제 생각은 결론적으로 S의 값을 가장 작게 만들어 주기 위하여 A배열과 B배열의 값을 곱해주게 될 때, 

A배열의 값이 변함에 따라서 B배열 또한 결과적으로 변하게 됩니다.

따라서 A배열과 B배열을 먼저 재배열하여 곱해주어 S의 최솟값을 구해도 상관이 없다는 점입니다.

(* S의 최솟값을 구하기 위해서는 'A배열의 가장 큰 수 * B배열의 가장 작은 수' 를 해주어야하고, 따라서 A배열의 인덱스가 낮은 순으로 큰 값으로 정렬을 하거나, 작은 값으로 정렬하게 되면, B배열은 A배열에 대해 반대로 정렬 해주어야 한다는 뜻입니다.)

즉, arr_A, arr_B 배열을 생성하여 값을 입력받게 한 뒤, 단순 버블소트(bubble sort)를 이용하여 A와 B 둘 다 정렬을 해줍니다. (저는 단순히 버블소트를 사용하였지만 다른 효율적인 정렬 알고리즘을 사용하시는 것이 좋습니다..라고 생각합니다.)

그 후 정렬된 A,B 배열을 이용하여 S 값을 구해주면 최소 S를 구할 수 있습니다.

+Java)

import java.util.Arrays;

import java.util.Scanner;

public class algo1026 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int loop = sc.nextInt();

int[] arrA = new int[loop];

int[] arrB = new int[loop];

int[] tmp = new int[loop];

for(int i=0; i<loop; i++)

arrA[i] = sc.nextInt();

for(int i=0; i<loop; i++)

arrB[i] = sc.nextInt();

Arrays.sort(arrA);

Arrays.sort(arrB);

int j=0;

for(int i=arrB.length-1; i>=0; i--)

tmp[j++] = arrB[i];

int minresult=0;

for(int i=0; i<loop; i++)

minresult += arrA[i] * tmp[i];

System.out.println(minresult);

sc.close();

}

}

백준 알고리즘 1015번 수열 정렬 문제입니다.

(참고 - https://www.acmicpc.net/problem/1015 )

코드 ) 

#include <stdio.h>

int main() {

int i, j, testcase;

int arr[50];

int tmp[50] = {0, };

scanf("%d", &testcase);

for (i = 0; i<testcase; i++) {

scanf("%d", &arr[i]);

for (j = 0; j<i; j++) {

if (arr[j] > arr[i]) {

tmp[j]++;

}

else if (arr[j] <= arr[i]) {

tmp[i]++;

}

}

}

for (i = 0; i<testcase; i++) {

printf("%d ", tmp[i]);

}

return 0;

}

- 문제는 복잡해보이지만, 간단하게 생각해볼 수 있습니다.

앞으론 testcase에 대한 설명은 생략하도록 하겠습니다.

먼저 배열 arr를 선언해준 뒤, 값을 입력받아 저장합니다.

이후 if문을 이용하여 arr의 값을 비교 해 줄 때, 

0으로 초기화 시켜 준 tmp라는 배열을 하나 생성해주어

해당 i번째 수행 시에 tmp의 값을 1씩 증가시켜주는 로직을 이용하여 구현하였습니다.

이중 for문에서 안의 for문에서는 j=0부터 j<i까지, 

즉 i번만큼 해당 i번째 수행 시 입력받은 arr[i]의 값과, 

이미 저장되어있는 arr[j] (이때, j는 0~i-1까지)의 값을 비교하여 

tmp의 값을 변하게 합니다.

+java)

public class algo1015 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int loop = sc.nextInt();

int[] arr = new int[50];

int[] rst = new int[50];

for(int i=0; i<loop; i++) {

arr[i] = sc.nextInt();

for(int j=0; j<i; j++) {

if(arr[j] > arr[i])

rst[j]++;

else

rst[i]++;

}

}

for(int i=0; i<loop; i++) {

System.out.println(rst[i]);

}

}

}

백준 알고리즘 - 1009번 분산처리 문제입니다. 

(참고 : https://www.acmicpc.net/problem/1009 )

코드 ) 

#include <stdio.h>

int main() {

int arr[10000];

int i, j, testcase, data, jegop, sum;

scanf("%d", &testcase);

for(i=0; i<testcase; i++) {

sum = 1;

scanf("%d %d", &data, &jegop);

for(j=0; j<jegop; j++) {

sum = (sum * data) % 10;

if(sum == 0)

arr[i] = 10;

else

arr[i] = sum;

}

}

for(i=0; i<testcase; i++) {

printf("%d\n", arr[i]);

}

return 0;

}

- 먼저, testcase를 입력받아 총 몇 회 실행할 것인지 입력받도록 합니다.

그 후, data와 제곱수(jegop)을 입력받아, sum에 data를 곱한 후, 10으로 나눈 나머지를 구하게 되면 항상 1의자리만 남게 됩니다. 

이 과정을 jegop번만큼 곱해주므로 for문 안에서 jegop만큼 수행하게 됩니다.

이렇게 반복 수행하여 나온 값(sum)이 0이라면 배열(arr)의 해당 번지에 10을 저장해주고, sum이 0이 아닌 다른 수라면 그 수를 배열의 해당 번지에 저장해주면 됩니다.

testcase만큼 입력을 받고 나서 arr에 분산처리된 값들이 저장 되면,

마지막으로 for문을 한번 더 testcase만큼 수행하여 arr에 저장 된 값들을 출력해주면 됩니다.

해당 문제에서 testcase에 대한 조건이 없었으므로 배열은 그냥 임의의 큰 수인 10000으로 잡았지만, 만약 testcase의 조건이 있었다면 배열의 크기를 testcase에 맞게 조정해주는 것이 좋겠죠.?

백준 알고리즘 1008번 문제입니다 (참고 - https://www.acmicpc.net/problem/1008 )

C 코드 ) 

#include <stdio.h>

int main() {

double A,B;

scanf("%lf %lf", &A, &B);

printf("%.9lf\n", A/B);

return 0;

}

아주 간단하다고 생각할 수 있지만, 의외로 중요한 문제라고 할 수 있습니다.

(오답)

#include <stdio.h>

int main() {

double A,B;

scanf("%f %f", &A, &B);

printf("%.9f\n", A/B);

return 0;

}

위 차이는, scanf에서의 포맷문자가 f인지 lf인지의 차이입니다.

포맷문자가 f이고 파라미터의 크기가 4이면 float로 처리하고, 

파라미터의 크기가 8이면 double로 처리하게 됩니다.

scanf는 입력을 받아야하므로 모든 파라미터를 포인터로 받게 되는데,

포인터는 주소값 4Byte만 전달될 뿐 해당 포인터가 가리키는 자료형이 무엇인가는 전달되지 않습니다.

즉, scanf가 전달받는 포인터는 void타입 포인터로 보면 됩니다.

그러므로 float과 double을 f와 lf로 구분해주어야 하는데, 문제에서는 소수점 9자리 이상 출력이었으므로 double을 사용해야 하는 문제입니다.

따라서 f로 하면 해당 문제에서 오답으로 판정되고, lf로 해주어야 올바른 답으로 향할 수 있다고 볼 수 있습니다.

더하여, 사용자가 만든 함수도 파라미터 전달 시 타입정보는 전달되지 않습니다.

받을 수 있는 타입이 처음부터 고정되어 있을 뿐이고, scanf처럼 타입이 가변형인 경우는 타입정보를 명시해 주는 수단으로써 포맷정보를 이용하게 되는 것입니다.

++)Java

public class algo1008 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println((double)sc.nextInt() / sc.nextInt());

}

}