코딩딩딩

1. 그리디 알고리즘 'greedy'란 한국어로 '탐욕스러운'으로 해석이 된다. 탐욕스러운 알고리즘? 어떻게 해야 탐욕적인 거지? 등 여러 의문이 생길 수 있다. 정리를 하자면 그리디 알고리즘이란 "선택의 순간에서 최적의 선택만을 하는 방법"을 의미한다. 단, 매 순간마다 최적의 선택을 하지만 남아 있는 선택들은 고려를 하지 않기 때문에결과가 항상 최적이라는 보장은 없다. 그러므로, 그리디 알고리즘을 사용하기 위해선 조건이 따라붙어야 한다. 2. 그리디 알고리즘의 최적해 도달 조건 1)  탐욕적 선택 속성(greedy choice property)탐욕적인 선택이 항상 최적의 해를 보장한다. 즉, 각각의 선택이 서로 영향을 주지 않는다. 2) 최적 부분 구조(optimal substructure)부분 문제..

1. join 함수 기본적으로 리스트를 출력 시 예를 들어 ['1', '2', '3'] 이런 식으로 ','을 포함하여 출력이 된다. 각 원소값만 붙여서 하나의 수로 나타내고 싶었을 때가 있었을 것이다. 이런 경우에 구분기호를 없애고 출력을 도와주는 join함수를 사용하면 된다. ''.join(리스트): 리스트 요소만을 합친 문자열 반환 ex) ''.join(['1', '2', '3']) -> '123' '구분문자'.join(리스트): 리스트 요소와 구분문자를 합친 문자열 반환ex) '/'.join(['1', '2', '3']) -> '1/2/3' 결국, '구분문자'에 어떤 문자를 넣어주는지에 따라서 형성되는 문자열이 달라진다고 생각하면 된다. 2. 예제 적용 (백준 16943) 실제로 문제를 풀다 보면 ..

1. 개념 포함-배제 원칙은 합집합의 원소의 개수를 구하는 것과 동일하다고 볼 수 있다. 집합 2개: |A∪B| = |A| + |B| - |A∩B| 집합 3개: |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| 집합 4개: |A∪B∪C∪D | = |A| + |B| + |C| + |D| - |A∩B| - |A∩C| - |B∩C| - |A∩D| - |B ∩D| - |C∩D| + |A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D| - |A∩ B∩C∩D| 위의 공식에서 나타나듯이 집합의 개수를 늘려가면서 교집합 연산을 하는 것을 확인할 수 있다. 부호는 양수, 음수를 번갈아 가며 나타난다. 그러므로 집합 n개에 대하여 아래와 같은 공식이 ..