양말의 짝을 찾을수있는 효율적인 알고리즘

 
 
stackoverflow에서 재미난 주제를 발견하였다.
 
주제에 대한 요약은 아래와 같다.

세탁물에서 양말의 짝을 찾는 도중 내가 하는 방식이 그다지 효율적이지 않다는 걸 알게 되었다.

나는 양말을 하나를 고르고 그 짝을 찾기 위해 세탁물 더미에서 반복적으로 찾았다.
이는 평균적으로 n/2 * m/4 = n^2/8의 양말을 반복해야 한다.

나는 컴퓨터 과학자로서 O(N log N)에 달성하기 위해 정렬을 떠올렸다
양말을 복제할 수 없기 때문에 해싱이나 not in-place 정렬 같은 해결책은 사용할 수 없다

따라서 질문은

2n 개의 요소를 포함하는 n개의 양말 더미를 고려할 때(각 양말이 정확히 하나의 일치하는 쌍을 가지고 있다고 가정)
최대 로그 여분의 공간으로 효율적으로 짝을 찾는 가장 좋은 방법은 무엇인가요?

 
질문자는 양말의 짝을 찾기 위해
양말 더미에서 양말을 하나 선택하고
그 양말의 짝을 찾기 위해 양말 더미에서 다른 양말을 계속 뽑아보면서 짝이 나올 때까지 반복하고 있던 것.
 
 

양말 짝 찾는 효율적인 방법을 알려줘!

 

I use pigeon hole principle to pair exactly one from the laundry pile. I have 3 different colors of socks (Red, Blue and Green) and 2 pairs of each color. I pick up 4 number of socks each time and I always make up a pair and get to work.

나는 빨래 더미에서 정확히 하나의 짝을 찾기 위해 비둘기의 집 원리를 사용한다
나는 빨란 색, 파란색, 녹색 3가지 색상의 양말을 각각 2켤레씩 가지고 있다
나는 매번 양말을 4개를 집어 들어 항상 한 짝을 만든다.

 
비둘기의 집 원리는  pigeonhole principle 라 부르며
비둘기다 드나드는 구멍의 원리 -> 비둘기 구멍의 원리 -> 비둘기 집의 원리로 불린다.
n마리보다 더 많은 비둘기가 n 개의 구멍에 들어가야 한다면 적어도 하나의 구멍에는 두 마리 이상이 들어가야 하는 것을 의미한다.
 
즉 빨간 양말 세트, 파란 양말 세트, 녹색 양말 세트에서 양말을 4개를 집으면 반드시 한 개는 짝이 이뤄지는 것.
 
일단 이 방식은 양말의 종류가 늘어 날 날 수록 n+1 개를 집어야 한다. 
 

Pick up a first sock and place it on a table. Now pick another sock; if it matches the first picked, place it on top of the first. If not, place it on the table a small distance from the first. Pick a third sock; if it matches either of the previous two, place it on top of them or else place it a small distance from the third. Repeat until you have picked up all the socks.

첫 번째 양말을 들고 테이블 위에 둔다.
이제 다른 양말을 찾은 후 첫 번째 양말과 일치하면 첫 번째 양말 위에 놓는다
그렇지 않다면 첫 번째에서 조금 떨어진 곳에 놓는다
세 번째 양말을 고르고 이전 두 양말 중 일치한다면 그 위에 놓고, 아니라면 두 번째에서 조금 떨어진 곳에 놓는다
이를 반복한다

 
양말 더미에서 나온 것이 짝이 아닐 때 양말더미에 다시 넣지 않는 것으로 반복 횟수를 줄이는 방식이다.
일반적으로 사용할만함.
 

1. For each color of socks, form a pile. Iterate over all socks in your input basket and distribute them onto the color piles.

2. Iterate over each pile and distribute it by some other metric (e.g. pattern) into the second set of piles

3. Recursively apply this scheme until you have distributed all socks onto very small piles that you can visually process immediately

1. 양말 더미에서 양말 색깔 별로 분류하여 더미를 만드세요
2. 양말의 색 더미에서 다른 기준(예: 패턴)으로 두 번째 더미를 만드세요
3. 모든 양말을 한눈에 파악하기 쉬운 작은 더미가 만들어질 때까지 반복하세요

 
한눈에 양말의 짝을 쉽게 분리가능한 상태까지 양말들을 여러 기준으로 분류를 반복적으로 한 후에 양말짝을 찾는 방식이다.
 
댓글을 보면 이것에 긍정하는 사람도 있지만
가지고 있는 양말이 하나의 색상에 비슷비슷하게 생겨서 분류하기가 힘들다는 사람도 많다.

이때 여러 사람이 함께하면 양말을 더 빨리 맞출 수있는가 라고 생각할 수 있는데 이는 비효율 적이라 한다.

"100명의 사람이 10개의 양말 더미에서 싸우는 것을 상상해 보자. 손 충돌과 인간 통신 등 동기화 비용이 효율성과 속도를 파괴한다." 

 
 

step 1) discard all your existing socks
step 2) go to Walmart and buy them by packets of 10 - n packet of white and m packets of black. No need for other colors in everyday's life.

1단계 기존의 모든 양말을 버려라
2단계 대형마트에 가서 흰 양말 세트랑 검은 양말 세트를 구매하라 일상생활에서 다른 색은 필요 없다

엥?
 

If it's winter, you don't have to wear matching socks. We are programmers. Nobody needs to know, as long as it works.

겨울이라면, 짝이 맞는 양말을 신을 필요가 없습니다. 우리는 프로그래머야. 양말로써 작동하는 한, 아무도 알 필요가 없다.

엥?
 
 
출처
https://stackoverflow.com/questions/14415881/how-can-i-pair-socks-from-a-pile-efficiently