백준 알고리즘 - 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();

}

}

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

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

프로그래머의 가장 기초적인 언어 중 하나인 C에 대해 설명하려 합니다.

C는 대학에서 IT관련 학과라면, 더하여 주위에서는 전자공학과 학생들도 기초적으로 배우는 과목이더군요.

먼저 프로그래밍 언어에 대해 소개하고 넘어가도록 하겠습니다.

프로그래밍 언어란 주어진 어떤 문제를 해결하기 위해 사람과 컴퓨터 사이에서 의사소통을 가능하게 하는 인공적인 언어입니다. 이 언어를 통해 사용자는 컴퓨터에게 일련의 일을 시키는 명령어들의 집합체인 '프로그램' 을 작성할 수 있습니다.

수 많은 프로그램 언어 중 공통적으로 프로그램 언어에 대해 살펴보겠습니다.

1. 간결성 - 사람이 프로그램을 쉽게 이해하고 읽을 수 있도록 간결하게 표현할 수 있다.

2. 직교성 - 언어의 각 구성요소가 상호 독립적이면서도 어떤 환경에서도 그 구성요소가 같은 의미로 사용된다.

3. 가독성 - 사람이 이해하기 쉽도록 작성된 프로그램이나 프로그래밍 언어의 문법, 주석등이 가독성의 향상에 도움이 된다.

라는 등등의 프로그래밍 언어의 특징이 있습니다.

먼저, C언어의 특성에 대해 살펴보겠습니다.

1. 이식성이 뛰어나다. - C언어는 다른 프로그램 언어보다 높은 호환성을 가지고 있으며 C언어의 표준함수만 작성 된 프로그램은 어떤 기종의 컴퓨터에서도 정상적으로 컴파일 되고 실행될 수 있습니다. 예를 들어 데스크탑 컴퓨터에서 작성된 프로그램이 대형 컴퓨터에서도 완벽히 사용 될 수 있다는 것입니다.

2. 다양성을 가진다. - C언어는 계산용 프로그램 뿐만이 아니라 GUI(Graphic User Interface), 시스템 프로그램(System Program), 응용 프로그램(Application Program)등과 같이 컴퓨터의 모든 분야에서 사용할 수 있도록 설계된 효율적인 프로그램 언어입니다.

3. 유연성이 좋다. - C언어의 가장 큰 특징 중 하나는 새로운 프로그램을 개발하기 위해 이미 작성된 프로그램 모듈들을 그대로 사용할 수 있다는 것입니다. 대표적인 응용 소프트웨어로 오토캐드, 윈도우, 폭스프로 등이 있다고 합니다.

4. 혼합성을 가진다. - C언어는 다른 프로그램 언어와 함께 혼합되어 사용될 수 있으며, 혼합 프로그램을 개발하는 프로그램의 혼합성을 극대화시키는 데에 사용될 수 있습니다. 

5. 절차지향적 특징을 가진다. - 기본적으로 많은 사람들이 인지하고 있는 C언어와 다른 언어의 차이점이라 할 수 있겠습니다. Java, C++ 등은 객체지향적인 특징을 가집니다. 객체지향에 관련 된 부분은 블로그 내 Java 카테고리에서 자세히 설명드리겠습니다. 절차지향적 프로그래밍이란 정해진 순서대로 프로그래밍을 하는 방식을 의미합니다. 따라서 C언어를 학습하는 데 오랜 시간이 걸리지 않는다는 장점이 있습니다.

위에서 C언어의 특징 및 장점에 대해 이야기 하였다면, 단점 또한 존재합니다.

1. 다른 학습자가 프로그램의 내용을 이해하기 어려운 표현이 될 수도 있습니다.

2. 완전한 고급언어에 비해서 상대적으로 LOW level(표현이 맞는지 모르겠습니다.^^) 을 이해해야 하므로 배우기가 쉽지 않습니다.

3. 자료형의 검사기능이 미약합니다.

4. 혼합적으로 연산하는 경우 연산 우선순위에 따라 자동적으로 계산되므로 연산 우선순위를 모르면 잘못된 계산 결과를 얻을 수 있습니다.

5. 배열에서 첨자의 범위를 검사하는 기능이 미약합니다.

6. 프로그램을 모듈화하지 않으면 이해하기 어려운 프로그램이 되는 경우가 많습니다.

이러한 C언어의 특징들은 보는 관점에 따라 다르게 가치가 판단될 수 있다고 생각합니다. 특히 C언어는 소프트웨어 측면이나 하드웨어의 개발 도구로써 다양하게 사용 될 수 있는 언어의 특징을 가지고 있으므로 널리 사용되는 언어라 할 수 있겠습니다.

이상으로 C언어의 특징을 마무리 하겠습니다.

해당 정보들은 '불량너구리'님의 블로그

http://blog.naver.com/PostView.nhn?blogId=ashly77&logNo=120125897912

를 다수 참고하여 정리하였습니다.

백준 알고리즘 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());

}

}