본문 바로가기
728x90

알고리즘316

[Python] 백준 1918 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제 해결 - 하나씩 뺐을 때 문자/괄호/연산부호 분리해서 문자와 괄호,연산부호와 분리한다음 재배열을 해야한다. 어떻게 해야할까... => 문자는 그대로 출력하므로 뽑으면 바로 문자열에 이어 붙이고 괄호,연산부호는 stack 안에 넣은 후 배열 하는 것이 좋을 것이다. - 이제 순서에 대해서 고민을 해야하는데 이는 그림으로 생각을 해야지 편하다.(그림은 직접 그려보길 추천한다. 여러가지 경우가.. 2022. 12. 15.
[Python] 백준 17413 단어 뒤집기2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 전략 - '' 와 word 는 출력 값이 다른데 어떻게 구현할 것인가? - 띄어쓰기 마다 단어를 뒤집을 것인데 어떻게 표현할 것인가? => isalnum 을 사용해 alphabet이나 number가 아닌 것과 구별 아니면 띄어쓰기로 인식하고 reverse()를 이용하여 단어 뒤집기! import sys input = sys.stdin.readline if __.. 2022. 12. 14.
[Python] 백준 1717 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 해결 - 집합을 어떻게 합칠 것인가? ( union 사용해야겠지...?) - set.add() 사용 할 것인가? => 사용하면 좋은데 어떻게 일반적으로 표현을 할 것인가? ex) 1번집합 2번집합 합치면 뭐로 표현??? - 해결책 => 트리를 이용해 부모를 정하자 ! ex) 1번집합 2번집합 합치면 숫자 작은 1번집합이라고 하자! CODE import.. 2022. 12. 13.
[Python] 백준 1991 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해결 전위 순회(preorder) 중위 순회(inorder) 후위 순회(postorder) 스캔 순서 노드 방문→왼쪽 자식→오른쪽 자식 왼쪽 자식→노드방문→오른쪽 자식 왼쪽 자식→오른쪽 자식 →노드 방문 예시 A→B→D→C→E→F→G D→B→A→E→C→F→G D→B→E→G→F→C→A 위 내용을 잘 모르겠으면 자료구조(Data Structure)의 트리 부분을 공부하고 오는 것이 좋.. 2022. 12. 10.
728x90