최소 길이의 실만 사용해서 구슬을 원형으로 배열하는 놀라운 방법

1. 문제 25707번: 팔찌 만들기 (acmicpc.net) 25707번: 팔찌 만들기 N개의 구슬을 모두 사용하여 조건에 맞게 팔찌를 만들 때 사용하는 줄의 길이의 최솟값을 출력한다. www.acmicpc.net 2. 풀이 서로 인접하는 구슬 사이 차이가 최소가 된다면 전체 줄의 길이가 최소가 될 것 같다 구슬의 크기를 담은 리스트를 오름차순 정렬하면 서로 인접하는 값들의 차이가 최소가 될 것 0번 1번 차이 1번 2번 차이 2번 3번 차이 ... n-2번 n-1번 차이들의 합에 원형으로 배열하니까 마지막 n-1번과 0번의 차이도 구해서 더해주면 될 것 from sys import stdin n = int(stdin.readline()) ball = list(map(int,stdin.readline(..

• format_list_bulleted 애드 혹 알고리즘
• · 2023. 2. 4.
• textsms

union find 재활훈련 - union by size 복기하기

1. 문제1 4143번: Bridges and Tunnels (acmicpc.net) 4143번: Bridges and Tunnels The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 100,000. We assume that al www.acmicpc.net 2. 풀이1 서로 연결되는 간선이 주어질때마다 각 노드의 집합 크기를 구하는 문제 find..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 1. 31.
• textsms

게임이론 배우기 -소수 부르기 게임-

1. 문제 25632번: 소수 부르기 게임 (acmicpc.net) 25632번: 소수 부르기 게임 용태가 부를 수 있는 소수는 $11, 13, 17$이고, 유진이가 부를 수 있는 소수는 $13, 17, 19$이다. 둘 다 최선을 다해서 플레이한다면 $13 → 17 → 11 → 19$로 진행될 수 있다. 용태가 더 이상 부를 소수가 www.acmicpc.net 2. 풀이1 두 플레이어가 주어진 범위 a,b와 c,d에서 각각 소수를 찾는다 만약 승리를 위해 최선을 다해서 플레이한다면, 어떻게 해야 할까 핵심 규칙은 이미 부른 소수는 부르지 못한다는 것이다 그러므로 상대가 가지고 있는 소수를 내가 먼저 부른다면, 상대가 가지고 있는 소수를 부르지 못하게 하면서 동시에 나는 턴을 넘기므로 매우 유리해진다 따라..

• format_list_bulleted 게임이론
• · 2023. 1. 30.
• textsms

문자열 정렬할 때 실수하기 쉬운부분 복기하기 -줄서기-

1. 문제 17178번: 줄서기 (acmicpc.net) 17178번: 줄서기 아이즈원의 팬인 시온이는 드디어 티켓팅에 성공하여 콘서트를 갔다. 콘서트장에 일찍 도착한 시온이는 기대하며 입장을 위해 줄을 섰다. 하지만 아이즈원의 인기대로 시온이를 포함한 많은 www.acmicpc.net 2. 풀이 문제를 읽어보면서 구조를 잘 생각해보면.. n개의 줄에 다섯명씩 있는데 앞 사람부터 입구에 입장을 할건데 티켓 순서대로 입장을 수행한다 근데 티켓 순서는 알파벳이 사전 순서대로, 그리고 숫자가 작은 순서대로가 먼저 오는것이다 입장을 하는데 내 순서가 아니면 대기줄에서 들어갈 순서가 맞는 사람인지 검사해서 들어갈 사람이면 보내주고 그래도 들어갈 사람이 없으면 현재 대기줄이 아닌 사람은 대기공간에 들어가야할 것이다..

• format_list_bulleted 구현,시뮬레이션
• · 2023. 1. 29.
• textsms

스택 테크닉 익히기1 -문자열 폭발

1. 문제 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 2. 풀이1 주어진 첫번째 문자열에서 제시된 두번째 문자열을 모두 지우고 합친다음에, 또 두번째 문자열이 존재한다면 지우고 합쳐서... 이를 반복해서 더이상 지울 문자열이 존재하지 않으면 그것을 출력하면 되는 간단한 문제 단순히 replace 함수를 사용하면 그냥 시간초과다 replace 함수가 O(N)보다 조금 더 걸린다고 함 from sys import stdin s1 = stdin...

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 1. 29.
• textsms

브루트포스의 기본은 슬라이딩 윈도우(sliding window)

1. 문제 1120번: 문자열 (acmicpc.net) 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 2. 풀이 생각보다 어렵다... 첫번째 문자열에 앞에 알파벳 넣어보고... 혹은 뒤에 알파벳 넣어보고... 두번째 문자열과 길이가 같아질때 비교해서 서로 다른 문자의 개수 세보고... 그러면 26개 알파벳 리스트 만들어서 중복조합으로 길이 차이만큼 뽑아서 앞 뒤로 넣어보고 비교해보나..?? 두 문자열 길이의 차이가 k이면.. k개 모두 임의의 알파벳 26개 앞에 넣어보..

• format_list_bulleted 슬라이딩 윈도우
• · 2023. 1. 28.
• textsms