본문 바로가기

Algorithm/문제 풀이62

[알고리즘] 후위 표기식 (백준 1918번) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net 설마 이 문제 푼다고 한나절이 꼬박 걸릴지 몰랐다. 이전에 스택 활용에서 중위 표기식 → 후위 표기식 변환하는 메서드를 작성한 적이 있는지라 바로 할 수 있을 줄 알았는데 조건이 하나 더 있었다. 연산자 간의 우선순위를 고려해야한다. 즉 a+b*c 는 abc*+ 가 되어야한다. (오답 : ab+c*) 처음엔 무식하게 괄호를 직접 수식에 때려박을까 했는데 결국 안되었고 온전히 스택의 순수 기능을 활용하기로 했다. Solution 각 연산자의 우선순위를.. 2020. 8. 31.
[알고리즘] 에디터 (백준 1406번) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수� www.acmicpc.net 자료구조를 적절히 사용해서 시간 효율성을 따지는 문제이다. 함부로 내장 라이브러리를 사용하게 된다면 O(NM) 시간이 걸리기에 무조건 시간초과가 발생한다. 때문에 한 번에 명령에 O(1) 시간이 걸려야하므로 총 O(M) 시간에 문제를 해결해야 한다. Solution 기본적으로 ArrayList, LinkedList 등은 내부적으로 값을 삽입, 조회, 삭제 시 O(N)시간이 걸리기에 사용해선 안된다. 난 Stack 2개를 활용해서 커서를 기준으로 왼쪽 문자열 스택.. 2020. 8. 31.
[알고리즘] 쇠막대기 (백준 10799번) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 스택 사용 문제이다. 생각보다 해결 방법을 떠올리는 데 시간이 오래 걸렸다. 막대기가 겹쳐져있다는 조건 때문에 당황했다. 다른 사람들은 더 효율적인 방법으로 하긴 했는데 우선 내가 한 방법은 레이저를 나타내는 "()" 괄호쌍을 다른 문자로 대체하고 닫힌 괄호 ')'를 만났을 때 괄호쌍 대신 저장해놓은 문자들을 pop해서 개수를 센 뒤 문자 개수 +1 만큼 결과값에 더하는 방법을 택했다. import org.omg.PortableInterceptor.INACTIVE; imp.. 2020. 8. 30.
[알고리즘] 경주로 건설 (2020 카카오 인턴십) 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 일단 최소비용 + 최단거리 경로 탐색 문제이다. 여러가지 방법들로 풀던데 난 처음엔 dfs를 이용해서 브루트포스 방식으로 했다. 하지만 이 방식의 문제점은 depth가 깊어질수록 4방향으로.. 2020. 8. 30.

티스토리툴바