티바이트

십진수 11을 이진수로 바꾸려면 

십진수 m을 n진법으로 나타내는 과정도 이와 같다.

ⓛ m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b1를 얻는다.

② m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b2를 얻는다.

...

...

이같은 과정을 m이 0보다 작아질 때까지 반복하고,

얻은 b수열을 뒤집으면 n진법 표현을 얻을 수 있다.

아래는 C++로 구현한 코드이다. (예외처리는 하지 않음)

C++의 string를 사용하는 대신, 배열의 뒤쪽에서부터 값을 채워나가면

뒤집는 동작을 하는 코드를 사용하지 않아도 된다.

대신 출력할 때 시작 위치 주소를 맞게 설정해야 한다.

g++ 컴파일러에서 (C++언어)

아래와 같은 헤더를 인클루드하여 사용할 수 있다.

#include <bits/stdc++.h>

해당 헤더파일을 확인해 보면(링크),

cstdio, cstdlib, cmath 등 C언어 표준헤더들과

stack, queue, vector 등과 같은 STL관련 헤더들을 포함하고 있는 것을 볼 수 있다.

프로그래밍 대회 등에서 이 헤더를 사용하여 코딩시간을 단축할 수 있다.

C언어 표준헤더가 아니므로 Visual Studio에서는 사용할 수 없다.

ex)

#include <bits/stdc++.h>

int main()

{

    std::stack<int> s;

    std::queue<int> q;

    std::vector<int> v;

    printf("abc\n");

    printf("%d\n", (int)sqrt(100));

    return 0;

}

링크 : http://codeforces.com/contest/723

A : The New Year: Meeting Friends

 세 사람이 있는 수직선 위의 세 지점이 주어지고, 모두의 이동거리의 합이 최소가 되는 약속지점을 찾는 문제이다. 교내대회에서 유사한 문제를 풀어본 적이 있어서 금방 해결할 수 있었다. 위치를 정렬했을 때 중간값이 되는 지점을 찾아야 하는데,  입력이 항상 3개라 조건문으로도 찾을 수 있겠지만 코드를 빨리 작성하려고 std::sort()를 사용하여 해결했다.

B : Text Document Analysis

 주어지는 문자열에서 괄호 밖에 있는 단어 중 가장 긴 단어와, 괄호 안에 있는 단어의 개수를 구하는 문제. 

괄호 안에 있는 단어 수를 셀 때, 언더스코어 또는 여는 소괄호 다음에 나오는 단어를 카운팅하는 것으로 간단하게 짤 수 있었다.

C : Polycarp at the Radio

 문제를 이해하지 못해서 시간만 소비하고 포기...

D : Lakes in Berland

 물과 육지를 나타내는 2차원 배열이 입력으로 주어지고, 호수의 개수를 주어진 수로 줄일 때 메워야 하는 영역의 최소 수를 구하는 문제이다.

  먼저 호수와 바다를 구분하기 위해 바깥쪽에 있는 물을 따로 표시했다. 최대 입력의 크기인 50x50보다 더 큰 52x52 배열을 만들고 바깥의 물을 BFS하여 바다로 표시했다.

 그리고 안쪽의 물 역시 BFS를 사용하여 영역의 개수를 세고, 각 영역의 크기와 시작점을 구조체로 저장해 두었다. 그리고 영역크기 순으로 소팅하여 작은 것부터 채우는 것으로 코드를 작성하였다.

A, B, D를 풀고 C도 풀어보려다가 시간이 다 되어 E, F번 문제는 못 풀어보았다..

Rank : 640

Rating : 1456 -> 1531 (+75)

격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때

다음과 같은 식을 사용할 수 있다.

d가 0보다 크면 원 외부, d가 0보다 작으면 원 내부로 판단하는 것이다.

그러나 원을 그릴 때는 범위 내의 모든 점에 대입해야 할 뿐만 아니라 

매번 곱셈 연산을 3번 사용하여야 한다.

midpoint algorithm을 사용하면 이를 효율적으로 해결할 수 있다.

(원의 반지름이 n일 때 O(n))

원리

[그림1]

이 알고리즘의 원리는 결정된 한 점이 있을 때

한 칸 옆인 에 대응되는 y 값이 인지 인지 판단하는 것이다.  (위 그림에서 까만색 점 2개)

[그림 1]과 같이 원에 포함되는 것으로 결정된 한 점

가 있을 때 가 원의 내부인지 외부인지 판별하는 식은 아래와 같이 나타낼 수 있다.

중간점이 원 내부에 포함될 경우(p<=0), [그림1]에서 p의 위쪽 점을 선택하고,

p점이 원 밖일 경우(p>0) p의 아래쪽 점을 선택하는 것이다.

같은 방법으로 을 다음과 같이 점화식으로 나타낼 수 있다.

이제 을 결정해야 하는데,

위에서 서술한 바와 같이 의 부호에 따라 선택되므로 다음과 같이 나타낸다.

이를 활용하여 의 식을 간단히 하면

코드를 좀더 간편하게 하기 위해 대신 를 활용하면

최종적으로 아래 식을 얻을 수 있다.

한편 p의 초기값 는 위에서 식에 x의 초기값 0과 y의 초기값 r을 대입하여

5/4 - r이라는 것을 알 수 있다.

그런데 p의 점화식을 보면 초기값 외에는 모두 정수의 덧셈/뺄셈 연산이므로 (2x는 x+x로 계산)

p0을 int형으로 하고 1-r로 두어도 무방하다.

위 과정을 x > y가 되기 전까지 반복한다.

[그림 2]

실제로 그려보면 아래 그림과 같은 8분원(octant)을 얻을 수 있다.

[그림 3]

그리고 아래와 같이 대칭인 8개 점을 동시에 그리면 전체 원이 그려진다.

(x, y)

(x, -y)

(-x, y)

(-x, -y)

(y, x)

(y, -x)

(-y, x)

(-y, -x)

[그림 4]

4방향으로 뚫려 있는 부분은 따로 채워준다. 

[그림 5]

8개 부분을 따로 표시해 보면 아래 그림과 같다.

[그림 6]

원 채우기

y값이 변할 때 해당 y좌표에 해당하는 부분을 모두 칠하면

가운데 정사각형 영역을 제외한 부분을 채울 수 있다.(하단 코드 참조)

[그림 7]

나머지 정사각형 부분은 쉽게 채울 수 있다.(하단 코드 참조)

[그림 8]

모두 단색으로 칠해보면 아래 그림과 같은 원이 나온다.

[그림 9]

콘솔창에서는 한계가 있어 Javascript를 사용하여 그린 큰 원.

[그림 10]

구현

[그림 9]를 그릴 때 작성한 C언어 코드이다.

gcc컴파일러로 컴파일 가능하다.

나머지 코드들은

https://github.com/tibyte/algorithms/tree/master/bresenham/midpoint_circle

에서 다운로드 가능.

프리프로세서인 #include에 대한 간단한 실험을 해 보았다.

코드 중간에서 소스코드가 있는 txt파일을 로드해도 전처리 과정에서 include가 처리되기 때문에 정상적으로 컴파일된다.

main.c

#include <stdio.h>

int main(void)
{
#include "source.txt"   //'hello world!'가 출력된다.
	return 0;
}

source.txt

https://github.com/tibyte/practice/tree/master/C/include

두 직사각형이 평면상에 놓여져 있을 때 아래와 같이 7가지로 나누어 생각해 볼 수 있다.

회색 사각형을 기준으로

1. 한쪽 귀퉁이를 덮음

2. 한 변을 덮음

3. 자신의 한 변이 모두 덮임

4. 교차

5. 자신이 포함됨

6. 다른 사각형을 모두 덮음

7. 겹치지 않음

각각의 경우를 나누어 처리할 수도 있으나

1~6의 겹치는 영역(직사각형)을 보면 모두 공통적인 특징이 있다.

겹치는 영역(Intersection)의

왼쪽 변은, 기존 두 사각형의 왼쪽 변 중에서 더 오른쪽에 있는 것

오른쪽 변은, 기존 두 사각형의 오른쪽 변 중에서 더 왼쪽에 있는 것

위쪽 변은, 기존 두 사각형의 위쪽 변 중에서 더 아래쪽에 있는 것

아래쪽 변은, 기존 두 사각형의 아래쪽 변 중에서 더 위쪽에 있는 것

이 된다는 것을 확인할 수 있다.

화면 좌측상단이 원점인 좌표계를 기준으로  코딩할 때 사각형 구조체를 x, y, width, height로 정의한다면, 겹치는영역의

(왼쪽 변) x는 기존 두 사각형의 x중에서 큰 것
(오른쪽 변) width는 기존 두 사각형의 x+width 중에서 작은 것 - x좌표

(위쪽 변) y는 기존 두 사각형의 y중에서 큰 것

(아래쪽 변) height는 기존 두 사각형의 y+height 중에서 작은 것 - y좌표

으로 하면 된다.

-x, -y 가 붙어있는 이유는 해당 속성이 각각 너비와 높이이기 때문.

아래는 Javascript 코드로 작성해 본 것이다.

코드를 보면 두 사각형이 겹치지 않은 경우를 걸러내는 부분이 추가되었다.

이 문제에 대해 조금 다르게 생각해 볼 수도 있는데,

너비가 w이고 높이가 h인 screen이 있을 때

임의의 점에 대하여

그 점이 screen 안에 있을 때는 그대로 표시하고,

screen 밖에 있을 때는 screen의 안쪽 변 끝에 두는 간단한 식이 있다.

x' = min(w, max(0, x))

y' = min(h, max(0, y))

이 식을 한 사각형의 4 꼭지점(초록색)에 각각 적용한다면,

두 사각형의 겹치는 부분이 만드는 새로운 사각형의 4 꼭지점(파란색)을 얻을 수 있다.

연관글 :

자바스크립트로 구현한 결과는 여기에 올림.

문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007

32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.

하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)

예시 

입력 : -1 2 0 -1 2

출력 : 0

입력 : 2 2 2 2 5

출력 : 5

입력 : 2 2 2 2 2

출력 : 2

(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)

생각 1

integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.

=> 메모리 용량 4GB가 필요하므로 비효율적

생각 2

입력이 들어올 때마다 리스트에 넣는다.

리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.

마지막에 남은 수를 출력한다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)

생각 3

생각2에서 리스트 대신 트리를 사용한다.

시간복잡도 : O(nlogn)

공간복잡도 : O(n)

생각 4

임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.

(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)

문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로

들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.

시간복잡도 : O(n)

공간복잡도 : O(1)

소스코드 (C++)

#include <cstdio>

using namespace std;

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int leng;

scanf("%d",&leng);

int acc = 0;

int num;

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

scanf("%d",&num);

acc ^= num;

}

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

}

return 0;

}