Algorithm & Data Structure/문제 풀이

[4949] 균형잡힌 세상 (Python)

링크 : https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 생각 정리 일단 stack으로 하면 된다는 생각까지가 힘들었다.. 만약 stack으로 해줄 수 있다는 걸 알았으면 시간이 더 단축됐을텐데말이다. stack을 이용하면 '(' or '[' 는 그냥 입력하고 ')' or ']'는 각각 '(' or '['가 있는지 확인을 해준 후, 있다면 빼주는 것이다. stack에 들어가는 것은 '('와 '[' 뿐인 것이다. stack이 ..

[10828] 스택 (Python)

링크 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 분류 자료구조 스택 생각 정리 입력을 꽤 많이 받으므로 input()이 아닌 readline()으로 입력을 받아야 겠다. stack(리스트)에 쓸 수 있는 push, pop, top, size, empty 문법을 생각해본다. 큐와는 또 다르므로 주의! push : append() pop : pop() top : [-1] (따로 top()이 아니라 그냥 맨 위의 것을..

[9012] 괄호 (Python)

링크 : https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 어려운 문제를 계속 풀어와서 그런지 상대적으로 쉬운 문제도 어렵게 풀고 있었어서 해결하는데 꽤 애를 먹었다.. 이 문제는 로직만 생각해내면 쉽게 풀 수 있을 것 같다 분류 자료구조 문자열 스택 생각 정리 1. '('의 개수와 ')'의 개수가 같아야한다. 2. '(' 가 나오기 전에 ')'가 나오면 안된다. '('를 +1로, ')'를 -1로 생각해서 1. su..

[18258] 큐 2 (Python)

BFS와 DFS 개념을 공부하고 문제를 풀어보기 위해 백준 18258번 문제를 풀어보았다. 해당 문제의 설명은 다음과 같다. 역시 시간초과를 해결하느라 머리를 굴려야했다 :) 큐의 개념을 익히고 실습하는 문제. 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의하세요. 링크: https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 생각정리 - 큐 문제이므로 deque를 사용해야겠다! 시간복잡도가 더 적으니까~ - 사실 이거..

[10250] ACM 호텔 (Python)

풀기 힘들었던 문제만 tistory에 올리고 있습니다. 더 많은 문제풀이 코드는 github에 있습니다:) https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 분류 구현 사칙연산 수학 입력예제1 2 6 12 10 30 50 72 출력예제1 402 1203 생각 정리 N은 손님이 방문한 번째 수, H는 높이(층 수), W는 가로(호실 수) 이다. 층과 호수에 대한 수학적 규칙을 발견해야 한다. (나는 이렇게 풀지 못했다지..) 손님이 머..

[1543] 문서 검색 (Python)

https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 분류 그리디 알고리즘 완전탐색 (Brute Force) 알고리즘 - 구현 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고,..