잡다한 IT 지식

문제 출처 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZVqPrHaAy_HBIOy[문제 설명]'L', 'R', '?' 3가지 명령이 있다.'L'은 왼쪽, 'R'은 오른쪽, '?'는 양쪽 다 가능하며 사용자가 지정해야 된다.'?'를 정하는 기준은 원점에서 가장 먼 거리를 이동하는 경우를 정해야 한다.참고로 최종 도착지가 최대 거리가 아니다.예를 들어, LLLRR이면 -3 ~ 0 사이를 이동한다.이 경우에 최종 도착점은 -1이다. 최대 거리는 도착점이 -3일 때 거리인 3이다. [접근 방법]1. 그리디만약, 최종 도착점이 최대 거리인 경우라면 그리디로 풀 수 있다. 'L'과 'R' 둘 중에서 가장 많이 나온 명..

태그 잊지 않고 붙이세요#Algorithm #출제사이트 #D4 #Solved #Dijkstra문제 링크제한사항가장 첫 줄은 전체 테스트케이스의 수이다.각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.접근 방법문제엔 복구 시간이라고 쓰였지만 간선과 가중치로 단순하게 생각해보자.지도의 위치가 노드이며 복구 시간은 해당 노드로 이어진 간선의 가중치다.점과 점 사이 최소 거리로 문제를 단순화할 수 있다. 다익스트라로 해결 가능하다.복잡도시간복잡도: (V + E) * logE (V는 노드의 개수, E는 간선의 개수)공간복잡도: O(E)코드import heapqT = int(input())#..

태그 잊지 않고 붙이세요#Algorithm #sw_expert_academy #D3 #Solved문제 링크제한사항첫 줄에 테스트케이스의 수 T가 주어진다. 1다음 줄부터 테스트 케이스의 별로 T, T_end, k가 주어진다.1문제 정리함정 문제다. 문제 초반에 python 코드를 주고 비용이랑 이전 비용 차이 cost 함수 등 많은 정보를 주지만 다 필요 없는 내용이다.우리가 구할 값은 T에 K를 몇 번 곱하면 T_end보다 작아지느냐다.예제 1은 1000 0.1 0.8이 주어진다. 여기서 1000에 0.8^42의 값이 0.1보다 작아진다.접근 방법단순하게 반복문으로 T_end보다 작아질 때까지 곱한다. 이걸로 통과된다.복잡도시간복잡도는 x를 반복횟수라고 생각했을 때$T * k^x $x $O({ln(Te..

태그 잊지 않고 붙이세요#sw_expert_academy #binary_search #D3 #Solved문제 링크제한사항11문제 정리이분 탐색 과정 중에 왼쪽 오른쪽을 번갈아 검색한 경우의 개수를 구해라.접근 방법단순한 이분 탐색 구현 문제다. 단, flag 값을 통해서 이전에 왼쪽을 탐색했는지 혹은 오른쪽을 탐색했는지 판별하면 된다.A가 정렬이 필요하므로 NlogN이 필요하고 추가적으로 M개 원소를 이진 탐색하므로 M*logN이 필요하다.복잡도시간복잡도: 정렬 + M개 원소를 이진탐색 = O(N * logN) + O(M * logN) = O(N * logN + M * logN) = O((N + M) * logN)공간복잡도: O(N + M)코드T = int(input())# 여러개의 테스트 케이스가 주어..

태그 잊지 않고 붙이세요#sw_expert_academy #Implementation #D2문제 링크제한사항[제약 사항]N 은 5 이상 15 이하이다.M은 2 이상 N 이하이다.각 영역의 파리 갯수는 30 이하 이다.문제 정리파리가 가장 많이 죽는 위치를 선택하라.접근 방법파리가 가장 많이 죽는 위치를 구해야한다.2차원 배열 모든 점을 시작점으로 삼고 DFS를 통해 모든 값을 일일이 계산하는 방법을 사용했다.(row, col) 지점에서 대각선, 오른쪽, 아래 방향으로 DFS 진행하여 누적합을 구했다.시간복잡도는 N^2 * M^2무식한 방법이지만 제약 사항을 먼저 확인했다면 해당 시간복잡도로 충분히 통과 가능함을 알 수 있다.복잡도시간복잡도: O(N^2 * M^2)공간복잡도: O(N^2)코드T = int(..

#sw_expert_academy #Algorithm #D2 #Solved문제 링크제한사항시간 : 10개 테스트케이스를 합쳐서 C의 경우 10초 / C++의 경우 10초 / Java의 경우 20초 / Python의 경우 30초메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내문제 정리가장 큰 최빈수를 구하라.접근 방법최빈수는 해당 숫자가 가장 많이 나올 때 최빈수가 된다.최빈수인지 확인하기 위해선 숫자의 출현 빈도를 따로 저장할 필요성이 있다.생각나는 선택지는 2가지. map과 단순 int 배열. map은 해싱 비용도 있으므로 int 배열 사용했다. [^1] 문제에서 최빈수가 여러 개면 가장 큰 점수를 출력하라는 조건이 있다.선행 검색 중에 최빈값의 출현 빈도가 현재 최빈값과 ..