후위식 연산(스택)
2021. 10. 19. 09:52
⏰ 코딩테스트/자료구조 활용
후위식 연산(스택) 후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요. 만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 21입니다. ▣ 입력설명 첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다. ▣ 출력설명 연산한 결과를 출력합니다. ▣ 입력예제 1 352+*9- ▣ 출력예제 1 12 풀이 계산한 것을 다른 스택에 저장해줘야 하나 했는데 그대로 스택에 올려주면서 연산하면 되는거였다. 코드1 a = input() stack = [] answer = 0 for x in a: if x.isdecimal(): stack.append(int(x)) else: i..
후위표기식 만들기(스택)
2021. 10. 18. 11:09
⏰ 코딩테스트/자료구조 활용
후위표기식 만들기(스택) 중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하라. 중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있으면 중위표기식이다. 후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식이다. 예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현된다. 만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)*2 이면 35+2* 로 바꾸어야 한다. 입력 설명 첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다. 출력 설명 후위표기식을 출력한다. 입력 예제 1 3+5*2/(7-2) 출력 예제 1 352*72-/..
백준 알고리즘 - 10799 - 쇠막대기
2021. 10. 16. 17:43
⏰ 코딩테스트/자료구조 활용
풀이 () : 무조건 레이저 스택 이용 틀린 수도코드 if ( : 스택에 ( 넣기 if 스택의 맨마지막이 ( : 스택에 ( 넣기 else 스택의 맨마지막이 ) : 스택에 ( 넣기 else ) : if 스택의 맨마지막이 ( : 스택에서 ( 빼고나서 스택에 쌓여있는 ( 개수만큼 더해주기 else 스택의 맨마지막이 ) : 스택에서 ( 빼고 count +1 틀린 코드 string = input() n = list(string) stack = [] cnt = 0 for i in n: if i=='(': stack.append(i) else: # i==')' if stack[-1] == '(': # 스택의 맨 마지막이 ( stack.pop() cnt += len(stack) else : # 스택의 맨 마지막이 ) ..
가장 큰 수(스택)
2021. 10. 14. 10:20
⏰ 코딩테스트/자료구조 활용
가장 큰 수(스택) 선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다) 만약 5276823 이 주어지고 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 됩니다. ▣ 입력설명 첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제거해야할 자릿수의 개수가 주어집니다. ▣ 출력설명 가장 큰 수를 출력합니다. ▣ 입력예제 1 5276823 3 ▣ 출력예제 1 7823 ▣ 입력예제 2 9977252641 5 ▣ 출력예제 2 99776 코드 n, m = map(int,input().split()) n = list(map(int, str(n))) # n을 한개씩 접근해서 int화 ..
역수열
2021. 10. 12. 11:41
⏰ 코딩테스트/그리디
역수열(그리디) 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 역수열은 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 자연수 N(3
증가수열 만들기
2021. 10. 12. 10:44
⏰ 코딩테스트/그리디
증가수열 만들기(그리디) 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니다. 예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다. ▣ 입력설명 첫째 줄에 자연수 N(3
침몰하는 타이타닉
2021. 10. 9. 15:07
⏰ 코딩테스트/그리디
침몰하는 타이타닉(그리디) 유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫째 줄에 자연수 N(5
창고 정리
2021. 10. 8. 11:32
⏰ 코딩테스트/그리디
창고 정리(그리디) 창고에 상자가 가로방향으로 일렬로 쌓여 있습니다. 만약 가로의 길이가 7이라면 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다. 위에 그림을 1회 높이 조정을 하면 다음과 같아진다. 창고의 가로 길이와 각 열의 상자 높이가 주어집니다. m회의 높이 조정을 한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 창고 가로의 길이인 자연수 L(1
씨름 선수
2021. 10. 8. 10:34
⏰ 코딩테스트/그리디
씨름 선수(그리디) 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다.” 만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다. ▣ 입력설명 첫째 줄에 지원자의 수 N(5
백준 알고리즘 - 1931 - 회의실 배정
2021. 10. 7. 10:19
⏰ 코딩테스트/그리디
풀이 그리디 : 문제 푸는 단계에서 가장 좋은 것을 선택하는 것 보통의 그리디는 대부분 정렬과 동반되어 나온다. 회의가 끝나는 시각을 기준으로 정렬을 해야 최대한 회의를 많이 할 수 있다. 빨리 끝나는 것이 중요하기 때문이다. 2 3 1 4 3 5 → 회의 진행 가능 4 6 5 7 → 회의 진행 가능 그리고 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교해 보는 것이다. 코드 1 n = int(input()) meeting = [] for i in range(n): first, second = map(int,input().split()) meeting.append((first, second)) # 튜플 형태로 저장 meeting.sort(key = lambda x: (x[1], x[0])) # x[1..
마구간 정하기(결정알고리즘)
2021. 10. 6. 21:27
⏰ 코딩테스트/그리디
마구간 정하기(결정알고리즘) N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간 간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요. ▣ 입력 설명 첫 줄에 자연수 N(3
뮤직비디오(결정알고리즘)
2021. 10. 5. 12:11
⏰ 코딩테스트/그리디
뮤직비디오(결정알고리즘) 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려..
백준 알고리즘 - 1654 - 랜선 자르기
2021. 10. 5. 10:59
⏰ 코딩테스트/그리디
틀린 코드 k, n = map(int,input().split()) a = [] for _ in range(k): a.append(int(input())) num = sum(a)//n while True: ans=0 for i in range(k): ans += a[i]//num if ans==n: print(num) break num -= 1 답은 맞았지만 시간초과. 코드 k, n = map(int,input().split()) def Count(len): # 길이를 변수로 받아서 cnt = 0 for i in line: cnt+=(i//len) return cnt line = [] ans = 0 largest = 0 # 랜선 중 가장 긴 값 for i in range(k): tmp = int(inpu..
이분 검색
2021. 10. 3. 12:06
⏰ 코딩테스트/그리디
이분 검색 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다. ▣ 입력설명 첫 줄에 한 줄에 자연수 N(3
격자판 회문수
2021. 10. 3. 11:26
⏰ 코딩테스트/리스트 탐색
격자판 회문수 1부터 9까지의 자연수로 채워진 7*7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하세요. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말합니다. 빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않습니다. ▣ 입력설명 1부터 9까지의 자연수로 채워진 7*7 격자판이 주어집니다. ▣ 출력설명 5자리 회문수의 개수를 출력합니다. ▣ 입력예제 1 2 4 1 5 3 2 6 3 5 1 8 7 1 7 8 3 2 7 1 3 8 6 1 2 3 2 1 1 1 3 1 3 5 3 2 1 1 2 5 6 5 2 1 2 2 2 2 1 5 ▣ 출력예제 1 3 코드1 arr = [list(map(int, inpu..
스도쿠 검사
2021. 10. 3. 10:38
⏰ 코딩테스트/리스트 탐색
스도쿠 검사 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 완성된 9×9 크기의 스도쿠가 주어지면 정확하게 풀었으면 “YES", 잘 못 풀었으면 ”NO"를 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다. ▣ 출력설명 첫째 줄에 “YES" ..