본문 바로가기

자료구조

 (8)
[Python] 10216번 Count Circle Groups https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 22/09/20 전형적인 분리 집합 문제로, 분리 집합에 대한 내용만 잘 알고 있다면 쉽게 풀 수 있는 문제이다. 만약 분리집합을 모른다면 조금 푸는데 힘들 것이다. 문제 접근 방식: 문제에서는 통신영역이 서로 닿거나 겹치면 통신이 가능하다고 보는데, 여러 다리를 거쳐서 통신이 되는 것도 통신이 가능하다고 간주하였다. 때문에 이 정보를 보고 바로 분리 집합에 관련된 문제이겠구나..
[Python] 17413번 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 22/09/14 조금 귀찮았던 문자열 문제로, 스택을 이용하여 문제를 접근했다. 문제 접근 방식: 문제 자체는 간단하다. 공백을 기준으로 단어가 정해지는데, 원래 문자열이 주어지면 단어만 전부 뒤집어서 출력해주는 문제이다. 나는 뒤집는다는 점에 주목하여 문자 하나하나를 스택에 담다가 공백을 만나면 그 스택을 뒤집어서 전부 출력하는 것으로 접근했다. 하지만 여기에서 ..
[Python] 1927번 최소 힙 / 11279번 최대 힙 / 11286번 절댓값 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net https://www.acmicpc.net/pr..
[Python] 1544번 사이클 단어 https://www.acmicpc.net/problem/1544 1544번: 사이클 단어 사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 www.acmicpc.net 22/09/11 그룹 제출 현황에 있는 문제를 아무 문제나 무작위로 한 문제 골라서 풀었다. 문제 접근 방식: 원형으로 쓴다는 아이디어에서 착안하여 덱 자료구조를 떠올렸다. 파이썬의 deque은 rotate라는 메서드가 존재하기 때문에 이 메서드를 활용하면 될 것이라고 생각했다. 구현은 다음과 같이 진행했다. 새로운 단어가 나오면 cycle_word라는 리스트에 그 새로운 단어를 원형으로 써서 읽힐..
[Python] 1270번 전쟁 - 땅따먹기 1270번: 전쟁 - 땅따먹기 (acmicpc.net) 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n
[Python] 4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 22/08/28 마찬가지로 클래스 2++ 문제 중 안 푼 문제가 있길래 풀어본 문제이다. 전형적인 스택을 사용한 응용문제이며, 괄호 문자열에 대한 개념을 알고 있었으면 더 쉽게 푸는 문제이다. 접근 방법: 문제에서 주어진 대로 접근했다. 이제 괄호 스택을 하나 만드는데, '(' 나 '['가 나올 때마다 괄호 스택에 차곡차곡 그 괄호들을 넣어준다. 마찬가지로, ')' 나 ']'..
[Python] 1874번 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 22/08/28 마찬가지로 클래스 2++에 해당하는 문제 중 풀지 않은 문제가 있어서 풀은 문제이다. 문제 풀이 자체는 그렇게 마구 어렵다거나 그러지는 않는데 문제 해석이 조금 난감했던 문제이다.(내 국어 능력이 부족한 탓 일 수도 있다.) 하지만, 여러 번 틀렸다거나 그러지는 않았고 한 번에 맞았다. 지금 되돌아 ..
[Python] 2013번 선그리기 https://www.acmicpc.net/problem/2013 2013번: 선그리기 첫째 줄에 선분의 개수 N(1 p2[0]: return p1 elif p1[0] = p2[1]: return p1 else: return p2 def point_swap(p1, p2): if point_compare(p1, p2) == p1: return p2, p1 else: return p1, p2 def line_swap(p1, p2, p3, p4): if point_compare(p1, p3) == p1: return p3, p4, p1, p2 else: return p1, p2, p3, p4 def can_draw_once(line1, line2)..

티스토리툴바