문자열 그리디 연습1 - 최소 횟수로 교환해서 두 문자열 같게 만들기

1. 문제 13413번: 오셀로 재배치 (acmicpc.net) 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 2. 풀이1 문자열의 문자를 바꾸는 방법이 2가지 1) B는 W로, W는 B로 뒤집기 2) 서로 다른 두 위치의 문자를 교환하기 이런 상황에서 두 문자열이 서로 같게 만드는, 최소 횟수로 교환하는 방법을 찾을려면? 탐욕적으로 생각해보면 생각보다 간단한 문제다 두 문자열을 처음부터 동시에 순회해서, 두 문자가 서로 같다면 그대로 넘어가면 될거고 두 문자가 서로 다른 순간에 교환을 해야할거임 0번째는 W와..

• format_list_bulleted 그리디 알고리즘
• · 2023. 5. 16.
• textsms

알고리즘 문제 해결(PS)을 위한 게임이론 기초지식 - 님 게임(Nim game) 배우기

1. 님 게임(Nim game) 게임이론에서 가장 중요한 게임 형태중 한가지라고 할 수 있다. ""수학적 전략 게임으로, 여러 개의 돌 무더기가 있다고 가정하자. 두 사람이 서로 차례를 번갈아가며 게임을 한다. 자신의 차례에 하나의 돌 무더기를 선택하고, 1개이상의 원하는 만큼의 돌을 제거한다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다."" 2. 게임의 수학적 기술 현재 시점에 n개의 돌 무더기에 있는 돌의 개수가 $x_{1}, x_{2}, ... , x_{n}$이라고 하자. 내가 어떤 돌 무더기를 하나를 선택하여 돌을 가져가고 나서 변화된 돌의 개수는 $y_{1}, y_{2}, ... , y_{n}$이라고 하자. 만약 k번째의 돌 무더기를 선택하고 돌을 가져갔다면.. 돌의 개수는 줄어드니까 ..

• format_list_bulleted 게임이론
• · 2023. 5. 15.
• textsms

C++ 알고리즘 기초9 -사칙연산 배우기-

1. 사칙연산 C++에서 사용되는 사칙연산 덧셈, 뺄셈, 곱셈, 나눗셈은 각각 +,-,*,/으로 구할 수 있다. #include using namespace std; int main() { int a = 9, b = 4; cout

• format_list_bulleted C++ 기초
• · 2023. 5. 14.
• textsms

시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

1. 문제 19947번: 투자의 귀재 배주형 (acmicpc.net) 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 2. 풀이 아주 기본적인? 다이나믹 프로그래밍.. 근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정 dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고 dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서.. 1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데 이거 어떻게 하더라... 잠깐 정적.. ------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 5. 10.
• textsms

세그먼트 트리 응용단계 - 이분탐색과 콜라보1

1. 문제 1321번: 군인 (acmicpc.net) 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 2. 풀이 문제를 잘 읽어보면 어떻게 풀어야할지 대충 보인다 군인은 군번대로 1번부대부터 차례대로 배치되고, 부대가 4, 3, 7 이렇게 있을때, 군번이 6번인 군인은 2번부대에 배치된다.. 왜냐하면 1번부대에 4번까지 배치하고 5번,6번 군인은 2번 부대에 배치되니까 그런데 부대의 인원이 줄어들거나 늘어날수 있고 그럴때 군인들이 처음부터 다시 배치한다는 것이다 이거는 이제 세그먼트 트리의 업데..

• format_list_bulleted 세그먼트 트리
• · 2023. 5. 9.
• textsms

숫자를 안만들고 나머지를 구하는 방법, 문자열 연산 없이 두 수를 붙이는 방법

1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..

• format_list_bulleted 정수론
• · 2023. 5. 8.
• textsms