본문 바로가기

알고리즘&자료구조

 (18)
9012 - 괄호 문제 괄호 문자열은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 한 쌍의 괄호 기호로 입력으로 주어진 괄호 문자열이 괄호의 모양이 바르게 구성된 올바른 괄호 문자열인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 입력 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 출력 만일 입력 괄호 문자열이 올바른 괄호 문자열이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 예제 입력 6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()..
9093 - 단어 뒤집기 문제 문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다. 출력 각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다. 예제 입력 2 I am happy today We want to win the first prize 예제 출력 I ma yppah yadot eW tnaw ot niw eht tsrif ezirp 풀이 def reverse_word(sente..
코딩테스트 연습 - 구명보트(탐욕법) 문제 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제..
4주차 - 진법변환/비트연산 파이썬에 내장된 진법 변환 함수들 10진법 → 2진법 : bin() 10진법 → 8진법 : oct() 10진법 → 16진법 : hex() n진법 → 10진법: int() 비트연산 - AND(&), OR(|), XOR(^), NOT(~), SHIFT() 한 개 또는 두 개의 이진수에 적용되는 연산 AND : 둘 다 1일때만 1을 반환, 아닐땐 0을 반환. OR: 둘 중 하나라도 1일 때 1을 반환, 아닐땐 0을 반환 XOR: 둘 중 하나만 1일 때 1을 반환 NOT: 비트 반전 연산자; 1은 0으로, 0은 1로 SHIFT: 비트 이동 연산자; 주어진 수 만큼 옮김 bin(0b112) = 0b11 비트연산의 활용 컴퓨터 연산을 위한 비트 필드 데이터 압축 및 암호화 유한 상태 기계 컴퓨터 통신을 위한 포트 ..
코딩테스트 연습 - 타겟 넘버(DFS/BFS)(푸는중) 문제 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 풀이 ..
3주차 - 너비우선탐색/깊이우선탐색 1. 너비우선탐색(BFS; Breadth First Search) : 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회탐색 → 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 while len(queue)>0: count = len(queue)# 같은 거리에 있는 큐 개수 for time in range(count):# 같은 거리에 있는 큐 개수만큼 검사 now = queue.pop(0) if now == destination: return answer for i in data: if i[0]==now and visited[i[1]-1]==False: queue.append(i[1]) visited[i[1]-1]=True elif i[1]==..
코딩테스트 연습 - 모의고사(완전탐색) [문제] 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한 조건 시험은 최대 10,00..
2주차 - 완전탐색/이분탐색 탐색이란? : 많은 데이터 속에서 원하는 데이터를 찾는 것. 탐색의 종류 완전탐색(Brute Force) 이분탐색(이진검색) 깊이우선탐색(DFS) 너비우선탐색(BFS) 문자열탐색 KMP BM 1. 완전탐색 가능한 모든 경우의 수 탐색하며 값을 찾는 것 결과 값이 가장 확실하지만 그만큼 시간이 가장 오래걸리는 탐색방법 반복문/재귀함수를 이용해 완전탐색 # 반복문을 이용한 완전탐색 def solution(trump): for i in range(len(trump)): if trump[i] == 8: return i return -1 # 재귀함수를 이용한 완전탐색 def solution(trump, loc): if trump[loc] == 8: return loc else: return solution(tru..
코딩테스트 연습 - 주식가격(스택/큐) [문제] 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 price return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이..
1주차 - 스택 & 큐 1. 스택(Stack; 쌓다) push : 입력 peek : 가장 마지막으로 입력된 값 확인 pop : 가장 마지막으로 입력된 값 꺼내오기 Stack 함수 직접 구현하기 # Stack 함수 직접 구현하기 class Stack(list): push = list.append def peek(self): return self[-1] s = Stack s.push(1) s.push(2) s.push(3) print("my stack is: ", s) # my stack is: [1, 2, 3] print("popped value is: ", s.pop()) # popped value is: 3 print("my stack is: ", s) # my stack is: [1, 2] print("peeked valu..

티스토리툴바