Algorithm & Data Structure

[programmers] 완주하지 못한 선수 (Python)

링크 : https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 분류가 해시로 되어 있다. 해시는 Key-value쌍으로 데이터를 저장하는 자료구조라고 한다. 나는 해시를 몰랐기 때문에 아래와 같은 코드를 작성했지만 효율성에서 0점을 받았다 ㅎㅎ def solution(participant, completion): answer = '' for i in range(len(completion)): f..

[programmers] 모의고사 (Python)

링크 : https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 (level 1입니다) 분류 완전 탐색 생각 정리 반복되는 숫자들에 관심을 가지면 안되고, 반복되는 갯수에 관심을 가져야 한다. 수포자1은 5개, 수포자2는 8개, 수포자 3은 10개를 반복하므로 문제의 정답과 비교할 때 나머지를 이용한다는 생각을 한다. 문제의 정답과 같을 때 맞춘 점수를 ++해주고 두번 째 문제는 return 형식이다. 맞춘 점..

[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를 사용해야겠다! 시간복잡도가 더 적으니까~ - 사실 이거..