mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-05-21 20:13:45

사전식 배열


이 문서는 토막글입니다.

토막글 규정을 유의하시기 바랍니다.


1. 개요2. 예시

1. 개요

배열 규칙의 한 종류이다.

예를 들어 A, B, C, D의 순서로 사전식 배열을 하게되면, 배열의 첫 번째 순서가 알파벳 A가 되고 그 다음 BCD 순이 된다. 처음 알파벳 A가 나오고 BCD를 배열하고 끝나면 다음 B가 첫번째로 놓이고 ACD가 배열된다. 이런 식으로 배열되면 CDAB는 17번째 배열이라는 것을 알 수 있는데 첫 문자에 A가 오는 게 6가지, B가 오는 게 6가지, C가 첫 번째 오고 다음 A가 오면 남은 BD 배열하는 방법 2가지, CB 오고 남은 AD 배열하는 방법 2가지, 그 다음이 CDAB 문자열이 나온다. 이런 식의 사전식 배열은 배열 자체가 어떤 정보가 될 때 그 정보를 빠르게 처리하기 위해(수학 문제를 풀기 위해) 만들어진 배열이며 규칙을 통해 어떤 배열이 몇 번째 배열이 되는지 쉽게 파악할 수 있는 장점이 있다.

실생활의 예시로는 올림픽 순위 집계 방식을 들 수도 있다. 금메달 2개, 은메달 2개, 동메달 2개의 성적을 거둔 A국가와 금메달 1개, 은메달 10개, 동메달 50개의 성적을 거둔 B국가가 있다고 가정해보자. 이때, 금메달 -> 은메달 -> 동메달의 순서로 사전식 배열하는 경우, A국가가 B국가보다 더 높은 순위에 위치하게 된다. 전체 메달 갯수는 B국가가 더 많지만, 첫 번째 배열기준인 금메달 개수가 A국이 더 많기 때문이다. 가장 먼저 금메달의 갯수가 더 많은 국가가 더 높은 순위에 위치하고, 금메달 갯수가 동일하다면 은메달의 갯수가 더 많은 국가가 더 높은 순위에 위치하고, 금메달과 은메달의 갯수가 동일하면 동메달의 갯수가 더 많은 국가가 더 높은 순위에 위치하는 식이다.

2. 예시

A, B, C, D를 A -> B -> C -> D의 순서로 사전식 배열하게되면 다음과 같다.

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

분류