목록개발/algorithm (175)
백준1935 - 후위 표기식 2 (스택) Python
https://www.acmicpc.net/problem/1935 해당 문제는 피연산자 갯수 | 후위표기식 | 피연산자와 대응하는 값을 주고, 해당 식을 계산하는 문제다. 후위 표기식에 대한 설명 # 해당 문제에는 후위 표기식에 대한 설명이 없으므로 아래 설명으로 대체한다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다. 중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설..
백준15815 - 천재 수학자 성필 (스택) Python
https://www.acmicpc.net/problem/15815 해당 문제는 '후위 표기식'을 연산하는 문제다. 문제에서 말하는 설명을 이해하면 후위 표기식은 우선 순위에 따라 이미 정렬된 문자열을 다루는 것이기 때문에 abc*+ 의 경우, b * c 를 먼저 처리한 뒤 a + (b * c)를 하여 값을 연산한다고 볼 수 있다. 그리고 이는 스택으로 풀이가 가능한데, 빈 스택에 연산자가 들어오기 전까지 스택에 정수를 추가하다가, 연산자가 들어올 경우 스택 마지막에 위치한 두 정수를 꺼내 연산한 뒤 다시 스택에 넣어주는 과정을 반복하는 방식으로 풀이가 가능하다. 문제 풀이 방식 import sys data_temp = sys.stdin if sys.platform == 'linux' else open(..
백준2713 - 규현이의 사랑을 담은 문자메시지 Python
https://www.acmicpc.net/problem/2713 문제 자체가 어려운 편은 아니나, 구현 자체에 오랜 시간을 소요한 문제였다. 문자열 첫 번째에 '공백'이 나오는 가능성을 배제하고 첫 코드를 작성하여, 백준에 첫 질문을 만들게 한 문제기도 하다. 문제에서 하나의 테스트 케이스를 해결하는 과정을 요약하면 아래와 같다. 1. 공백 순서를 신경써서 행렬 높이, 행렬 너비, 문자열을 찾는다. 2. 행렬 높이 * 행렬 너비 크기의 2차원 배열을 만든다. 3. 주어진 규칙에 따라 알파벳을 정수 변환 후, 이진수로 변환한다. 이때, 하나의 알파벳이 이진 수 변환 시 길이는 5여야 하며, 이를 만족하지 않을 경우 0으로 채운다. 4. 이차원 배열을 문제에서 주어진 규칙에 따라 채운다. 5. 채운 이차원..
프로그래머스 Lv.3 - 거스름돈 (DP) Python
https://school.programmers.co.kr/learn/courses/30/lessons/12907 해당 문제는 각 돈의 종류로 특정 값을 만들 수 있는 모든 경우의 수를 출력하는 문제다. 이 또한 지난 포스팅과 같이 다이나믹 프로그래밍으로 풀이가 가능하다. 즉 위 문제 예시와 같이, n = 5원 / money = [1,2,5]라면 리스트 money에 있는 동전으로 만들 수 있는 0원 ~ 5원까지의 경우의 수를 구해나가며 5원을 만들 수 있는 경우의 수를 구할 수 있다. 먼저 경우의 수를 담을 리스트를 선언한다. 이때, 앞서 언급한 것과 같이 0원 ~ 5원을 만들 수 있는 경우의 수를 담아야 하므로 리스트의 길이는 n+1 이고 초깃값은 0이다. 하지만, 0원을 만드는 경우는 '모든 돈을 사..
백준11053 - 가장 긴 증가하는 부분 수열 (DP) Python
https://www.acmicpc.net/problem/11053 해당 문제는 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제다. 인덱스 순서대로 가장 긴 수열을 구해나가면 결국 가장 긴 수열이 무엇인지 파악할 수 있으므로, 다이나믹 프로그래밍(DP)으로 풀이가 가능하다. 먼저 각 인덱스 별로 가장 긴 수열의 길이를 저장해야 하므로 수열의 크기에 맞게 리스트를 만든다. 이때, 리스트에서 각 원소가 갖는 기본값(최솟값)은 1인데, 수열에서의 각 인덱스들은, 자기 자신만을 갖는 길이 1의 수열을 만들 수 있기 때문이다. N, arr = int(data[0]), list(map(int, data[1].split())) dp = [1 for _ in range(N)] 사실 처음 보는 문제 유형..
백준1991 - 트리순회 (그래프, 재귀) Python
https://www.acmicpc.net/problem/1991 해당 문제는 이진트리의 전위 순회 / 중위 순회 / 후위 순회한 결괏값을 출력하는 문제다. 문제에서 해당 순회들이 무엇인지는 설명하고 있기 때문에 추가적인 설명은 하지 않는다. 해당 입력값에 따른 그래프 구현은 아래와 같다. 들어오는 문자열을 쪼갠 뒤 root 노드를 key로 설정, 왼쪽 | 오른쪽 자식이 '.'이면 None으로 설정한 뒤 두 자식을 리스트로 하여 value로 설정했다. def makingGraph (data) : _graph = {} for _str in data : root, left, right = _str.split() left = left if left != '.' else None right = right if ..
백준1283 - 단축키 지정 JS
https://www.acmicpc.net/problem/1283 문제는 n개의 문자열을 주고, 주어진 규칙에 따라 순서대로 단축키가 적용된 문자를 대괄호로 감싼 전체 문자열 출력하는 문제다. 단축키를 설정하는 기준은 먼저 각 문자열이 가진 단어들의 첫 글자가 단축키로 지정되어 있는지 살핀 뒤, 지정되어 있지 않다면 단축키로 등록한 뒤 단축키를 대괄호로 감싸 문자열 반환. 각 단어의 첫 글자가 모두 단축키로 등록되어 있다면 왼쪽부터 단축키로 지정되어 있는지 확인 후 단축키로 등록한 뒤 지정되어 있지 않다면 단축키로 등록한 뒤 단축키를 대괄호로 감싸 문자열로 반환하면 된다. (이때, 단축키는 대소문자를 구분하지 않고, 특정 문자열에 단축키를 지정할 수 있는 문자가 없는 경우 문자열을 그대로 반환해야하니, ..
백준24444 - 알고리즘 수업 - 너비우선탐색1 (deque) Python
https://www.acmicpc.net/problem/24444 문제는 너비우선탐색을 구현하여, 각 정점의 방문순서를 출력하는 문제다. 너비우선탐색 문제 풀이 대해 포스팅을 몇 번 진행한 적 있지만, 이번 포스팅에서는 파이썬 내장모듈인 deque에 대해 소개한다. deque는 double-end queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조를 말한다. deque는 collections 모듈에 포함되어 있으며 리스트와 유사한 동작을 수행하지만 효율적인 연산을 제공한다. 개인적으로 생각하는 deque와 리스트의 큰 차이점은 맨앞에서 요소를 제거할 때인데, 이때, n이 전체 길이라고 한다면 deque는 O(1)의 시간복잡도, 리스트는 O(n)의 시간복잡도로 처리된다는 것에 있다. (..