shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
1955년에 레스터 R. 포드 주니어와 D. R. 풀커슨은 최초로 알려진 알고리즘인 포드-풀커슨 알고리즘을 만들었다. 1955년 논문에서 포드와 풀커슨은 해리스와 로스의 문제가 다음과 같이 공식화되었다고 썼다( 5페이지 참조):연결된 두 도시를 여러 중간 도시를 거쳐 연결하는 철도 네트워크를 고려하고, 네트워크의 각 링크에는 그 용량을 나타내는 숫자가 할당된다. 정상 상태 조건을 가정하고, 한 주어진 도시에서 다른 도시로의 최대 흐름을 찾아라.1962년 저서 《네트워크 흐름》에서 포드와 풀커슨은 다음과 같이 썼다:1955년 봄에 T. E. 해리스가 F. S. 로스 장군(퇴역)과 함께 철도 교통 흐름의 단순화된 모델을 공식화하고 이 특정 문제를 모델이 제시하는 핵심 문제로 지목했다 [11].여기서 [11]은 1955년 해리스와 로스의 비밀 보고서 《철도 네트워크 용량 평가 방법의 기본》을 참조한다( 5페이지 참조).
수년에 걸쳐 최대 흐름 문제에 대한 다양한 개선된 솔루션이 발견되었는데, 특히 에드먼즈와 카프, 그리고 독립적으로 디니츠의 최단 증대 경로 알고리즘, 디니츠의 블로킹 흐름 알고리즘, 밀어내기-재표시 알고리즘인 골드버그와 타잔의 알고리즘, 골드버그와 라오의 이진 블로킹 흐름 알고리즘이 있다. 셔먼과 켈너, 리, 오레키아, 시드포드의 알고리즘은 각각 대략적으로 최적의 최대 흐름을 찾지만 무방향 그래프에서만 작동한다.
2013년 제임스 B. 올린은 formula_1 알고리즘을 설명하는 논문을 발표했다.
2022년 리 천, 라스무스 킹, 양 P. 리우, 리처드 펭, 막시밀리안 프로브스트 구텐베르크, 수샨트 사흐데바는 최대 흐름 문제의 특정 사례인 최소 비용 흐름 문제를 위해 formula_2으로 실행되는 거의 선형 시간 알고리즘을 발표했다. 음수 가중치를 갖는 단일 원천 최단 경로 문제의 또 다른 특정 최소 비용 흐름 문제의 경우 거의 선형 시간 알고리즘도 보고되었다. 두 알고리즘 모두 2022년 컴퓨터 과학의 기초 심포지엄에서 최고 논문으로 선정되었다.
먼저 몇 가지 표기법을 설정한다:
정의. 간선의 용량은 간선을 통해 통과할 수 있는 최대 흐름량이다. 형식적으로는 formula_11 함수이다.
정의. 흐름은 다음을 만족하는 formula_12 함수이다:
비고. 흐름은 대칭 왜곡적이다: 모든 formula_13에 대해 formula_17이다.
정의. 흐름의 값은 소스에서 싱크로 통과하는 흐름의 양이다. 형식적으로 formula_18인 흐름에 대해 다음으로 주어진다:
정의. 최대 흐름 문제는 소스에서 싱크로 가능한 한 많은 흐름을 보내는 것이다. 즉, 최대 값을 갖는 흐름 formula_20를 찾는 것이다.
여러 개의 최대 흐름이 존재할 수 있으며, (정수뿐만 아니라) 임의의 실수 (또는 임의의 유리수) 흐름 값이 허용되는 경우, 기본 최대 흐름의 무한한 선형 조합이 있기 때문에 정확히 하나의 최대 흐름이 있거나 무한히 많은 최대 흐름이 있다. 즉, 한 최대 흐름에서 간선 formula_21에 formula_22 단위의 흐름을 보내고 다른 최대 흐름에서 formula_23 단위의 흐름을 보낸다면, 각 formula_24에 대해 formula_21에 formula_26 단위를 보내고 나머지 간선에 흐름을 적절히 라우팅하여 다른 최대 흐름을 얻을 수 있다. 흐름 값이 임의의 실수 또는 유리수일 수 있다면, 각 쌍 formula_27에 대해 무한히 많은 formula_28 값이 존재한다.
다음 표는 최대 흐름 문제를 해결하기 위한 알고리즘의 역사적 발전을 보여준다. 나열된 많은 출판물에는 초기 연구와 결과를 비교하는 유사한 표가 포함되어 있다.
강한 다항 시간.
강한 다항 시간 알고리즘은 입력 수에만 의존하고 이 숫자의 크기에는 의존하지 않는 다항 시간 경계를 가진다. 여기서 입력은 정점(formula_29로 표기)과 간선(formula_30로 표기)이다. 각 알고리즘의 복잡도는 빅 O 표기법을 사용하여 명시된다.
의사 다항 시간 및 약한 다항 시간.
강한 다항 흐름 알고리즘 개발과 병행하여 입력 용량의 크기에 따라 실행 시간이 달라지는 의사 다항 시간 및 약한 다항 시간 경계가 오랫동안 존재했다. 여기서 formula_31 값은 모든 용량을 정수 값으로 재조정했을 때 가장 큰 간선 용량을 나타낸다. (네트워크에 무리수 용량이 포함된 경우, 이 재조정은 불가능할 수 있으며 이러한 알고리즘은 정확한 솔루션을 생성하지 못하거나 근사 솔루션으로도 수렴하지 못할 수 있다.) 의사 다항 시간과 약한 다항 시간의 차이점은 의사 다항 시간 경계는 formula_31에 대해 다항식일 수 있지만, 약한 다항 시간 경계는 formula_33에 대해서만 다항식일 수 있다는 점이다.
정수 흐름 정리.
정수 흐름 정리(integral flow theorem)는 다음을 명시한다.
이 주장은 흐름의 값이 정수라는 것뿐만 아니라(이는 최대 유량 최소 컷 정리에서 직접 파생된다), 모든 간선에 대한 흐름이 정수라는 것이다. 이는 많은 조합론적 응용(아래 참조)에서 중요하며, 간선을 가로지르는 흐름은 해당 간선에 해당하는 항목이 탐색되는 집합에 포함되어야 하는지 여부를 인코딩할 수 있다.
다중 소스 다중 싱크 최대 흐름 문제.
하나의 소스와 하나의 싱크 대신, 소스 집합 formula_34과 싱크 집합 formula_35을 갖는 네트워크 formula_3가 주어졌을 때, formula_5을 가로지르는 최대 흐름을 찾아야 한다. 이 다중 소스 다중 싱크 문제는 formula_38의 각 정점에 연결되는 통합 소스와 formula_39의 각 정점에 연결되는 통합 싱크(슈퍼소스 및 슈퍼싱크라고도 함)를 각 간선에 무한 용량을 할당하여 최대 흐름 문제로 변환할 수 있다(그림 4.1.1 참조).
최대 이분 매칭.
이분 그래프 formula_40가 주어졌을 때, formula_41에서 최대 매칭을 찾아야 한다. 이는 가능한 가장 많은 수의 간선을 포함하는 매칭이다. 이 문제는 다음과 같이 네트워크 formula_42를 구성하여 최대 흐름 문제로 변환할 수 있다.
그러면 formula_5의 최대 흐름 값은 formula_41의 최대 매칭 크기와 같으며, 정수 최대 흐름에서 흐름이 formula_55인 간선을 선택하여 최대 매칭을 찾을 수 있다.
유향 비순환 그래프의 최소 경로 커버.
유향 비순환 그래프 formula_56가 주어졌을 때, formula_29의 각 정점을 덮는 최소 수의 정점-분리 경로를 찾아야 한다. formula_41로부터 이분 그래프 formula_59를 구성할 수 있는데, 여기서
그러면 formula_63가 크기 formula_64의 매칭 formula_65을 갖는 경우에만 formula_41가 formula_64개의 간선과 formula_68개의 경로를 포함하는 정점-분리 경로 커버 formula_69를 갖는다는 것을 보일 수 있다. 여기서 formula_70은 formula_41의 정점 수이다. 따라서 이 문제는 formula_63에서 최대 매칭을 찾음으로써 해결할 수 있다.
formula_63의 매칭 formula_65을 찾고 그로부터 커버 formula_69를 구성했다고 가정하자. 직관적으로 formula_76 두 정점이 formula_65에서 매칭되면, 간선 formula_78는 formula_69에 포함된다. 분명히 formula_69의 간선 수는 formula_64이다. formula_69가 정점-분리임을 보이기 위해 다음을 고려한다.
따라서 어떤 정점도 formula_69에서 두 개의 들어오는 간선이나 두 개의 나가는 간선을 가지지 않으며, 이는 formula_69의 모든 경로가 정점-분리임을 의미한다.
커버 formula_69의 크기가 formula_68임을 보이기 위해, 빈 커버에서 시작하여 점진적으로 구축한다. 커버에 정점 formula_21를 추가하려면, 기존 경로에 추가하거나, 해당 정점에서 시작하는 길이가 0인 새 경로를 생성할 수 있다. 전자의 경우는 formula_8이고 커버의 어떤 경로가 formula_87에서 시작하거나, formula_105이고 어떤 경로가 formula_87에서 끝날 때 적용 가능하다. 후자의 경우는 항상 적용 가능하다. 전자의 경우 커버의 총 간선 수는 1 증가하고 경로 수는 동일하게 유지된다. 후자의 경우 경로 수는 증가하고 간선 수는 동일하게 유지된다. 이제 모든 formula_70개 정점을 덮은 후 커버의 경로 수와 간선 수의 합이 formula_70이라는 것이 분명하다. 따라서 커버의 간선 수가 formula_64이면 경로 수는 formula_68이다.
정점 용량 포함 최대 흐름.
formula_3를 네트워크라고 하자. 간선 용량 외에 각 노드에 용량이 있다고 가정하자. 즉, formula_112인 맵핑이 있어서, 흐름 formula_113는 용량 제약과 흐름 보존뿐만 아니라 다음 정점 용량 제약도 만족해야 한다.
즉, 정점을 통과하는 흐름의 양은 해당 용량을 초과할 수 없다. formula_5을 가로지르는 최대 흐름을 찾기 위해 formula_5을 확장하여 문제를 원래의 최대 흐름 문제로 변환할 수 있다. 먼저, 각 formula_117는 formula_118과 formula_119으로 대체되는데, 여기서 formula_118은 formula_87로 들어가는 간선에 연결되고 formula_119은 formula_87에서 나오는 간선에 연결된다. 그리고 formula_118과 formula_119을 연결하는 간선에 용량 formula_126를 할당한다(그림 4.4.1 참조). 이 확장된 네트워크에서는 정점 용량 제약이 제거되므로 문제는 원래의 최대 흐름 문제로 취급될 수 있다.
s에서 t까지의 최대 경로 수.
유향 그래프 formula_56와 두 정점 formula_128, formula_129가 주어졌을 때, formula_128에서 formula_129까지의 최대 경로 수를 찾아야 한다. 이 문제는 몇 가지 변형이 있다.
1. 경로는 간선-분리여야 한다. 이 문제는 formula_41로부터 네트워크 formula_3를 구성하고, formula_128와 formula_129를 각각 formula_5의 소스와 싱크로 삼으며, 각 간선에 용량을 formula_55로 할당함으로써 최대 흐름 문제로 변환될 수 있다. 이 네트워크에서 최대 흐름이 formula_138이면 formula_138개의 간선-분리 경로가 존재한다.
2. 경로는 독립적이어야 한다. 즉, ( formula_128와 formula_129를 제외하고) 정점-분리여야 한다. 모든 정점과 모든 간선의 용량이 formula_55인 정점 용량을 가진 formula_41로부터 네트워크 formula_3를 구성할 수 있다. 그러면 최대 흐름의 값은 formula_128에서 formula_129까지의 독립 경로의 최대 수와 같다.
3. 경로가 간선-분리 또는 정점-분리일 뿐만 아니라, 경로 길이에 대한 제약도 있다. 즉, 길이가 정확히 formula_138이거나 최대 formula_138인 경로만 계산한다. 이 문제의 대부분의 변형은 작은 formula_138 값을 제외하고는 NP-완전이다.
클로저 문제.
유향 그래프의 클로저는 간선이 C를 떠나지 않는 정점들의 집합 C이다. 클로저 문제는 정점 가중 유향 그래프에서 최대 가중치 또는 최소 가중치 클로저를 찾는 과제이다. 이 문제는 최대 흐름 문제로의 환원을 사용하여 다항 시간에 해결될 수 있다.
실제 응용.
야구 토너먼트 탈락 문제.
야구 토너먼트 탈락 문제에서는 n개의 팀이 리그에서 경쟁한다. 리그 시즌의 특정 단계에서, formula_150는 팀 i의 승리 횟수이고 formula_151는 팀 i가 남은 경기 수이며, formula_152는 팀 j와의 남은 경기 수이다. 팀은 시즌을 1위로 마칠 기회가 없으면 탈락된다. 야구 토너먼트 탈락 문제의 과제는 시즌 중 각 시점에서 어떤 팀이 탈락되는지 결정하는 것이다. 슈워츠는 이 문제를 최대 네트워크 흐름으로 환원하는 방법을 제안했다. 이 방법에서는 팀 k가 탈락되는지 여부를 결정하기 위해 네트워크가 생성된다.
formula_153가 각각 소스와 싱크인 네트워크 formula_56라고 하자. 두 팀 간의 경기 수를 나타내는 게임 노드formula_155를 추가한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 formula_156 (i &lt; j)를 formula_29에 연결하고, 각각을 formula_128에서 용량 formula_152(두 팀 간의 경기 수)를 가진 간선으로 연결한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 formula_156를 두 팀 노드 i와 j에 연결하여 그 중 하나가 이기도록 한다. 이 간선들의 흐름 값은 제한할 필요가 없다. 마지막으로, 팀 노드 i에서 싱크 노드 t로 간선을 만들고 의 용량을 설정하여 팀 i가 formula_161보다 많이 이기는 것을 방지한다.
formula_38를 리그에 참가하는 모든 팀의 집합이라고 하고
이 방법에서는 팀 k가 네트워크 G에서 크기 formula_164의 흐름 값이 존재하는 경우에만 탈락하지 않는다고 주장한다. 언급된 기사에서는 이 흐름 값이 formula_128에서 formula_129까지의 최대 흐름 값임을 증명한다.
항공사 스케줄링.
항공 산업에서 주요 문제 중 하나는 승무원 스케줄링이다. 항공사 스케줄링 문제는 확장된 최대 네트워크 흐름의 응용으로 간주될 수 있다. 이 문제의 입력은 각 항공편이 어디서 언제 출발하고 도착하는지에 대한 정보를 포함하는 항공편 집합 F이다. 항공사 스케줄링의 한 버전에서는 최대 k개의 승무원으로 실행 가능한 스케줄을 생성하는 것이 목표이다.
이 문제를 해결하기 위해 네트워크 흐름 문제의 일반화인 경계 순환(bounded circulation)이라는 순환 문제의 변형을 사용하는데, 이는 간선 흐름에 대한 하한이라는 추가 제약이 있다.
formula_153가 각각 소스 및 싱크 노드인 네트워크 formula_56라고 하자. 각 항공편 i의 출발지 및 목적지에 대해, 항공편 i의 소스 노드 formula_169와 목적지 노드 formula_170를 formula_29에 추가한다. 또한 formula_30에 다음 간선들을 추가한다.
언급된 방법에서, formula_128와 formula_129 사이에서 formula_138 값의 흐름을 찾는 것은 F 항공편 집합에 대해 최대 formula_138명의 승무원으로 실행 가능한 스케줄을 찾는 것과 같다고 주장하고 증명된다.
항공사 스케줄링의 또 다른 버전은 모든 항공편을 수행하는 데 필요한 최소 승무원 수를 찾는 것이다. 이 문제에 대한 해답을 찾기 위해 이분 그래프 formula_187가 생성되는데, 여기서 각 항공편은 집합 A와 집합 B에 복사본을 가진다. 동일한 비행기가 항공편 i 다음에 항공편 j를 수행할 수 있다면, 는 에 연결된다. formula_63에서의 매칭은 F에 대한 스케줄을 유도하며, 분명히 이 그래프에서의 최대 이분 매칭은 최소 승무원 수로 항공사 스케줄을 생성한다. 이 문서의 응용 부분에서 언급된 바와 같이, 최대 이분 매칭은 최대 흐름 문제의 응용이다.
순환-수요 문제.
물건을 생산하는 공장과 물건을 배달해야 하는 마을이 있다. 이들은 도로 네트워크로 연결되어 있으며, 각 도로에는 최대 물건 흐름을 위한 용량 formula_189가 있다. 이 문제는 수요를 만족하는 순환이 존재하는지 찾는 것이다.
이 문제는 최대 흐름 문제로 변환될 수 있다.
이 새로운 네트워크를 formula_56라고 하자. 수요를 만족하는 순환은 다음 경우에만 존재한다:
순환이 존재한다면, 최대 흐름 해를 통해 특정 도로에서 수요를 만족하기 위해 얼마만큼의 물건을 보내야 하는지에 대한 답을 얻을 수 있다.
일부 간선에 흐름의 하한을 추가하여 문제를 확장할 수 있다.
이미지 분할.
클라인베르크와 타르도스는 그들의 책에서 이미지를 분할하는 알고리즘을 제시한다. 그들은 이미지에서 배경과 전경을 찾는 알고리즘을 제시한다. 더 정확히 말하면, 이 알고리즘은 다음과 같이 모델링된 비트맵을 입력으로 받는다. formula_203은 픽셀 i가 전경에 속할 가능성, formula_204은 픽셀 i가 배경에 속할 가능성, formula_205는 두 인접 픽셀 i와 j가 하나는 전경에, 다른 하나는 배경에 놓일 경우의 페널티이다. 목표는 다음 양을 최대화하는 픽셀 집합의 분할 (A, B)을 찾는 것이다.
실제로 A에 있는 픽셀(전경으로 간주)의 경우 formula_207를 얻고, B에 있는 모든 픽셀(배경으로 간주)의 경우 formula_208를 얻는다. 경계에서는 두 인접 픽셀 i와 j 사이에 formula_205를 잃는다. 이는 다음 양을 최소화하는 것과 동등하다.
이제 노드가 픽셀인 네트워크에 소스와 싱크를 추가하여 구축한다(오른쪽 그림 참조). 소스에서 픽셀 i로 가중치 formula_207인 간선을 연결한다. 픽셀 i에서 싱크로 가중치 formula_208인 간선을 연결한다. 픽셀 i에서 픽셀 j로 가중치 formula_205인 간선을 연결한다. 이제 이 네트워크에서 최소 컷(또는 동등하게 최대 흐름)을 계산하는 것이 남았다. 마지막 그림은 최소 컷을 보여준다.
1. 최소 비용 흐름 문제에서는 각 간선 (u,v)가 용량 외에 비용 계수 formula_215도 가진다. 간선을 통한 흐름이 formula_216이면, 총 비용은 formula_217이다. 주어진 크기 formula_218의 흐름을 최소 비용으로 찾는 것이 요구된다. 대부분의 변형에서 비용 계수는 양수 또는 음수일 수 있다. 이 문제에 대한 다양한 다항 시간 알고리즘이 존재한다.
2. 최대 흐름 문제는 선택적 제약으로 보강될 수 있다. 음의 선택적 제약은 특정 쌍의 간선이 동시에 0이 아닌 흐름을 가질 수 없음을 나타낸다. 양의 선택적 제약은 특정 쌍의 간선 중 적어도 하나는 0이 아닌 흐름을 가져야 함을 나타낸다. 음의 제약이 있는 경우, 문제는 단순한 네트워크에서도 강하게 NP-난해가 된다. 양의 제약이 있는 경우, 분수 흐름이 허용되면 문제는 다항식으로 풀리지만, 흐름이 정수여야 할 때는 강하게 NP-난해일 수 있다.
수학, 경제학, 컴퓨터 과학에서 안정 매칭 문제(Stable matching problem)는 각 요소에 대한 선호도 순서가 주어졌을 때, 두 개의 동일한 크기의 요소 집합 사이에 안정적인 매칭을 찾는 문제이다. 매칭은 한 집합의 요소에서 다른 집합의 요소로의 전단사이다. 매칭은 다음의 경우 불안정하다.
다시 말해, 매칭은 (A, B) 쌍이 서로를 현재 매칭된 상대보다 선호하는 경우가 없을 때 안정적이다.
안정 결혼 문제는 다음과 같이 서술되었다.
서로 짝을 이루어야 할 두 계층(이 예에서는 이성애자 남성과 여성)의 존재는 이 문제를 안정 룸메이트 문제와 구별한다.
안정 결혼 문제의 해결책을 찾는 알고리즘은 다양한 실제 상황에서 응용된다. 이 중 가장 잘 알려진 것은 졸업하는 의대생을 첫 병원 배치에 배정하는 것이다. 2012년, 노벨 경제학상은 로이드 S. 섀플리와 앨빈 E. 로스에게 "안정적인 할당 이론과 시장 설계의 실제"에 대한 공로로 수여되었다.
안정 결혼의 중요하고 대규모 응용 중 하나는 대규모 분산 인터넷 서비스에서 사용자를 서버에 할당하는 것이다. 수십억 명의 사용자가 인터넷에서 웹 페이지, 비디오 및 기타 서비스에 액세스하며, 각 사용자는 해당 서비스를 제공하는 전 세계 수십만 개의 서버 중 하나에 매칭되어야 한다. 사용자는 요청된 서비스에 대해 더 빠른 응답 시간을 제공할 만큼 근접한 서버를 선호하여 각 사용자에 대한 서버의 (부분적인) 선호도 순서를 생성한다. 각 서버는 낮은 비용으로 서비스를 제공할 수 있는 사용자를 선호하여 각 서버에 대한 사용자의 (부분적인) 선호도 순서를 생성한다. 전 세계 콘텐츠 및 서비스의 대부분을 배포하는 콘텐츠 전송 네트워크는 이러한 거대하고 복잡한 사용자-서버 간의 안정 결혼 문제를 수십 초마다 해결하여 수십억 명의 사용자가 요청된 웹 페이지, 비디오 또는 기타 서비스를 제공할 수 있는 각 서버와 매칭되도록 한다.
안정 매칭을 위한 게일-섀플리 알고리즘은 히브리 유니언 칼리지 졸업 랍비를 유대인 회중에게 배정하는 데 사용된다.
다른 안정 매칭.
일반적으로 여러 가지 안정 매칭이 있을 수 있다. 예를 들어, 세 명의 남성(A, B, C)과 세 명의 여성(X, Y, Z)이 다음의 선호도를 가지고 있다고 가정해 보자.
이 매칭 배열에는 세 가지 안정적인 해결책이 있다.
세 가지 모두 안정적이다. 불안정성은 두 참가자 모두 다른 대안 매칭에 더 만족해야 하기 때문이다. 한 그룹에게 첫 번째 선택을 주는 것은 매칭이 안정적임을 보장하는데, 이는 그들이 다른 어떤 제안된 매칭에도 불만족할 것이기 때문이다. 모든 사람에게 두 번째 선택을 주는 것은 다른 어떤 매칭도 당사자 중 한 명에게 불만을 일으킬 것임을 보장한다. 일반적으로 안정 결혼 문제의 모든 인스턴스에 대한 해결책 집합은 유한 분배 격자의 구조를 가질 수 있으며, 이 구조는 안정 결혼에 관한 여러 문제에 대한 효율적인 알고리즘을 이끌어낸다.
명의 남성과 명의 여성이 있는 안정 결혼 문제의 균일 무작위 인스턴스에서 안정 매칭의 평균 수는 점근적으로 formula_1이다.
안정 매칭의 최대 수를 갖도록 선택된 안정 결혼 인스턴스에서 이 수는 의 지수 함수이다.
주어진 인스턴스에서 안정 매칭의 수를 세는 것은 #P-완전이다.
알고리즘적 해결책.
1962년, 데이비드 게일과 로이드 섀플리는 대학 입학과 결혼을 원하는 개인들의 맥락에서, 다른 그룹에 동일한 수의 개체가 있을 경우 모든 결과적인 짝짓기/매칭 요소가 안정적이도록 항상 짝지어진 커플로 해결하는 것이 가능함을 증명했다. 그들은 이를 위한 알고리즘을 제시했다.
게일-섀플리 알고리즘 (지연 수락 알고리즘이라고도 함)은 여러 "라운드"(또는 "반복")를 포함한다.
이 알고리즘은 남성 또는 여성의 수가 formula_2일 때 시간 formula_3 내에 모든 참가자에 대해 안정적인 결혼을 생성함을 보장한다.
가능한 모든 안정 매칭 중에서 이 알고리즘은 항상 모든 남성에게 가장 좋고 모든 여성에게는 가장 나쁜 매칭을 생성한다.
이것은 남성(청혼하는 측)의 관점에서 진실된 메커니즘이다. 즉, 어떤 남성도 자신의 선호도를 잘못 보고하여 자신에게 더 나은 매칭을 얻을 수 없다. 또한 GS 알고리즘은 남성에 대한 그룹 전략 증명(group-strategy proof)이다. 즉, 남성 연합이 자신들의 선호도를 왜곡하여 연합 내 모든 남성이 더 나은 상태가 되도록 조정할 수 없다. 그러나 일부 연합이 자신들의 선호도를 왜곡하여 일부 남성은 더 나은 상태가 되고 다른 남성은 같은 배우자를 유지하는 것이 가능하다.
GS 알고리즘은 여성(검토하는 측)에게는 진실되지 않다. 각 여성은 자신의 선호도를 잘못 보고하여 더 나은 매칭을 얻을 수 있다.
농촌 병원 정리.
농촌 병원 정리는 안정 매칭 문제의 더 일반적인 변형에 관한 것으로, 병원에 의사를 배치하는 문제에 적용되는 경우 기본 n-대-n 형태의 안정 결혼 문제와 다음과 같은 방식으로 다르다.
이 경우 안정성 조건은 매칭되지 않은 어떤 쌍도 매칭에서의 자신의 상황(다른 배우자이든 매칭되지 않은 상태이든)보다 서로를 선호하지 않는 것이다. 이 조건에서도 안정 매칭은 여전히 존재하며, 게일-섀플리 알고리즘으로 찾을 수 있다.
이러한 종류의 안정 매칭 문제에 대해 농촌 병원 정리는 다음과 같이 설명한다.
무차별성을 포함한 안정 매칭에서는 일부 남성이 두 명 이상의 여성에게 무관심할 수 있으며 그 반대도 마찬가지이다.
안정 룸메이트 문제는 안정 결혼 문제와 유사하지만, 모든 참가자가 단일 풀에 속한다는 점(동일한 수의 "남성"과 "여성"으로 나뉘는 대신)에서 다르다.
병원 레지던트 문제 – 또한 대학 입학 문제로 알려짐 –는 병원이 여러 레지던트를 받을 수 있거나 대학이 한 명 이상의 학생으로 구성된 신입생을 받을 수 있다는 점에서 안정 결혼 문제와 다르다. 병원/레지던트 문제를 해결하는 알고리즘은 병원 중심적일 수 있다(1995년 이전 NRMP가 그랬던 것처럼). 또는 레지던트 중심적일 수 있다. 이 문제는 안정 결혼 문제가 해결된 동일한 게일과 섀플리의 원본 논문에서 알고리즘과 함께 해결되었다.
커플을 포함한 병원/레지던트 문제는 레지던트 집합에 커플을 포함할 수 있으며, 이들은 함께 배정되어야 한다. 동일한 병원이거나 커플이 선택한 특정 병원 쌍(예: 결혼한 커플이 함께 지내며 서로 멀리 떨어진 프로그램에 갇히지 않도록 보장하기를 원함)에 배정될 수 있다. 병원/레지던트 문제에 커플을 추가하면 이 문제는 NP-완전이 된다.
할당 문제는 최대 가중치를 갖는 가중 이분 그래프에서 매칭을 찾는 것을 목표로 한다. 최대 가중치 매칭은 안정적일 필요는 없지만, 일부 응용에서는 안정적인 매칭보다 최대 가중치 매칭이 더 좋다.
계약을 포함한 매칭 문제는 참가자들이 다른 계약 조건으로 매칭될 수 있는 매칭 문제의 일반화이다. 계약의 중요한 특별한 경우는 유연한 임금을 포함한 매칭이다.
저작자표시(attribution)는 저작권법에서 저작권자 또는 저작물 작성자에게 크레디트를 부여하여 인정하는 것을 말한다. 저작물이 저작권의 보호를 받는 경우, 저작자가 작성한 저작물의 일부를 직접 인용할 때 저작자표시를 요구하는 오랜 전통이 있다.
저작자는 라이선스를 통해 저작자표시를 공식적으로 요구할 수 있으며, 이는 타인이 저작물을 작성했다고 주장하는 것을 법적으로 방지하고 저작권자가 저작물 작성으로 인한 명예 이익을 유지할 수 있도록 한다. 저작권자가 저작자 자신인 경우, 이러한 행위는 저작물에 대한 크레디트를 제공함으로써 창작자를 인정하는 예의와 존경의 표시로 종종 도덕적으로 여겨진다.
그러나 저작권의 보호를 받지 않는 퍼블릭 도메인 저작물은 세계 대부분의 지역에서 그러한 저작자표시 요구사항이 없다. 이것이 범죄는 아니지만 비윤리적인 행위인 표절과 저작자의 법적 조치 원인이 될 수 있는 저작권 침해를 구별하는 요소이다.
저작권자표시.
세계 대부분의 국가에서는 베른 협약으로 인해 원본 자료에 저작권자표시가 필수는 아니다. 가장 기본적인 형태의 저작자표시는 종종 Copyright © [연도] [저작권자 이름]의 형태로 저작권자의 신원을 명시하는 것이다. 미국에서는 이러한 표시의 보존이 과거에는 저작물이 퍼블릭 도메인으로 들어가는 것을 막기 위한 필수 요건이었다. 이것은 1988년 베른 협약 이행법에 의해 저작권 등록 및 저작권 기명 요구사항이 종료된 1989년 3월 1일에 변경되었다.
류하오판(, 2003년 10월 23일 ~ )는 중화인민공화국의 축구 선수로 포지션은 센터백이며 현재 중국 슈퍼리그 저장 FC 소속이다.
컴퓨터 예약 시스템(computer reservation system), 컴퓨터 좌석 예약 시스템 또는 중앙 예약 시스템(central reservation systems, CRS)은 항공 여행, 호텔, 렌터카 또는 기타 활동과 관련된 정보를 저장하고 검색하며 거래를 수행하는 데 사용되는 컴퓨터화된 시스템이다. 원래 항공사에서 설계하고 운영했지만, CRS는 나중에 여행사와 글로벌 유통 시스템(GDS)에서 여러 항공사의 티켓을 예약하고 판매하는 데 사용하도록 확장되었다. 대부분의 항공사는 CRS를 GDS 회사에 아웃소싱했으며, 이들 회사는 인터넷 게이트웨이를 통해 소비자에게도 접근을 가능하게 한다.
현대 GDS는 일반적으로 호텔 객실, 렌터카, 항공권뿐만 아니라 기타 활동 및 투어를 예약할 수 있게 한다. 또한 일부 시장에서는 철도 예약 및 버스 예약에 대한 접근을 제공하지만, 이들이 항상 주 시스템과 통합되는 것은 아니다. 이들은 호텔 산업의 사용자에게 컴퓨터화된 정보를 전달하는 데 사용되어 예약을 하고 호텔이 초과 예약되지 않도록 보장한다.
항공사 예약 시스템은 더 큰 승객 서비스 시스템에 통합될 수 있으며, 여기에는 항공사 재고 시스템과 출발 통제 시스템도 포함된다. 현재의 중앙 집중식 예약 시스템은 네트워크 전체의 시스템 중단에 취약하다.
MARS-1.
MARS-1 기차표 예약 시스템은 1950년대에 일본국유철도 연구개발원(현재의 철도종합기술연구소)에 의해 설계 및 계획되었으며, 이 시스템은 결국 1958년에 히타치 제작소에 의해 생산되었다. 이는 세계 최초의 기차 좌석 예약 시스템이었다. MARS-1은 좌석 위치를 예약할 수 있었으며, 중앙 처리 장치와 40만 비트의 자기 드럼 메모리 장치로 좌석 파일을 보관하는 트랜지스터 컴퓨터로 제어되었다. 이 시스템은 많은 프로세서 레지스터를 사용하여 기차의 좌석이 비어 있는지 예약되어 있는지를 나타내어 좌석 패턴 검색 및 업데이트, 터미널과의 통신, 예약 통지 인쇄, CRT 디스플레이를 가속화했다.
1953년 트랜스 캐나다 항공 (TCA)은 원격 단말기를 갖춘 컴퓨터 기반 시스템을 조사하기 시작했으며, 그해 여름 토론토 대학교의 페란티 마크 1 기계에서 한 가지 설계를 시험했다. 성공적이었지만, 연구원들은 입출력이 큰 문제임을 발견했다. 페란티 캐나다는 이 프로젝트에 참여하여 신뢰할 수 없는 진공관 기반 마크 1 대신 천공 카드와 트랜지스터화된 컴퓨터를 사용하는 새로운 시스템을 제안했다. 그 결과물인 ReserVec 시스템은 1962년에 작동을 시작하여 1963년 1월에 모든 예약 업무를 인계했다. 터미널은 TCA의 모든 티켓 판매 사무실에 설치되어 원격 운영자가 필요 없이 약 1초 만에 모든 조회 및 예약이 완료될 수 있었다.
1953년 아메리칸 항공의 CEO C. R. 스미스는 로스앤젤레스에서 뉴욕으로 가는 비행기에서 우연히 IBM의 고위 영업 대표인 R. 블레어 스미스 옆에 앉게 되었다. C.R.은 블레어를 초대하여 그들의 Reservisor 시스템을 방문하고 IBM이 시스템을 개선할 방법을 찾아보라고 요청했다. 블레어는 토마스 왓슨 주니어에게 아메리칸 항공이 대규모 협력에 관심이 있다고 알렸고, 일련의 저수준 연구가 시작되었다. 이들의 자동화된 항공사 예약 시스템 (ARS) 아이디어는 1959년 반자동 비즈니스 연구 환경(SABRE)으로 알려진 벤처로 이어졌고, 이듬해에 출시되었다. 1964년 12월 SABRE가 완전히 완성되었을 때, 이는 세계 최초의 온라인 트랜잭션 처리 시스템이었으며, 당시 "세계에서 가장 큰 민간 실시간 상업 전자 정보 처리 시스템"이었다.
다른 항공사들도 자체 시스템을 구축했다. 팬아메리칸 월드 항공은 1965년에 PANAMAC 시스템을 출시했고 델타 항공은 1965년에 DELTAMATIC을 출시했는데, 이들 모두 IBM이 SABRE와 함께 SABER 공동 프로젝트의 일환으로 개발했다 (이후 아메리칸 항공은 프로젝트에 다른 이름을 고집하여 SABRE라는 이름이 붙었다). DELTAMATIC에 이어 1968년에는 델타 자동 여행 계정 시스템(DATAS)이 나왔다.
1965년 IBM은 SABER 공동 프로젝트에 대한 작업을 PARS로 일반화했으며, 이는 1971년까지 산업 표준이 되었다. 1971년부터 1973년까지 아메리칸 항공은 SABRE를 PARS 기반 시스템으로 전환했다.
곧 여행사들은 다양한 ARS에 직접 접속하여 예약을 함으로써 자신들의 업무를 자동화할 수 있는 시스템을 추진하기 시작했다. 이것이 에이전트들에게 너무 많은 권한을 부여할 것을 우려한 아메리칸 항공의 경영진 로버트 크랜달은 미국 여행의 중앙 정보 처리 기관이 될 산업 전체의 컴퓨터 예약 시스템을 만들 것을 제안했다. 다른 항공사들은 이것이 미국의 반독점법을 위반할 수 있다는 이유로 반대했다.
여행사 접근.
1976년, 유나이티드 항공은 아폴로 시스템을 여행사들에게 제공하기 시작했다. 비록 에이전트들이 유나이티드의 경쟁사 항공권을 예약할 수는 없었지만, 편리한 터미널의 마케팅 가치는 필수불가결한 것으로 입증되었다. SABRE, PARS, DATAS도 곧 여행사들에게 공개되었다. 1978년 항공사 규제 완화법 이후, 효율적인 CRS는 특히 중요하게 입증되었다. 일부 집계에 따르면, 텍사스 에어의 임원 프랭크 로렌조는 SystemOne CRS에 대한 통제권을 얻기 위해 적자를 보고 있던 이스턴 항공을 특별히 인수했다.
또한 1976년 비데콤 인터내셔널은 영국항공, 브리티시 칼레도니안, CCL과 함께 세계 최초의 다중 접속 예약 시스템인 트래비콤을 출시했으며(전적으로 비데콤 기술 기반), 처음에는 2개, 이후 49개 국제 항공사(영국항공, 브리티시 칼레도니안, 트랜스월드 항공, 팬아메리칸 월드 항공, 콴타스 항공, 싱가포르 항공, 에어 프랑스, 루프트한자, 스칸디나비아 항공, 에어 캐나다, KLM, 알리탈리아, 캐세이퍼시픽 항공, 일본항공 포함)에 영국 내 수천 개의 여행사로 분배하는 네트워크를 형성했다. 이를 통해 에이전트와 항공사는 공통 분배 언어 및 네트워크를 통해 통신할 수 있었으며, 1987년까지 영국 항공 비즈니스 거래 예약의 97%를 처리했다. 이 시스템은 비데콤에 의해 중동(DMARS), 뉴질랜드, 쿠웨이트(KMARS), 아일랜드, 카리브해, 미국, 홍콩 등 세계 다른 지역에서도 복제되었다. 트래비콤은 트래블 오토메이션 서비스(Travel Automation Services Ltd)의 상호였다. 영국항공(당시 트래블 오토메이션 서비스의 100%를 소유)이 갈릴레오 시스템 개발에 참여하기로 결정하자 트래비콤은 상호를 갈릴레오 UK로 변경하고 트래비콤에서 갈릴레오로 에이전시를 이전하는 과정이 시작되었다.
유럽 항공사들도 1980년대에 여행 수요 증가와 GDS가 ever-increasing 서비스와 검색 기능을 제공할 수 있도록 하는 기술 발전의 힘을 받아 자국 내에 자체 예약 시스템을 배포하며 이 분야에 투자하기 시작했다. 1987년, 에어 프랑스와 서독의 루프트한자가 이끄는 컨소시엄은 SystemOne을 모델로 한 아마데우스를 개발했다. 아마데우스 글로벌 트래블 디스트리뷰션은 1992년에 출시되었다. 1990년, 델타 항공, 노스웨스트 항공, 트랜스월드 항공은 월드스팬을 결성했고, 1993년에는 또 다른 컨소시엄(영국항공, KLM, 유나이티드 항공 등을 포함)이 아폴로를 기반으로 경쟁사 갈릴레오 GDS를 결성했다. 저비용 항공사 부문 및 중소규모 국내 및 지역 항공사를 포함하여 4대 네트워크가 다루지 않는 틈새 시장을 겨냥한 KIU와 같은 수많은 소규모 회사들도 형성되었다.
처음에 항공사의 예약 시스템은 자사 항공편을 다른 항공편보다 선호했다. 1987년까지 미국 정부 규정에 따라 SABRE와 다른 미국 시스템은 중립적이어야 했으며, 항공사는 대신 이 시스템에 대한 접근권을 이윤을 위해 판매했다. 유럽 항공사의 시스템은 여전히 소유주의 항공편에 편향되어 있었지만, 플라이트 인터내셔널은 이들도 필연적으로 중립적이 될 것이라고 보도했다.
수년간 글로벌 유통 시스템 (GDS)은 여행 산업에서 지배적인 위치를 차지해 왔다. GDS를 우회하고 높은 GDS 수수료를 피하기 위해 항공사들은 웹사이트를 통해 직접 항공편을 판매하기 시작했다. GDS를 우회하는 또 다른 방법은 아메리칸 항공과 같은 여행사와의 직접 연결이다.
《구원자》는 2025년에 개봉한 대한민국의 영화이다.
디지털 자산 관리(Digital asset management, DAM) 및 컴퓨터 응용 프로그램으로서의 사용 구현은 소유자 및 대리인이 데이터 파일에 대한 작업을 수행할 수 있도록 디지털 자산 수집에 필요하다.
미디어 자산 관리 (MAM)라는 용어는 일반적으로 오디오 녹음, 사진, 비디오와 같이 "미디어"로 간주되는 디지털 객체의 하위 집합에 적용될 때 디지털 자산 관리를 지칭하는 데 사용될 수 있다. 미디어, 특히 비디오를 포함하는 모든 편집 과정은 MAM을 사용하여 미디어 구성 요소에 접근하여 유연하게 함께 편집하거나 라이브 피드와 결합할 수 있다. MAM은 일반적으로 이미지에서 패턴 인식을 사용하여 수집하거나 수동으로 입력한 메타데이터로 구성된 검색 가능한 이미지, 오디오 및 비디오 인덱스를 하나 이상 제공한다.
디지털 자산 관리(DAM)는 디지털 방식으로 저장된 모든 형태의 정보 조각을 전자적으로 관리하는 데 초점을 맞출 수 있다. DAM은 분명히 전략적인 반면 MAM은 거의 항상 전술적이다. 두 자산 관리 모두 주로 보관, 보존 및 특히 재사용에 사용되는 장기 저장 콘텐츠를 반영한다.
응용 프로그램은 아날로그 녹음 및 디지털 데이터 도메인에서 (인코딩, 이미지 스캐닝, 광학 문자 인식 등을 통해) 디지털 자산 관리를 가져오거나 새 개체로 작성하여 구현한다.
DAM 시스템의 주요 기능은 자산의 내용과 메타데이터를 통해 자산의 정보 검색을 지원하는 검색 가능한 인덱스를 제공하여 사용자가 자산을 쉽게 이용할 수 있도록 하는 것이다. 카탈로그 기능은 일반적으로 새 자산에 대한 수집 프로세스의 일부이다.
워크플로우.
디지털 자산에는 일반적으로 생성, 승인, 라이브, 보관, 삭제와 같은 다양한 상태를 포함할 수 있는 수명 주기가 있다.
종종 DAM 시스템은 디지털 자산의 이전 버전을 저장하고 해당 버전을 다운로드하거나 되돌릴 수 있도록 한다. 따라서 DAM 시스템은 고급 유형의 버전 관리 시스템으로 작동할 수 있다.
DAM 시스템에는 일반적으로 데이터 보호 동의 및 자산을 승인하고 분류하는 기능과 같은 컴플라이언스 조치가 포함되어 산업 또는 지역 컴플라이언스가 충족되도록 보장하며 사용자가 자신의 위치에 대해 법률을 준수하는 자산에만 접근할 수 있도록 한다.
마지막으로, DAM 시스템은 일반적으로 관련 사람들이 자산에 접근할 수 있도록 보안 제어를 포함한다. 이는 종종 통합 인증과 같은 기술을 통해 기존 디렉터리 서비스와 통합하는 것을 포함한다.
소규모 DAM 시스템은 예를 들어 비디오 제작 시스템과 같은 특정 운영 환경에서 사용된다. 이들 간의 주요 차이점은 자산을 관리하기 위해 디지털 사본을 만드는 데 사용되는 입력 인코더 유형과 문 및 온라인 리소스로 사용 가능하게 만드는 데 사용되는 출력 디코더 및 포맷터 유형이다. 콘텐츠 항목의 메타데이터는 처리 중 콘텐츠를 처리하는 데 필요한 코덱 선택에 대한 가이드 역할을 할 수 있으며 접근 제어 규칙을 적용하여 승인 정책을 시행할 때 유용할 수 있다.
워크플로우에서 특정 기술이 필요한 자산은 해당 자산을 생성하거나 저장하는 도구 설계뿐만 아니라 해당 자산을 배포하고 보관하는 시스템 아키텍처에서 대역폭, 대기 시간 및 접근 제어 요구 사항을 고려해야 한다.
자산이 활발하게 작업되지 않을 때, 이들은 운영 중 필요한 형식보다 저장 비용이 "더 저렴한" 데이터베이스의 바이너리 라지 오브젝트(바이너리 라지 오브젝트) 또는 표준 파일 시스템의 파일 등 다양한 형식으로 DAM에 저장될 수 있다. 이를 통해 고성능 처리 시스템의 집합체가 중앙에 고밀도 저장 솔루션을 갖춘 네트워크 내에서 대규모 DAM을 구현할 수 있다.
디지털 자산 관리 시스템은 다음 분류에 속한다.
이러한 모든 유형에는 워크플로우 관리, 협업, 프로젝트 관리 및 개정 관리 기능이 포함된다.
미디어 자산 문제.
자산은 여러 형식과 일련의 버전으로 존재할 수 있다. 원본 자산의 디지털 버전은 일반적으로 최종 사용에 허용 가능한 품질을 보장하는 데 필요한 최고 해상도, 색 농도 및 (해당하는 경우) 프레임 속도로 캡처된다. 시각적 인덱싱에 사용하기 위한 저품질 섬네일 사본도 있을 수 있다.
자산의 메타데이터에는 패키징, 인코딩, 출처, 소유권 및 접근 권한, 원본 생성 위치가 포함될 수 있다. 이는 자산에 대해 작업하거나 자산과 함께 사용되는 도구 및 시스템에 자산이 어떻게 처리되고 표시되어야 하는지에 대한 힌트를 제공하는 데 사용된다.
코드워리어(CodeWarrior)는 NXP 반도체가 임베디드 시스템에 사용되는 여러 마이크로컨트롤러 및 마이크로프로세서 (프리스케일 콜드파이어, ColdFire+, Kinetis, Qorivva, PX, Freescale RS08, Freescale S08, S12Z)와 디지털 신호 컨트롤러 (DSC MC56F80X 및 MC5680XX)용 소프트웨어를 편집, 컴파일 및 디버깅하기 위해 발행한 통합 개발 환경 (IDE)이다.
이 시스템은 메트로웍스가 매킨토시에서 개발했으며, 이 플랫폼에서 기존 모토로라 68k와 파워PC (PPC) 명령어 집합 아키텍처를 모두 깨끗하게 지원한 최초의 개발 시스템 중 하나였다. 애플이 파워PC로 전환하는 동안 코드워리어는 시맨텍의 THINK C와 애플 자체의 Macintosh Programmer's Workshop을 빠르게 대체하며 맥의 사실상 표준 개발 시스템이 되었다. 1996년 애플의 NeXT 인수는 맥 프로그래밍이 NeXT 플랫폼 자체 개발 도구인 GNU 컴파일러 모음을 기반으로 구축된 인터페이스 빌더와 프로젝트 빌더로 옮겨가면서 코드워리어의 중요성이 감소하는 결과를 가져왔다.
메트로웍스는 코드워리어를 마이크로소프트 윈도우로 이식하고 더 다양한 플랫폼을 위한 컴파일러를 도입하며 이에 대응했다. 이는 모토로라의 다양한 마이크로컨트롤러 라인에 대한 소프트웨어 스택의 주요 부분이 되었고, 결국 1999년 모토로라가 메트로웍스를 인수하게 만들었다. 이 제품은 PPC 또는 기타 모토로라 프로세서 기반의 대부분의 플랫폼과 많은 게임 콘솔에서 널리 사용되었다. 이 제품은 2004년 프리스케일 세미컨덕터가 설립될 때 그 회사로 넘어갔고, 2015년 NXP가 프리스케일을 인수하면서 NXP로 넘어갔다.
원래는 "클래식 IDE"로 알려진 단일 통합 제품이었으나, 나중에 IDE는 이클립스 IDE로 대체되었다. 현재 버전은 클래식 IDE 6.3 버전과 이클립스 IDE 11.0 버전이다. 지원되는 언어는 C, C++, 그리고 어셈블리어이다.
1992년 10월, 시맨텍 언어 제품 그룹의 개발 관리자였던 존 맥이너니는 자신의 파워PC 제품 작업을 위해 회사를 떠났다. 처음에는 파스칼 컴파일러를 생각했다. BBEdit의 저자인 리치 시겔은 맥이너니가 시맨텍을 떠났다는 소식을 듣고 몬트리올의 메트로웍스의 그렉 갈라노스에게 이 소식을 전했다. 갈라노스는 맥이너니에게 전화를 걸어 "꿈의 직업을 설명해달라"고 요청했다. 맥이너니는 애플이 미래에 사용하겠다고 발표한 새로운 파워PC (PPC) 칩을 위한 코드 생성기를 쓰고 싶다고 말했다.
메트로웍스는 이미 파스칼과 모듈라-2 컴파일러를 개발했는데, 원래는 아타리 ST용이었으나 나중에 맥을 포함한 여러 동시대 기계로 이식되었다. 그들은 맥이너니를 몬트리올로 초청하여 갈라노스와 그의 파트너 장 벨랑제와 만났다. 그들은 PPC를 위한 새로운 도구 체인에 큰 기회가 있다고 느꼈고, 그들의 컴파일러와 맥이너니가 작성한 새로운 PPC 코드 생성기를 결합했다. 그들은 맥의 주요 개발 시스템 공급업체인 시맨텍보다 더 빠르게 시장에 진출할 수 있다고 느꼈다. 시맨텍은 PPC용 제품 출시를 앞두고 있지 않았고, 애플은 수년 동안 무시되었던 Macintosh Programmers Workshop (MPW)의 업데이트 버전을 PPC 개발에 사용하고 있었다. 맥이너니는 관심이 있었지만 그들의 컴파일러에 감명받지 못했고, 이 초기 접촉에서는 거의 아무것도 나오지 않았다.
비슷한 시기에 안드레아스 호멜은 독일 대학에서 컴퓨터 과학 석사 학위를 마치고 있었다. 그는 C로 컴퓨터 게임을 작성하는 데 관심을 갖게 되었지만, 기존 컴파일러가 품질이 낮은 코드를 생성한다는 것을 알게 되었다. 그는 수년 동안 68k용 C 컴파일러와 간단한 통합 개발 환경 (IDE)을 개발했다. 대학을 마친 후 그는 함부르크에서 일자리를 제안받았지만, 자신의 컴파일러 시장성이 있는지 알아보기로 결정했다. 몇 달 후 그는 갈라노스로부터 전화를 받았다. 여러 차례의 대서양 횡단 전화 통화 끝에 갈라노스는 호멜을 몬트리올로 초대하여 함께 일하는 것에 대해 논의했다.
1993년 2월, 갈라노스는 맥이너니에게 전화하여 팔로 알토에서 만나 메트로웍스가 인수한 새로운 C 컴파일러를 검토할 수 있는지 물었다. 맥이너니는 매우 감명받았다. 이 시스템은 초기 Think C 버전과 비슷해 보였고 매우 빨랐다. "다이아몬드 원석"이라고 묘사하며, 맥이너니는 몇 시간 내에 메트로웍스와 계약을 맺었다. 호멜은 자신의 C 컴파일러를 완전한 C++ 구현으로 확장하면서 코드 생성 단계와 분리할 것이었다. 맥이너니는 호멜의 컴파일러에 의해 구동되는 새로운 PPC 코드 생성기를 작성할 것이었다. 호멜의 기존 68K 코드 생성기는 그 플랫폼에 사용될 것이며, 파스칼도 지원하도록 약간 수정될 것이었다. 몬트리올의 베라르디노 바라타와 마르셀 아킴은 IDE 개발을 계속하고 동일한 코드 생성기에서 실행되는 파스칼 컴파일러를 개발할 것이었다.
새로운 시스템을 검토하면서 맥이너니는 코드 생성에 완전히 새로운 접근 방식을 취하기로 결정했다. 당시의 일반적인 컴파일러는 중간 표현 (IR)을 반복적으로 검사하여 점점 더 최적화된 코드 버전을 생성한 다음 최종적으로 기계 명령어로 변환했다. 이 접근 방식은 RISC 플랫폼에는 덜 중요했는데, 명령어 집합 아키텍처가 훨씬 간단하고 주어진 작업에 어떤 특정 유형의 명령어를 사용할지 결정하는 데 훨씬 적은 노력이 들었기 때문이다. 대신 맥이너니의 새로운 코드 생성기는 초기 IR을 직접 PPC 코드로 변환했다.
주요 변경 사항은 레지스터 사용을 위한 차이틴의 알고리즘을 구현한 것이었다. 1982년에 도입된 이 시스템은 컴파일러 기술의 획기적인 발전이었다. 이는 코드 생성기가 지역 변수를 프로세서 레지스터에 매우 효율적으로 매핑할 수 있도록 했다. 성능을 위해 레지스터 사용에 의존하는 기계(RISC 프로세서의 주요 개념 중 하나)에서 이 기술은 엄청난 개선을 가져올 수 있다. 단점은 O(N2) 프로세스이므로 결과를 계산하는 데 비용이 많이 든다는 것이다.
PPC 컴파일러 개발을 돕기 위해 애플의 조던 매트슨은 맥이너니에게 RS/6000 시스템 중 하나를 보냈다. 1993년 8월까지 기본 시스템이 실행되었다. 맥이너니는 메트로웍스에서 일자리를 찾고 있던 전 시맨텍 동료인 댄 포드웰로부터 전화를 받았다. 갈라노스는 포드웰에게 전화했고, 그는 즉시 고용되어 디버거를 작성했으며, 단 4주 만에 완료했다.
프로토타입 파워 맥 기계는 1993년 9월 회사에 보내졌다. 당시 메인 IDE와 컴파일러 도구 체인은 여전히 68k 기계에서 실행되어 PPC 바이너리를 생성했으며, 이 바이너리는 프로토타입으로 옮겨져 디버깅되었다. 이를 통해 시스템을 PPC로 빠르게 포팅할 수 있었고, 12월까지 전체 시스템이 생산 준비를 마쳤다.
이 시스템은 1994년 1월 맥월드 엑스포에서 코드워리어라는 이름으로 출시되었다. 파워 맥도 그 달에 출시될 예정이었으나, 일련의 지연으로 인해 3월 14일 파워 맥 기계의 공식 출시까지 연기되었다.
당시 애플의 MPW와 시맨텍의 Think C는 모두 68k 기계에서만 실행되었으며, MPW만이 PPC 바이너리를 생성할 수 있었다. PPC에서 기본적으로 실행되고 해당 플랫폼 전용 코드를 기반으로 한 코드워리어는 단일 기계에서 개발 및 디버깅을 가능하게 하면서 훨씬 더 높은 성능을 제공했다. 다른 개발 시스템의 판매는 거의 하룻밤 사이에 중단되었다. 1986년부터 맥 개발 시장을 지배했던 시맨텍은 1995년 3월 말까지 기본 PPC 버전을 출시하지 않았다. 이때까지 몇몇 주요 맥 소프트웨어 공급업체는 코드워리어로 전환했으며 시맨텍은 맥에서 어떤 시장 점유율도 다시 확보할 수 없었다.
코드워리어는 애플이 기계 아키텍처를 68K 프로세서에서 파워PC로 전환하는 데 성공하는 데 핵심적인 역할을 했다. 경쟁사(애플의 MPW 도구 및 시맨텍 C++)가 대부분 불완전하거나 시장에 늦게 출시되었을 때, 코드워리어는 완전하고 견고한 파워PC 컴파일러를 제공했기 때문이다. 메트로웍스는 또한 68K 및 파워PC 코드를 모두 포함하는 팻 바이너리를 쉽게 생성할 수 있도록 했다.
매킨토시용 코드워리어의 자바 지원은 1996년 5월, 코드워리어 9에 예정되어 있다고 발표되었다. 메트로웍스는 새로운 IDE를 작성하는 대신 디버깅을 포함한 자바 도구 지원을 코드워리어에 추가하는 접근 방식을 취했다.
여러 플랫폼으로 이동.
1997년 애플은 NeXT를 인수하여 그들의 운영체제인 OpenStep을 미래 맥 제품의 기반으로 사용했다. OpenStep은 전체 운영체제와 모든 응용 프로그램이 내부 개발 시스템을 사용하여 구축된다는 개념을 기반으로 했다. 이것은 GNU 컴파일러 모음 (GCC)을 기반으로 했다. 코드워리어는 플랫폼에서 "클래식" 맥 응용 프로그램을 작성하는 개발자에게 여전히 중요했지만, 개발이 주로 새로운 OpenStep 플랫폼을 통해 이루어질 것이므로 GCC를 통해 이루어질 것이라는 명확한 시간 프레임이 있었다.
1996년 8월, 메트로웍스는 BeOS 소프트웨어 개발자들이 이미 사용할 수 있었던 파워PC 컴파일러를 보완하는 BeOS 버전의 IDE인 BeIDE인 CodeWarrior for BeBox를 발표했다.
모토로라 시대.
메트로웍스가 1999년 모토로라에 인수된 후, 회사는 임베디드 응용 프로그램에 집중했으며, 데스크톱 컴퓨터용 컴파일러에는 적은 노력을 기울였다. 2005년 7월 29일, 그들은 다음 출시 버전인 CodeWarrior Pro 10 이후에는 Mac용 CodeWarrior가 중단될 것이라고 발표했다. 메트로웍스는 지난 4년 동안 제품의 매출 비중이 22%에서 5%로 떨어졌으며, 회사가 임베디드 개발 시장에 집중하기 위한 노력 때문이라고 밝혔다. 코드워리어에 대한 수요는 애플이 엑스코드 (OS X용 자체 소프트웨어 개발 키트)를 무료로 배포하기 시작하면서 감소했을 것으로 추정된다. 또한, 애플이 인텔 칩으로 전환하면서 메트로웍스는 2005년 초에 인텔 컴파일러 기술을 노키아에 판매했기 때문에 명확한 제품이 없게 되었다.
전성기 시절 이 제품은 매년 여러 차례의 신속한 출시 주기와 독특한 광고 캠페인으로 유명했다. 그들의 "괴짜웨어" 셔츠는 뉴욕 타임스의 패션 페이지에 실리기도 했다.