안경잡이개발자

728x90
반응형

  파이썬(Python)에서 Pandas 라이브러리를 제대로 활용하기 위해서는 다양한 연산 방법과 함수에 대해서 알고 있어야 합니다.


※ 데이터 프레임의 NULL 여부 확인 ※


  NULL 여부를 확인할 때는 isnull() 혹은 notnull() 함수를 사용할 수 있습니다. 현실 세계의 다양한 데이터는 존재하지 않는 경우도 있기 때문에 NULL 값에 대한 체크가 필요합니다. 또한 fillna() 함수를 이용해서 NULL 값을 다른 값으로 치환할 수 있습니다.


import numpy as np
import pandas as pd

word_dict = {
    'Apple': '사과',
    'Banana': '바나나',
    'Carrot': '당근',
    'Durian': '두리안'
}

frequency_dict = {
    'Apple': 3,
    'Banana': 5,
    'Carrot': np.nan,
    'Durian': 2
}

importance_dict = {
    'Apple': 3,
    'Banana': 2,
    'Carrot': 1,
    'Durian': 1
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)
importance = pd.Series(importance_dict)

summary = pd.DataFrame({
    'word': word,
    'frequency': frequency,
    'importance': importance
})

print(summary.notnull())
print(summary.isnull())
summary['frequency'] = summary['frequency'].fillna('데이터 없음')
print(summary)


※ Series 자료형의 연산 ※


  Series 자료형은 사칙연산을 수행할 수 있습니다. 이 때 NULL 데이터는 어떻게 처리할지의 여부도 결정할 수 있습니다.


import pandas as pd array1 = pd.Series([1, 2, 3], index=['A', 'B', 'C']) array2 = pd.Series([4, 5, 6], index=['B', 'C', 'D']) array1 = array1.add(array2, fill_value=0) print(array1)


※ Data Frame 자료형의 연산 ※


  Series 자료형을 여러 개 묶은 형태인 Data Frame도 당연히 사칙연산을 수행할 수 있습니다. 저는 2차원 배열 형태를 Data Frame으로 변환하여 연산을 수행해보았습니다. Data Frame 변수인 array1에서는 원래 (0, 2) 위치에 데이터가 존재하지 않았으므로 여전히 NaN으로 처리됩니다. 다만 array1에 더해지는 array2에서 존재하지 않는 데이터는 0으로 치환됩니다.


import pandas as pd

array1 = pd.DataFrame([[1, 2], [3, 4]], index=['A', 'B'])
array2 = pd.DataFrame([[1, 2, 3], [4, 5, 6], [7, 8, 9]], index=['B', 'C', 'D'])

print(array1)
print(array2)

array1 = array1.add(array2, fill_value=0)
print(array1)


※ Data Frame의 집계 함수 ※


import pandas as pd

array1 = pd.DataFrame([[1, 2], [3, 4]], index=['A', 'B'])
array2 = pd.DataFrame([[1, 2, 3], [4, 5, 6], [7, 8, 9]], index=['B', 'C', 'D'])

array1 = array1.add(array2, fill_value=0)
print(array1)
print("컬럼 1의 합:", array1[1].sum())
print(array1.sum())


※ Data Frame의 정렬 함수 ※


  데이터 프레임의 특정한 컬럼으로 정렬을 수행할 수도 있습니다.


import numpy as np import pandas as pd word_dict = { 'Apple': '사과', 'Banana': '바나나', 'Carrot': '당근', 'Durian': '두리안' } frequency_dict = { 'Apple': 3, 'Banana': 5, 'Carrot': 1, 'Durian': 2 } importance_dict = { 'Apple': 3, 'Banana': 2, 'Carrot': 1, 'Durian': 1 } word = pd.Series(word_dict) frequency = pd.Series(frequency_dict) importance = pd.Series(importance_dict) summary = pd.DataFrame({ 'word': word, 'frequency': frequency, 'importance': importance }) summary = summary.sort_values('frequency', ascending=False) print(summary)



728x90
반응형

728x90
반응형

  판다스(Pandas)는 파이썬(Python) 라이브러리 중 하나로서 데이터를 효과적으로 처리하고 보여줄 수 있도록 도와줍니다. 또한 Numpy와 함께 사용되어 다양한 연계 기능을 제공합니다. 판다스의 기본 자료형 중 하나로는 시리즈(Series)가 있습니다. 이는 Numpy 배열과 흡사하지만 인덱스(Index)를 제공한다는 점에서 사전(Dictionary) 자료형에 가깝습니다. 이를 이용해 인덱스로 특정한 데이터에 바로 접근할 수 있습니다.


import pandas as pd array = pd.Series(['사과', '바나나', '당근'], index=['a', 'b', 'c']) print(array['a'])


  사전과 흡사하게 동작한다는 점에서 파이썬(Python)의 사전(Dictionary)를 판다스 객체로 만들 수 있습니다.


import pandas as pd

dict = {
    'a': '사과',
    'b': '바나나',
    'c': '당근'
}

array = pd.Series(dict)
print(array['a'])


※ 데이터 프레임(Data Frame) ※


  데이터 프레임은 Pandas에서 다수의 Series 데이터를 모아 처리하는 목적으로 사용할 수 있습니다. 일반적으로 표 형태로 특정한 데이터를 출력하고자 할 때 간단히 사용할 수 있습니다.


import pandas as pd

word_dict = {
    'Apple': '사과',
    'Banana': '바나나',
    'Carrot': '당근'
}

frequency_dict = {
    'Apple': 3,
    'Banana': 5,
    'Carrot': 7
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)

summary = pd.DataFrame({
    'word': word,
    'frequency': frequency
})

print(summary)


  또한 Pandas도 Numpy와 마찬가지로 연산이 가능합니다.


import pandas as pd

word_dict = {
    'Apple': '사과',
    'Banana': '바나나',
    'Carrot': '당근'
}

frequency_dict = {
    'Apple': 3,
    'Banana': 5,
    'Carrot': 7
}

importance_dict = {
    'Apple': 3,
    'Banana': 2,
    'Carrot': 1
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)
importance = pd.Series(importance_dict)

summary = pd.DataFrame({
    'word': word,
    'frequency': frequency,
    'importance': importance
})

score = summary['frequency'] * summary['importance']
summary['score'] = score

print(summary)


  이러한 판다스 객체는 인덱스를 기준으로 처리하고, 슬라이싱 하는 등의 작업을 수행할 수 있습니다. 슬라이싱을 할 때는 iloc 혹은 loc를 사용할 수 있습니다. iloc는 인덱스를 기준으로 슬라이싱을 처리하도록 도와줍니다.


import pandas as pd

word_dict = {
'Apple': '사과',
'Banana': '바나나',
'Carrot': '당근',
'Durian': '두리안'
}

frequency_dict = {
'Apple': 3,
'Banana': 5,
'Carrot': 7,
'Durian': 2
}

importance_dict = {
'Apple': 3,
'Banana': 2,
'Carrot': 1,
'Durian': 1
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)
importance = pd.Series(importance_dict)

summary = pd.DataFrame({
'word': word,
'frequency': frequency,
'importance': importance
})

print(summary)
print(summary.loc['Banana':'Carrot', 'importance':])
print(summary.iloc[1:3, 2:])


  같은 문법을 활용하여 특정한 데이터를 수정하거나 삽입할 수도 있습니다.


import pandas as pd

word_dict = {
    'Apple': '사과',
    'Banana': '바나나',
    'Carrot': '당근',
    'Durian': '두리안'
}

frequency_dict = {
    'Apple': 3,
    'Banana': 5,
    'Carrot': 7,
    'Durian': 2
}

importance_dict = {
    'Apple': 3,
    'Banana': 2,
    'Carrot': 1,
    'Durian': 1
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)
importance = pd.Series(importance_dict)

summary = pd.DataFrame({
    'word': word,
    'frequency': frequency,
    'importance': importance
})

summary.loc['Apple', 'importance'] = 5 # 데이터의 변경
summary.loc['Elderberry'] = ['엘더베리', 5, 3] # 새 데이터 삽입
print(summary)


※ Pandas를 이용해 엑셀(Excel)로 내보내기/불러오기 ※


  판다스의 내장 함수를 이용하면 엑셀 파일 형태로 내보내거나 불러올 수도 있습니다.


import pandas as pd

word_dict = {
    'Apple': '사과',
    'Banana': '바나나',
    'Carrot': '당근'
}

frequency_dict = {
    'Apple': 3,
    'Banana': 5,
    'Carrot': 7
}

word = pd.Series(word_dict)
frequency = pd.Series(frequency_dict)

summary = pd.DataFrame({
    'word': word,
    'frequency': frequency
})

summary.to_csv("summary.csv", encoding="utf-8-sig")
saved = pd.read_csv("summary.csv", index_col=0)
print(saved)


728x90
반응형

728x90
반응형

  파이썬(Python)의 넘파이(Numpy) 라이브러리에서는 다양한 기본 연산을 지원합니다. 기본적인 사칙연산을 지원하는데, 이러한 연산들은 배열 안에 포함되어 있는 원소에 대한 연산입니다. 예를 들어 배열의 모든 원소의 값에 10을 더하는 등의 작업을 수행할 수 있습니다. 저는 1부터 9까지의 숫자를 랜덤하게 3개만큼 생성하여 각 원소에 10씩 더하도록 프로그래밍을 해보았습니다.


import numpy as np array = np.random.randint(1, 10, size=3) result_array = array + 10 print(result_array[0], result_array[1], result_array[2])


  당연히 곱셈 또한 가능합니다.


import numpy as np array = np.random.randint(1, 10, size=3) result_array = array * 10 print(result_array[0], result_array[1], result_array[2])


  또한 이러한 Numpy의 연산은 Numpy 배열의 형태와 관계 없이 사용할 수 있습니다.


import numpy as np

array = np.random.randint(1, 10, size=4).reshape(2, 2)

result_array = array * 10

print(result_array[0][0], result_array[1][0], result_array[1][1])


※ 서로 다른 형태의 Numpy 연산 ※


  서로 다른 형태를 가진 Numpy 배열 끼리도 연산할 수 있습니다. 이 때는 기본적으로 행우선으로 연산이 이루어집니다.


import numpy as np

array1 = np.arange(4).reshape(2, 2)
array2 = np.arange(2)
array3 = array1 + array2

print(array3[0][0], array3[0][1], array3[1][0], array3[1][1])

  

  서로 다른 형태(Shape이 다를 때)의 Numpy를 연산할 때에는 브로드캐스트(Broadcast)가 적용됩니다. 다시 말해 브로드캐스트란 서로 모양이 다른 배열을 연산할 수 있도록 배열의 형태를 동적으로 변환하는 기법입니다.


  예를 들어


1 2 3

4 5 6

7 8 9



1 2 3을 더하면,


2 4 6

5 7 9

8 10 12


가 됩니다.


array1 = np.arange(1, 10)
array1 = array1.reshape(3, 3)

array2 = np.arange(1, 4)

print(array1 + array2)


  # 브로드캐스트는 최소한 하나의 배열의 차원의 크기가 1일 때 가능합니다.

  # 브로드캐스트는 차원에 대해서 축의 길이가 같을 때 사용이 가능합니다.


  그러므로 1 X 4인 배열과 4 X 1인 배열끼리도 덧셈이 가능한 것입니다. 이 때 자동으로 브로드캐스트가 적용되어 1 X 4는 4 X 4로 확장 되고, 4 X 1 또한 4 X 4로 확장 되어 연산이 이루어진다고 볼 수 있습니다.


import numpy as np

array1 = np.arange(4).reshape(4, 1)
array2 = np.arange(4)
array3 = array1 + array2

print(array3[0][0], array3[0][1], array3[0][2], array3[0][3])
print(array3[1][0], array3[1][1], array3[1][2], array3[1][3])
print(array3[2][0], array3[2][1], array3[2][2], array3[2][3])
print(array3[3][0], array3[3][1], array3[3][2], array3[3][3])


  또한 Numpy는 마스킹 연산도 수행이 가능합니다. 이는 각 원소가 특정한 조건을 만족하는지에 대한 결과가 배열 형태로 반환이 이루어집니다.


import numpy as np

# Numpy 원소의 값을 조건에 따라 바꿀 때는 다음과 같이 합니다.
# 반복문을 이용할 때보다 매우 빠르게 동작합니다.
# 대체로 이미지 처리(Image Processing)에서 자주 활용됩니다.
array1 = np.arange(16).reshape(4, 4)
print(array1)

array2 = array1 < 10
print(array2)

array1[array2] = 100
print(array1)


※ Numpy의 연산 함수 ※


  Numpy는 다양한 기본 함수들을 제공합니다.


import numpy as np

array = np.arange(16).reshape(4, 4)

print("최대값:", np.max(array))
print("최소값:", np.min(array))
print("합계:", np.sum(array))
print("평균값:", np.mean(array))


  가로 축에 대한 집계도 가능합니다.


import numpy as np

array = np.arange(16).reshape(4, 4)

print("합계:", np.sum(array, axis=0))



728x90
반응형

728x90
반응형

  파이썬(Python)에서는 Numpy라는 데이터 분석 전용 라이브러리가 많이 사용됩니다. Numpy는 다차원 배열을 효과적으로 처리할 수 있도록 해주는 다양한 기능을 제공하고 있습니다. 일반적으로 현실 세계에서 다양한 데이터배열 형태의 데이터로 표현할 수 있습니다. 720 X 480 크기의 이미지가 있다고 하면, 이를 720 X 480 배열로 나타낼 수도 있습니다.


  흔히 대부분의 문제는 행렬을 이용해 해결할 수 있다고 말합니다. Numpy는 그러한 행렬을 매우 효과적으로 처리할 수 있도록 도와준다는 특징이 있습니다. 더불어 Numpy는 List와 다르게, 하나의 자료형이 데이터로 들어간다는 특징이 있습니다.


  물론 다차원 배열은 파이썬의 리스트(List) 자료형을 이용해도 어렵지 않게 만들 수 있습니다. 하지만 Numpy를 사용하면 보다 효율적으로 다차원 배열을 사용할 수 있으며, 메모리의 효율성도 리스트보다 앞서게 됩니다. Numpy는 일반적으로 리스트를 입력으로 받아서, Numpy 객체로 처리하여 사용할 수 있도록 해줍니다. 기본적인 Numpy 객체의 사용 방법은 다음과 같습니다.


※ 파이참에서 Numpy 사용하기 ※


  파이참에서 Numpy를 사용하려면 이를 프로젝트 설정에서 등록해주시면 됩니다.



  이후에 인터프리터 설정에서 추가(+) 버튼을 눌러서 라이브러리를 추가해주시면 됩니다.



  Numpy를 검색해서 설치를 진행합니다.



  결과적으로 Numpy를 사용할 수 있게 되었습니다.



※ Numpy 사용해보기 ※


  Numpy 라이브러리는 리스트를 입력으로 받아서 Numpy 객체를 만들 수 있도록 해줍니다.


import numpy as np array = np.array([1, 2, 3]) print(array.size) # 배열의 크기 print(array.dtype) # 배열 원소의 타입 print(array[2]) # 인덱스 2의 원소


※ Numpy로 배열 만들기 ※


  Numpy에서 배열을 순식간에 생성하기 위해서는 arange() 함수를 사용할 수 있습니다. arange() 함수를 이용하면 0부터 특정 인덱스까지의 배열을 생성할 수 있습니다.


import numpy as np

array1 = np.arange(4)
print(array1[3])


※ Numpy 배열 합치기 ※


  concatenate() 함수를 이용하면 여러 배열을 하나로 합칠 수 있습니다.


import numpy as np

array1 = np.array([1, 2, 3])
array2 = np.array([4, 5, 6])
array3 = np.concatenate([array1, array2])

print(array3.shape)


※ Numpy 다양한 형태의 배열 만들기 ※


import numpy as np

array1 = np.zeros((4, 4), dtype=float)
array2 = np.ones((3, 3), dtype=str)
array3 = np.random.randint(0, 10, (3, 3))
# 평균이 0이고 표준편차가 1인 표준 정규를 띄는 값
array4 = np.random.normal(0, 1, (3, 3))
print(array1)
print(array2)
print(array3)
print(array4)


※ Numpy 배열의 형태 바꾸기 ※


  reshape() 함수를 이용하면, 기존 배열의 형태를 바꿀 수 있습니다. 예를 들어서 1차원 배열을 2차원 배열로 바꿀 수 있습니다.


import numpy as np

array1 = np.array([1, 2, 3, 4])
array2 = array1.reshape((2, 2))

print(array2.shape)


※ Numpy 배열을 세로 축으로 합치기 ※


  Numpy 배열은 세로 축으로 합칠 수도 있습니다. 기본적으로 축 값(Axis)이 0이라면 세로 축이고, 1이라면 가로 축입니다.


import numpy as np

array1 = np.arange(4).reshape(1, 4)
array2 = np.arange(8).reshape(2, 4)

array3 = np.concatenate([array1, array2], axis=0)
print(array3.shape)


※ Numpy 배열을 나누기 ※


  Numpy 배열을 나눌 때에는 split() 함수를 사용하며 이는 concatenate() 함수와 흡사하게 동작합니다. 2 X 4 배열을 왼쪽과 오른쪽으로 이등분하는 소스코드는 다음과 같습니다.


import numpy as np

array = np.arange(8).reshape(2, 4)
left, right = np.split(array, [2], axis=1)
print(left.shape)
print(right.shape)
print(right[1][1])


728x90
반응형

728x90
반응형

  이번 시간에는 알고리즘 대회를 위한 C++ 대회 환경구성해보도록 하겠습니다. 가장 먼저, 자신의 디버깅 및 개발을 위한 개발환경을 구축하셔야 합니다. 저는 정말정말 가벼운 개발환경인 Dev C++을 선호하는 편입니다. 따라서 Dev C++을 기준으로 설명드리고자 합니다.


  Dev C++ 설치 경로: https://sourceforge.net/projects/orwelldevcpp/


  Dev C++을 설치하셨으면, 실행 이후에 C++11로 컴파일 옵션 설정을 해주시면 됩니다. C++11에는 알고리즘 대회에 적용하기 쉬운 다양한 라이브러리가 준비되어 있기 때문에 실제로 굉장히 많은 하이 코더들이 이를 사용하고 있습니다. 이를 위해서 'Tools' - 'Compiler Options' 탭으로 이동합니다.



  이후에 다음과 같이 -std=c++11 컴파일 옵션을 적용합시다.


  -std=c++11

  이제 간단히 "Hello World!"를 출력하는 프로그램을 작성해보도록 하겠습니다.



#include <bits/stdc++.h>

using namespace std;

int main(void) {
	cout << "Hello World!";
	return 0;
}

  실행 결과는 다음과 같습니다.



※ #include <bits/stdc++.h>란? ※


  알고리즘 대회에서 가장 많이 사용되는 헤더 파일 중 하나가 바로 bits/stdc++.h입니다. 표준 라이브러리를 모두 포함하고 있는 헤더로서 이것을 사용하면 별도의 헤더를 추가적으로 넣지 않아도 됩니다. 다만 이 헤더는 GCC 전용 라이브러리이므로 GCC를 지원하는 대회 환경에서 사용해야 합니다. 다행히도 대부분의 대회 환경에서는 이를 지원합니다.


  이 헤더에 포함되어 있는 대표적인 라이브러리들은 다음과 같습니다.


  - #include <string>

  - #include <vector>

  - #include <memory>
  - #include <map>

  - #include <algorithm>

  - #include <queue>


  이외에도 정말 많이 사용되는 라이브러리들이 모두 포함되어 있으므로 시간 절약 및 숏코딩 측면에서 매우 유리하다고 할 수 있습니다. 한 번 벡터(Vector) 라이브러리를 이용해서 N개의 원소를 저장하여 출력하는 프로그램을 작성해보도록 합시다.

#include <bits/stdc++.h> using namespace std; int main(void) { int n; cin >> n; vector<int> a;

for(int i = 0; i < n; i++) { a.push_back(i); } for(int i = 0; i < n; i++) { cout << a[i] << ' '; } return 0; }


  실행 결과는 다음과 같습니다.




728x90
반응형

728x90
반응형

  코드포스 공식 사이트: https://codeforces.com/


  코드포스는 세계에서 가장 유명한 알고리즘 대회 사이트 중 하나입니다. 일반적으로 매 주마다 1회 이상의 대회가 열리며, 대회에 참여해서 문제를 풀면 자신의 성적에 따라서 레이팅(Rating)을 판정 받을 수 있습니다. 코드포스에 가입한 이후에 메인 화면(Home)으로 가보면 다음과 같이 다가 올 대회에 대한 정보가 오른쪽에 출력되며, 위쪽 내비게이션 바에서 대회 목록(Contests)에 들어가서 대회 정보를 확인할 수 있어요.



  대회 목록 페이지로 이동하면 다음과 같은 화면이 나옵니다. 위쪽에는 향후 다가올 대회에 대한 정보가 출력되고, 아래 쪽에는 최근까지 진행되었던 대회 정보가 출력됩니다.



  이 중에서 하나의 대회에 들어가서 확인해보도록 합시다. 그러면 다음과 같이 문제 목록이 출력되는 것을 확인할 수 있습니다. 이 중에서 원하는 문제를 선택해 문제를 풀 수 있습니다. 코드포스는 문제의 난이도가 쉬운 것부터 어려운 것 순서대로 나열되어 있다는 특징이 있습니다.



  특정한 문제를 선택해 들어가 보면 다음과 같은 형태로 문제에 대한 내용이 출력됩니다. 우리는 'SUBMIT CODE'를 눌러서 소스코드를 실제로 제출할 수 있고, 그에 대한 정답 확인은 'MY SUBMISSIONS' 탭에서 확인할 수 있습니다.



  또한 문제의 유형이나 점수 등에 대한 정보 [Problem Tags] 영역에서 확인할 수 있습니다. 이는 실제 대회가 진행되는 중에는 확인할 수 없고, 대회가 끝나고 나면 출제자의 의도 등을 확인할 수 있는 탭이에요. 또한 코드포스는 튜토리얼(Tutorial) 등에 대한 내용도 함께 제시됩니다. 완전히 정답 소스코드를 제공하는 것은 아니지만, 충분히 이해할 수 있는 수준에서의 해법을 알려준다는 특징이 있습니다.



  결과적으로 '코드 제출(SUBMIT CODE)' 버튼을 누르면 다음과 같이 코드를 제출할 수 있는 화면으로 넘어갑니다.



  소스코드를 제출한 이후에는 '나의 제출(MY SUBMISSIONS)' 탭에서 자신의 정답 여부를 확인할 수 있습니다. 코드포스는 정답이 틀린 경우, 정확히 어떠한 테스트(Test)에서 정답이 틀렸는지까지 알려준다는 특징이 있습니다. 물론 대회가 진행 중일 때는 알려주지 않지만요.



  또한 '순위(STANDINGS)' 탭에 가시면 다음과 같이 실시간으로 대회에 참여했던 참가자들의 순위 정보가 출력됩니다.



728x90
반응형

728x90
반응형

문제 유형: 정수론

문제 URL: https://codeforces.com/contest/1055/problem/C


  앨리스(Alice)와 밥(Bob)은 모두 각각 일정한 컨디션 주기가 있습니다. 운이 좋은(Lucky) 날이 몇 일 계속된 이후에, 그 이후에는 운이 나쁜(Unlucky) 날이 몇 일간 계속되는 방식입니다. 이 때 앨리스와 밥이 둘 다 운이 좋은(Lucky) 날이 최대 몇 일 겹칠 수 있는지를 구하면 되는 문제입니다.


  예를 들어 앨리스는 0일부터 2일까지 운이 좋고, 주기가 5라고 가정합시다. 또한 밥은 1일부터 3일까지 운이 좋고, 주기가 5라고 가정합시다. 이 때 운이 좋은 날을 1로, 운이 나쁜 날을 0으로 표현하면 다음과 같습니다. 둘 다 운이 좋은 날은 최대 2일이군요.


  0 1 2 3 4 5 6 7 8 9

  1 1 1 0 0 1 1 1 0 0

  0 1 1 1 0 0 1 1 1 0


  이 문제는 날짜가 0일부터 10억 일까지 입력될 수 있다는 점에서 사실상 상수 시간 안에 답을 도출할 수 있는 알고리즘이 필요합니다. 이는 '특정 주기'로 반복된다는 점에서 조금만 생각해보면 쉽게 구할 수 있습니다.


  바로 앨리스의 주기와 밥의 주기의 최대 공약수(GCD)를 구하는 것입니다. 최대 공약수를 기준으로 앨리스 혹은 밥의 주기를 '슬라이딩'하여 운이 좋은 날이 최대 얼마나 겹치는지 확인할 수 있기 때문이죠. 예를 들어 최대 공약수가 3이 나왔다면, 앨리스 혹은 밥의 컨디션 주기를 3만큼 시프트(Shift) 할 수 있는 것입니다. 왼쪽 혹은 오른쪽으로요. 


  따라서 전체 4가지 경우만 고려하면 돼요.


  1) 좋은 운이 시작되는 날이 A가 B에 비해 먼저 있을 때

  1-1) A가 B의 최대한 왼쪽에 붙는 경우를 계산하기.

  1-2) A가 B의 최대한 오른쪽에 붙는 경우를 계산하기.


  2) 좋은 운이 시작되는 날이 B가 A에 비해 먼저 있을 때

  2-1) B가 A의 최대한 왼쪽에 붙는 경우를 계산하기.

  2-2) B가 A의 최대한 오른쪽에 붙는 경우를 계산하기.


  위 4가지 경우를 모두 고려하여 최대한 많이 겹칠 수 있는 일자를 구하면 됩니다. 따라서 유클리드 알고리즘을 이용하여 사실상 상수에 가까울 정도로 빠른 속도로 답을 도출할 수 있는 것입니다.


※ 입출력 예시 ※

input
Copy
0 2 5
1 3 5
output
Copy
2
input
Copy
0 1 3
2 3 6
output
Copy
1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>

#include <limits.h>


using namespace std;


int gcd(int a, int b) {

if(a == 0)

return b;

return gcd(b % a, a);

}


int main(void) {

int la, ra, ta, lb, rb, tb;

cin >> la >> ra >> ta >> lb >> rb >> tb;

int pat = gcd(ta, tb);

int res = 0;

int gap = abs(la - lb) / pat;

// a가 b보다 더 앞에 있을 때 

if(la < lb) {

int temp = la + pat * gap; // a가 b의 최대한 왼쪽에 붙는 경우 

res = max(res, (temp + 1 + (ra - la)) - lb); 

temp = la + pat * (gap + 1); // a가 b의 최대한 오른쪽에 붙는 경우 

res = max(res, (1 + rb) - temp); 

}

// b가 a보다 더 앞에 있을 때

else {

int temp = lb + pat * gap; // b가 a의 최대한 왼쪽에 붙는 경우

res = max(res, (temp + 1 + (rb - lb)) - la); 

temp = lb + pat * (gap + 1); // b가 a의 최대한 오른쪽에 붙는 경우 

res = max(res, (1 + ra) - temp);

}

// 두 사람의 운이 좋은 날이 계속되는 길이보다 커질 수는 없음 

res = min(res, rb - lb + 1);

res = min(res, ra - la + 1);

cout << res;

return 0;

}


728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1055/problem/B


  앨리스(Alice)의 머리카락들이 계속 자라고 있습니다. 앨리스는 그래서 미용사에게 찾아갔습니다. 앨리스는 모든 머리카락이 최대 l 센티미터(Centimeter)가 될 수 있도록 머리를 자르고 싶습니다. 앨리스의 머리카락 개수는 N개이며, 각 머리카락을 1번부터 N번까지의 번호로 다룬다고 합시다.


  미용사가 가위를 이용해 한 번 머리카락을 자르면, 미용사는 길이가 l보다 큰 머리카락의 길이를 l이 되도록 만들 수 있습니다. 이 때 머리카락은 1번부터 N번까지 차례대로 위치하며 가위로 서로 인접한 머리카락들을 한 번에 자를 수 있습니다. 미용사는 가능한 빠르게 앨리스의 머리를 손질하고 싶습니다. 미용사가 가위질을 할 때마다 1초가 소요된다고 가정했을 때, 앨리스의 머리를 손질하는 최소 시간을 구하면 되는 문제입니다.


  또한 앨리스는 미용사에게 언제 갈 지를 정확히 결정하지 않았기 때문에, 특정한 시각에 자신의 머리카락의 길이를 미용사에게 알려주면서 머리 손질 시간을 물어보고자 합니다. 이 때 정확히 두 가지 유형의 쿼리(Query)가 있습니다.


  0) 앨리스가 지금 미용사에게 가면 머리를 손질하는데 얼마나 시간이 걸릴 지 물어보는 쿼리입니다.

  1) P와 D가 이어서 입력되며, P번째 머리카락이 D 센티미터만큼 자랐다는 의미를 가지는 쿼리입니다.


  기본적으로 앨리스가 원하는 머리카락 최대 길이인 l은 프로그램이 끝날 때까지 동일한 값을 가진다고 보면 됩니다.


  이 문제는 대표적인 구현 문제 유형이라고 볼 수 있습니다. 또한 인접한 머리카락들을 잘 살펴보는 것이 중요합니다. 그러므로 일단 맨 처음에 주어진 초기 상태를 보고 머리카락을 몇 번 잘라야 하는지를 검사합니다. 이후에 특정한 위치의 머리카락이 길어질 때마다 그 왼쪽과 오른쪽에 있는 머리카락과의 관계를 확인하여, 가위질 횟수가 증가할 지 혹은 감소할 지를 판단하면 됩니다.


  총 9가지 경우의 수만 고려하면 돼요. 머리카락이 l보다 작다가, l보다 길어진 특정한 머리카락의 위치를 (K), 왼쪽과 오른쪽에 있는 머리카락이 각각 길다면 (긴), 짧다면 (짧)이라고 합시다. 또한 머리카락 중에서 K가 가장 왼쪽 혹은 오른쪽에 위치할 때, 끝 부분은 (끝)이라고 합시다.


  1) 짧K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  2) 짧K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  3) 긴K짧: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  4) 긴K긴: 왼쪽과 오른쪽 가위질에 모두 포함될 수 있으므로 가위질 횟수 1 감소

  5) 끝K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  6) 끝K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  7) 짧K끝: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  8) 긴K끝: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  9) 끝K끝: 원소가 1개인 경우이므로 가위질 횟수 1 증가


  위 9가지 경우의 수를 고려하여 전체 가위질 최소 횟수를 구하는 프로그램을 작성하면 됩니다.


※ 입출력 예시 ※

input
Copy
4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0
output
Copy
1
2
2
1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0) 

#include <iostream>

using namespace std; long long a[100001]; long long n, m, l; int main(void) { cin >> n >> m >> l; int res = 0; cin >> a[0]; if(a[0] > l) { res++; } for(int i = 1; i < n; i++) { cin >> a[i]; // 초기 상태에서 가위질 횟수를 구합니다. if(a[i] > l) { if(a[i - 1] <= l) { res++; } } } for(int i = 0; i < m; i++) { int oper; cin >> oper; if(oper == 0) { cout << res << '\n'; } else { int x, length; cin >> x >> length; int count = 0; // 머리카락이 l보다 짧았다가, l보다 길어져서 '자를 머리카락'이 되는 경우 if(a[x - 1] <= l && a[x - 1] + length > l) { bool find = false; // 원소가 1개인 경우를 체크하기 위한 목적 if(x - 2 >= 0) { // 왼쪽 머리카락 확인 if(a[x - 2] <= l) count++; // (짧) else count--; // (긴) find = true; } if(x < n) { // 오른쪽 머리카락 확인 if(a[x] <= l) count++; // (짧) else count--; // (긴) find = true; } if(!find) res++; } if(count >= 1) res++; else if(count == -2) res--; a[x - 1] += length; } } return 0; }


728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1055/problem/A


  일직선 형태로 존재하는 지하철 노선이 있다고 합니다. 노선에는 1부터 N까지 번호가 매겨진 N개의 역이 있습니다. 이 때 밥(Bob)은 1번 역에 살고 있으며, 엘리스(Alice)는 S번 역 근처에 살고 있습니다.


  지하철 노선은 두 개의 트랙으로 구성됩니다. 첫 번째 트랙에서는 열차가 역 1에서 역 N으로 이동합니다. 두 번째 트랙에서의 열차는 N부터 1까지 반대 방향으로 이동합니다. 또한 기차는 트랙의 끝에 도달한 순간 운행을 정지한다고 가정합니다.


  다만 일부 역에서는 열차가 멈출 수 없는 상황이라고 합니다. 그러므로 몇몇 역은 열차가 그냥 통과하여 지나간다고 가정합니다. 이러한 상황에서 밥(Bob)에게 각 역에 대해서 열차가 멈출 수 있는지, 없는지의 여부가 알려져 있다고 했을 때 밥이 엘리스의 집으로 갈 수 있는지를 출력하면 됩니다.


  예를 들어 역이 5개이고, 엘리스가 4번 역 근처에 살고 있다고 해봅시다. 이 때 두 개의 트랙에서 열차가 멈출 수 있는 역들은 1로, 멈출 수 없는 역들을 0으로 표현할 때 다음과 같다고 가정합시다.


  첫 번째 트랙: 1 0 0 0 1

  두 번째 트랙: 0 1 1 1 1


  이 때는 밥이 출발지인 1번 역에서 5번 역으로 이동한 뒤에, 5번 역에서 두 번째 트랙을 타고 4번 역으로 이동하여 엘리스의 집에 도착할 수 있습니다.


  이 문제는 정말 간단한 구현 문제입니다. 밥이 항상 1번 역에서 출발한다는 점을 기억하면 됩니다. 그래서 만약 1번 역이 운행되지 않는 상태라면 그 즉시 도달할 수 없음을 알리고 종료하면 됩니다. 이후에는 각 역을 하나씩 확인하며, 첫 번째 트랙에서 운행되는 역일 때만 특정한 조건을 검사하면 됩니다. 여기서 조건은 바로 해당 역이 엘리스가 있는 역인지 혹은 두 번째 트랙으로 이동하여 반대 방향으로 이동하여 엘리스가 있는 역으로 갈 수 있는지를 의미합니다.


  따라서 간단한 난이도의 단순 구현 문제라고 볼 수 있습니다.


※ 입출력 예시 ※

input
Copy
5 3
1 1 1 1 1
1 1 1 1 1
output
Copy
YES
input
Copy
5 4
1 0 0 0 1
0 1 1 1 1
output
Copy
YES
input
Copy
5 2
0 1 1 1 1
1 1 1 1 1
output
Copy
NO

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream> using namespace std; int a[1001]; int b[1001]; int main(void) { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { cin >> b[i]; } if(a[1] == 0) { cout << "NO"; return 0; } for(int i = 1; i <= n; i++) { if(a[i] == 1) { if(i == m || (b[i] == 1 && b[m] == 1 && m < i)) { cout << "YES"; return 0; } } } cout << "NO"; return 0; }


728x90
반응형

728x90
반응형

문제 유형: 그리디

문제 URL: https://codeforces.com/contest/1075/problem/C


  문제를 간단히 요약하자면 다음과 같습니다.


  높이고 10^9이고, 너비가 10^9인 체스판이 있습니다. 이 때 가장 왼쪽 아래인 (1, 1)의 위치에 하나의 돌이 있습니다. 얘는 마차(Look)라서 이동할 때 상하좌우로 쭉쭉 이동할 수 있습니다. 이 돌은 체스판의 가장 위쪽에 도달하고자 합니다. y 좌표 상으로 10^9의 위치에 닿으면 되는 것이며 x 좌표는 어떤 값이 들어가도 상관 없습니다. 좌표를 나타낼 때는 (열, 행)과 같은 방식으로 표현합니다.


  이 때 체스판을 가로 막는 다양한 선들이 있다고 합니다. 선의 종류로는 수직선과 수평선이 있습니다.


  1) 수직선: 특정한 x 위치에서 수직으로 끝 없이 이어진 선입니다.

  2) 수평선: x1부터 x2까지의 열을 차지하는 선으로, 행 y에 위치합니다.


  수평선들은 수직 관계에 있는 다른 선들과는 x 좌표가 겹쳐도 됩니다. 하지만 수평한 수평선끼리는 x 좌표가 겹치지 않는다고 합니다. (1, 1)에 위치한 돌은 y 좌표 상으로 10^9의 위치에 닿을 때까지 이동할 수 있는데, 체스판에 있는 선들을 뚫고 나아갈 수 없다고 합니다. 따라서 선으로 가로 막힌 경우 선을 지우고 나아가야 합니다. 체스판의 가장 위쪽까지 도달하도록 선을 삭제할 때 최소한의 삭제할 선 개수를 구하면 됩니다.


※ 핵심 풀이 ※


  이 문제는 두 개의 사실만을 깨달으면 쉽게 풀 수 있고, 깨닫지 못하면 푸는 것이 굉장히 어렵습니다.


  ▶ 그것은 바로 수평선 중에서 왼쪽 x 좌표가 1이 아닌 것은 무시해도 된다는 것입니다.

  ▶ 그로 인해 수평선의 y 좌표는 신경 쓸 필요가 없다는 것까지 유추하면 됩니다.


  수평선의 왼쪽 x 좌표가 1이 아닌 것은 무시해도 좋은 이유를 설명해드리겠습니다. 이것은 '수평한 수평선끼리는 x 좌표가 겹치지 않는다'는 성질 때문에 가능한 것입니다.


  다음과 같은 경우를 생각해봅시다.



  몇 개의 선을 삭제해야 제일 위 칸으로 이동할 수 있을까요?


  정답은 바로 1개의 선입니다.



  위와 같이 중간에 있는 선을 지워버리면, 지그재그로 이동하여 제일 위 칸까지 이동할 수 있거든요. 결과적으로 왼쪽 x 좌표가 1인 수평선이 아니면 사실상 전혀 의미 없는 수평선이라고 할 수 있습니다. 돌 입장에서는 왼쪽 끝까지 편하게 이동할 수 있으니까요.



  결과적으로 기존의 시작할 때의 상태는 왼쪽 x 좌표가 1이 아닌 수평선들은 모두 지워버린 위 그림과 같은 상태와 같다고 볼 수 있습니다. 이렇게 정리된 상태에서 보니 한 가지 더 알게 되는 점이 있습니다. 그것은 바로 y 좌표는 굳이 신경 쓸 필요가 없다는 것입니다. 왜냐하면 어차피 하나의 y 좌표에는 최대 1개의 수평선만이 존재할 수 있을 테니까요. y 좌표는 고려 할 필요가 없습니다.


  이러한 원리를 이용하여, 각 수직선을 왼쪽부터 차례대로 확인하며 위를 덮는 수평선의 개수를 고려하여 정답을 도출하면 됩니다.


※ 예시 입출력 ※


input
Copy
2 3
6
8
1 5 6
1 9 4
2 4 2
output
Copy
1
input
Copy
1 3
4
1 5 3
1 9 4
4 6 6
output
Copy
1
input
Copy
0 2
1 1000000000 4
1 1000000000 2
output
Copy
2
input
Copy
0 0
output
Copy
0
input
Copy
2 3
4
6
1 4 3
1 5 2
1 6 5
output
Copy
2


※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include 
#include 
#define MAX 100001

using namespace std;

int vertical[MAX], line[MAX];
int INF = 1e9;

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> vertical[i];
	vertical[n++] = INF;
	sort(vertical, vertical + n);
	int lineCount = 0;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; 
		if (a != 1) // 왼쪽 x 좌표가 1인 수평선은 무시
			continue;
		line[lineCount++] = b;
	}
	sort(line, line + lineCount);
	int res = lineCount; // 시작 위치에서 돌이 위쪽으로만 뚫고 이동하는 경우를 초기 값으로 설정 
	int j = 0;
	// 각 수직선을 왼쪽부터 하나씩 확인하며 
	for(int i = 0; i < n; i++) {
		// 각 수직선을 덮는 수평선들의 개수를 세기 
		while (j < lineCount && line[j] < vertical[i]) {
			j++;
		}
		res = min(res, i + lineCount - j);
	}
	cout << res;
	return 0;
}


728x90
반응형