본문 바로가기

Algorithm76

[알고리즘] 쇠막대기 (백준 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.
[알고리즘] 보석쇼핑 투포인터 (2020 카카오 인턴십) 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이것 또한 결국 못 풀었던 문제였다. 특정 조건을 만족하는 '구간'을 찾아야하는 문제이므로 투포인터기법을 활용해야한다. 만약 투포인터 기법을 활용하지 않고 찾게 된다면 O(N ^ 2)의 시간이 걸리게 된다. 투포인터 기법 활용 시 O(N) 시간 만에 찾을 수 있다. Solution 우선 HashMap을 만들어서 보석의 이름을 키값으로 count라는 객체를 만든다. 이 때 count의 사이즈는 총 보석 종류의 수가 된다. 반복문을 돌린다. 현재 구간에 포함된 보석 종류의 수를 나타내는 gem_count가 총 보석.. 2020. 8. 30.
[알고리즘] 수식 최대화 (2020 카카오 인턴십) 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 상반기 카카오 인턴십 때 나온 문제이다. 해당 코딩 테스트에 참가했었기에 기억이 난다. (통과는 못했다.) 이 문제도 결국 못 풀었던 걸로 기억한다. 지금와서 다시 찬찬히 살펴보니 결국 문자열 처리 문제이다. 정확히 말하자면 '브루트 포스 + 문자열 처리' 문제라고 할 수 있겠다. 브루트 포스 문제인만큼 재귀 함수 사용은 필수적이다. 모듈은 크게 2개로 나누었는데 첫 번째는 '연산자 우선순위 결정' 메서드이고 나머지 하나는 '수식 계산' 메서드이다. 연산자.. 2020. 8. 29.

티스토리툴바