잡다한 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 #bfs #D4 #Solved문제 링크제한사항첫 번째 줄에 테스트 케이스의 수 T가 주어진다.각 테스트 케이스는 한 개의 줄로 구성되며, 각 줄에는 알파벳 소문자로만 구성된 문자열 S가 주어진다. S의 길이는 1 이상 100,000 이하이다.문제 정리문자 'x'를 넣어서 회문을 만들 수 있나?회문을 만드는데 필요한 연산 횟수는 몇번인가?접근 방법회문이 되려면 간단히 시작과 끝이 같으면 된다.두 문자가 같은 경우만약, 두 문자가 같다면 다음 문자로 넘어가면 된다. 이를 반복한다. 두 문자가 다른 경우문자가 같은 경우는 생각했으므로 이제 문자가 서로 다른 경우를 생각하면 된다.이 경우엔 2가지 분기로 나뉜다. 우선, 한 문자만 'x'일 경우다.이럴 땐, 'x' 문자..

태그 잊지 않고 붙이세요#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(..