초보와 고수사이 넘사벽 중간쯤

이번 편은 TIP이 생각나서 써봅니다.

2차원 평면에 사각형을 여러개를 그렸을 때 (중첩될 수 도 있음)

(입력 데이터로 사각형의 양 대각선 좌표를 주어짐)

1. 사각형이 표시하는 면적은 얼마인가?

2. 사각형이 1번만 겹치는 부분의 면적은 얼마인가?

3. 사각형이 겹치지지 않는 부분의 면적은 얼마인가?

이런 종류의 문제를 푸는 방법으로 플레인 스위핑이라는 유명한 방법이 있습니다.

http://blog.naver.com/PostView.nhn?blogId=choyi0521&logNo=220020192420

하지만 유명한 방법을 모두 알 수 없기도 하고

사각형이 표시하는 면적이 적고 사각형의 갯수가 적다면 아주 쉽게 푸는 방법이 있습니다.

최대 범위만큼 메모리를 잡고 각 사각형 마다 안에 면적안에 1을 추가합니다.

그럼 겹쳐지지 않는 부분은 1만 써있게 되고

2번 겹쳐지는 부분은 2, 3번 겹쳐지는 부분은 3이 됩니다.

위의 1번 문제는 모든 숫자의 갯수를 세면 되고

2번 문제는 2의 갯수를 세면 되고

3번 문제는 1의 갯수만 세면 됩니다.

간단한 것인데 쉽게 생각나면 쉽게 풀고 아니면 어렵게 풀어야 하는 문제입니다.

하지만 사각형이 무지 크면 사각형에 1을 써넣는 작업이 너무 많아서 TimeOut이 되는

방법입니다. 초급/입문으로만 쓰세요.

#삼성_소프트웨어_역량_테스트

많은 문제가 "전처리" + "모든 경우 탐색" + "조건확인" 이런 식으로 되었다고 말씀을 드렸는데

"전처리"에 해당하기도 하고 가벼운 퀴즈/퍼즐에도 사용되는 것이 있습니다.

예를 들어 특정 변화를 보여주고 일정 시간 후에 변화된 상태를 묻는 경우가 있습니다.

이 일정 시간이 100처럼 for문을 돌려서 해볼만한 것도 있고 1000000000 처럼 무지 큰값을 주는 경우도 있는데

이런 경우는 for문을 돌리지 말라는 뜻이겠죠?

1. NxN 배열의 1초일때 (1, 1)에 있을때 계속 해서 대각선 아래로 이동한다고 하고 경계를 넘으면 다음 줄로 이동 할때

    1초 1,1

    2초 2,1

    3초 1,2

    4초 3,1

    5초 2,2

    6초 1,3

    ......

          n,n

          1,1

    그림이면 쉬운데 글로는 어렵네요.

    10000000000초 후에 위치는?

힌트는 NxN 초 후에는 다시 돌아오니 10000000000%(NxN) 만 따지면 됩니다.

이것도 대각선이니 조금 처리가 필요합니다.

아마 이동이 대각선이 아니라 수평이나 수직 방향이었으면 좀 더 쉽게 생각을 할 수 도 있었을거에요.

이런 종류가 나온 책이 번역본은 없던데 아마존에서 algorithm quiz나 Algorithm puzzle을 찾아보면

기본적인 형태의 문제가 많이 있습니다. 

보통 문제가 여기서 끝나지 않고 이것은 전처리이고 그 후 다른 문제가 겹쳐지는 경우도 많이 있습니다.

#삼성_소프트웨어_역량_테스트

전쟁을 하러 가면서 총을 안가져 가는 격이지만

혹시 시험을 보러 갔는데 완전탐색을 풀 수 있는 문제가 나왔고

코드가 기억나지 않더라도 끝까지 물고 늘어져야 합니다.

많은 문제가 ~하는 경우는 몇 가지인가? 라고 묻기도 하지만

~하는 최대 값은 얼마인가? 라고 묻는 경우가 많이 있습니다.

(실제도 경우의 수보다 최대/최소값이 더 중요합니다.

  ~과제를 하는데 최소 얼마가 필요합니다. 라고 해야지

  "몇가지 방법이 있는데요.""라고 하면

  "이런.. 그래서 어떤 것이 최소냐고?" 라고 하겠죠.)

이럴때 순열/조합/중복순열/중복조합을 꼭 확인하고 풀어야 하는 경우도

있지만 중복순열로 풀면 되는 경우가 많이 있습니다.

왜냐하면 중복순열이 나머지를 다 포함하기 때문이죠.

그리고 모두 몇개를 고르는 것이 모르면 어려운데

(for문을 몇번 쓰는지 모르기 때문에)

예를 들어 항상 8개를 고른다고 하면 8중 for 문을 쓰면 됩니다.

for (a1=1;a1<=8;a1++)

  for (a2=1;a2<=8;a2++)

    ......

재귀 이런것 몰라도 이렇게 8중 for문 쓰면 그게 8개를 뽑는 중복순열입니다.

어차피 온라인저지는 코드를 보지 않기 때문에 답만 맞으면 되지

어떤 함수를 썼는지는 중요하지 않고 창피한 것 이런거 없습니다.

조합으로 풀 수 있는 것을 중복순열로 풀면 몇배의 실행시간이 더 걸리겠지만

답이 같은 경우가 많이 있습니다.

(아닌 것도 분명 있습니다.그러니 꼭 도구(외운 기본 코드)를 가지고 시험장에 가야죠.)

그리고 조합의 경우는 "바이너리 카운팅"이라는 방법으로 쉽게? 구할 수 있습니다.

재귀 같은 것 없습니다. 

(재귀를 이해 못하시겠으면 이렇게라도 하시면됩니다.)

비트연산을 이용하는 것인데 코드도 있고 하니 아래를 참고하세요.

http://dumpsys.blogspot.kr/2015/03/algorithm-binary-counting-power-set.html

많은 경우가 완전 탐색 문제이니 모든 경우의 수를 찾는,

즉, 순열/조합/중복순열/중복조합/(복합) 중 어떤 것인지를 빨리 알아내는 것이 중요합니다.