✏️ 알고리즘 개요알고리즘 문제를 풀다보면 특정 수열에서 i번째 원소를 기준으로 왼쪽 혹은 오른쪽 원소들에 대해 최대값을 구해야하는 경우가 종종 있다. 아래와 같이 단순하게 왼쪽, 오른쪽 원소들에 대해 반복문을 통해 최대값을 구하는 것을 생각해볼 수 있다.int[] arr = new int[]{5,9,6,2,1,4,5,6,8,10,4};for(int i=0; i=0; j--) { leftMaxValue = Math.max(leftMaxValue, arr[j]); } //오른쪽 최대값 int rightMaxValue = 0; for(int j=i+1; j 그러나 수열의 길이가 매우 길어지고, 찾아야하는 원소의 개수가 많아질수록 위와 같은 반복문은 매우 긴 시간복잡도를 가지..

🔗 문제https://www.acmicpc.net/problem/1655📝 풀이자료 구조 + 우선순위 큐접근법입력으로 들어오는 정수들에 대해 기록하고, 중간값을 N번 찾는 문제입력값 N은 최대 100,000으로 대략적인 시간복잡도는 O(NlogN)으로 잡고 풀어야 한다. 단순하게 생각했을 때, 입력을 받으면서 정렬을 계속 수행한 후 현재 개수/2의 인덱스를 구하면 되지만정렬의 시간복잡도는 O(NlonN)으로 입력값 N에 대해 최대 100,000번 수행한다고 하면 O(N^2)을 넘어서게 된다.그렇다면 어떻게 풀이를 해야할까? 매번 정렬을 수행할 수 없으니 정렬을 유지한 채 값을 기록하고, O(1)로 중간 값을 찾을 수 있어야 한다.자료구조 중 이러한 특성을 가지고 있는 자료구조가 있다.기본적인 정렬을 ..

취업준비를 하던 중 인턴 기회를 얻어 값진 경험을 했고, 첫 회사인만큼 가서 느꼈던 것들, 배운 점들이 많았습니다. 이번에는 이에 대한 회고를 해보려합니다. 🎊 인턴 합격24년 SSAFY를 수료하고 개인 학습과 취업 준비를 병행하던 중, 두 곳의 면접 기회를 얻었고 열심히 노력한 결과 25년을 맞아 3주 간의 인턴 경험을 얻을 수 있었다.‘시스템 개발’ 직무로 개발 현업을 직접 느낄 수 있고, SSAFY에서 해왔던 개발과 비교해서 어떤 새로운 환경이 기다리고 있을까라는 기대감과 함께 입사했다. 😳 첫 인사 드립니다.1월 6일 도착한 교육장에서 인턴 생활에 대한 가벼운 OT 진행 후 각 팀의 팀장님들이 인턴 사원들을 픽업하러 오셨다. (마치 프로듀스101…)나의 경우에는 TO가 혼자였고, 팀장님과 단 ..

여느 날처럼 에줍사 스터디를 진행하다가 그래프 탐색 문제에 대해 논의를 하던 중 나머지 스터디원들은 BFS로 접근을 했지만, 혼자 다익스트라로 접근을 했던 적이 있습니다. "왜 다익스트라를 떠올렸을까?"라는 생각을 한 결과, 다음과 같은 잘못된 기저가 깔려있다는 것을 알 수 있었습니다.시간복잡도 : Dijkstra BFS 또한 완전탐색으로 최단 거리를 찾는데 시간이 오래 걸릴 것이라 생각함알고리즘 특성 차이이번 회고를 통해 아래와 같이 잘못된 정보들을 바로잡으려합니다.추상적인 시간복잡도두 알고리즘의 동작 방식조건에 따른 수행 방식 BFS와 Dijkstra에 대한 정리는 이전에 정리해 두었던 글이 있으니 참조용으로 링크만 올려두겠습니다.https://infinitecode.tistory.com/13 [알고..