자료 구조 (13) 썸네일형 리스트형 [Python] 2036번 수열의 점수 / 1744번 수 묶기 https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 22/11/20 / 22/11/23 두 문제는 $N$의 크기만 다르고 솔루션이 완전히.. [Python] 25918번 북극곰은 괄호를 찢어 https://www.acmicpc.net/problem/25918 25918번: 북극곰은 괄호를 찢어 극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$와 $X$를 보면 $()$와 $)($로 찢어버린다는 것이다. 협이는 이러한 북극곰의 특성을 이용하여 길이 $N www.acmicpc.net 22/11/07 에디토리얼에서는 그리디 문제라고 나와있었으나, 조금 스택을 곁들인 애드 혹 스러운 문제로, 쉬운 방법으로 구현할 수 있는 문제이다. 문제 접근 방식: 카운터 변수를 하나 선언을 해주고 괄호 문자열에서 (가 나오면 그 변수에 1을 더하고 )가 나오면 1을 뺐다. 북극곰은 항상 () 또는 )(처럼 열린 괄호와 닫힌 괄호를 쌍으로 생성하기 때문에, 북극곰이 생성.. [Python] 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 22/10/09 스택을 이용해서 푸는 문제로, 괄호 문자열 문제를 풀었다면 응용해서 풀 수 있는 문제이다.(유사한 유형임) 문제 접근 방식: 괄호 문자열이 옳은지 그른지 판단하는 문제와 동일하지만, 차이점은 괄호 문자열은 시작과 끝이 정해져 있지만 이 문제 같은 경우는 시작과 끝이 괄호 문자열처럼 명확하지 않다는 것이다. 나는 괄호 문자열의 풀이에서 힌트를 얻어, 스택에 문자들을 계속 쌓다가 현재 문자가 스.. [Python] 20040번 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 22/10/01 사이클을 만들 수 있는지의 여부와, 만들 수 있다면 처음 사이클이 만들어졌을 때의 차례를 출력하는 문제로, 유니온-파인드 알고리즘을 활용하여 쉽게 풀 수 있는 문제이다. 만약 유니온-파인드 함수나 분리집합 자료 구조에 관해서 잘 모르는 상황이라면 공부를 먼저 하고 이 글을 보면 도움이 될 것이다. 문제 접근 방식: 이 문제에서 사이클이 만들어 진다는 뜻은, 이미 같은 선분으로.. [Python] 3108번 로고 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 22/09/22 유니온-파인드(분리 집합)와 두 직사각형이 만나는 함수를 섞으면 쉽게 풀 수 있는 문제이다. 유니온-파인드의 기본 난이도가 골드 5인데, 이 문제에서 유니온-파인드를 사용해야 된다는 점을 캐치하는 것, 그리고 두 직사각형이 만나는 함수를 구현하는 난이도, 그리고 약간의 예외처리를 고려하자면 저 난이도는 굉장히 적절한 난이도라고 생각한다. 문제 접근 방식: PU명령은 펜을 떼라는 명령이다. 이 .. 이전 1 2 다음