본문 바로가기

배열2

배열 행 우선 순위, 열 우선 순위 2차원 배열에 어떠한 값들을 저장하는 방법은 두 가지가 있습니다. 두 가지 방법으로 저장한 배열은 각각 '행 우선 배열'과 '열 우선 배열'이라고 부릅니다. 하나씩 알아보도록 하겠습니다. 행 우선 배열(row major ordering) 먼저 행우선 배열입니다. 이름 그대로 행을 우선시해서 저장하는 배열을 뜻합니다. 위의 그림에서 각 행들에 속하는 요소들을 빨간색 네모로 묶어보았는데 저 빨간색 네모를 먼저 채우고 다음 네모를 채운다고 생각하시면 됩니다. 즉, 1행을 다 채우고 2행을 채우는 식으로 배열을 채워나갑니다. 그런 식으로 배열을 채워나가면 저장되는 요소들의 순서는 위의 그림과 같습니다. 이제 요소들의 주소를 알아보겠습니다. 일단 axb 배열의 (i,j)의 주소를 구하는 공식은 '시작 주소 + (.. 2022. 3. 9.
[algospot][JOSEPHUS] 조세푸스 문제 문제 : https://algospot.com/judge/problem/read/JOSEPHUS N = 6, K = 3 을 예로 들어보자. 병사 리스트 삭제되는 인덱스 (0부터 시작) 삭제되는 병사 번호 (1부터 시작) 1 2 3 4 5 6 0 1 2 3 4 5 6 2 4 2 3 5 6 0 2 3 5 6 2 6 최종 결과는 위와 같다. 리스트에 병사들 번호를 차례대로 저장한뒤 배열요소가 2개가 남을 때까지 삭제되는 인덱스를 구해서 하나씩 배열에서 삭제시킨다. 삭제 인덱스는 0부터 시작하며 다음 삭제되는 인덱스는 삭제된 인덱스 + K -1 이다. +K는 시계 방향으로 K 번째인 사람이 다음 삭제되는 인덱스이기 때문에 더해주었다. -1은 현재 리스트에서 한 병사가 삭제되었기 때문에 이(삭제된 병사 인덱스 1.. 2020. 1. 28.