제로부터시작하는개발세계

차분배열 Difference Array구간 업데이트를 빠르게 수행하기 위한 기법입니다.일반적으로는 특정 구간 업데이트는 O(n) 만큼 걸리지만 차분 배열을 사용하면 O(1)에 가능하다.누적합을 문제를 풀 때 이러한 방법을 쓴 적이 있지만 특정 기법이 있는지는 잘 몰랐어서 정리를 해보려고 한다.기본 개념직관적으로 사용할 때는A = [1, 2, 3, 4, 5] 라는 배열이 존재하고0번 인덱스 ~ 2번 인덱스까지 2씩 더할려고 하면A[0] += 2 A[1] += 2 A[2] += 2 이런 방식으로 총 3번에 걸쳐서 수행이 된다.이러한 방식으로 여러 번 반복을 할 경우 시간 복잡도가 많이 올라가게 된다.차분배열을 사용해보자차분배열을 사용하려면 "배열의 크기 + 1" 크기에 해당하는 배열을 하나 만들어준다..

AWS로 리액트 빌드 폴더를 전송해보자 윈도우 기준으로 보고 있기 때문에 쉘 스크립트를 사용할 수 있는 환경을 각자 셋팅을 하고 해야 한다. 필자는 git bash를 사용해서 쉘 스크립트를 실행하였다. scp를 사용하자 우선 빌드 폴더를 scp를 사용하여 폴더를 전송하려고 한다. scp 를 사용할 때 단일 파일 전송 명령어는 아래와 같다. scp [옵션] [파일명] [원격지_id]@[원격지_ip]:[받는 위치] 디렉토리를 전송할때는 -r 옵션을 사용한다. scp [옵션] [디렉터리 이름] [원격지_id]@[원격지_ip]:[보낼 경로] scp -r build id@ip:경로 scp로 aws로 전송이 되는지 확인하기 aws 에 접속을 할때는 pem을 사용할것이므로 해당 명령어를 사용할 계획이다. -i 옵션 ..

Spring security 를 사용하지 않고 구현 카카오 애플리케이션 등록하는것은 제외하고 포스팅 할 예정 카카오 로그인 페이지를 이동하기 위해 리다이렉트 AuthController package crud.board.controller; import crud.board.dto.KakaoResponseDto; import crud.board.service.KakaoUserService; import lombok.RequiredArgsConstructor; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.bind.annotation.GetMapping; import org.springfr..

문제 링크 풀이 양방향 간선으로 주어지기때문에 roads에 저장된 연결된 간선을 배열에 모두 넣어준다. 주어진 destination 을 기준으로 다익스트라를 돌려 최단거리를 구해준다. sources에 있는 지역중 갈수 없는경우(1e9인 경우)에는 -1 을 answer에 넣어주고 아닐 경우에는 최단 거리를 넣어준다. 제한사항 3 ≤ n ≤ 100,000 각 지역은 정수 1부터 n까지의 번호로 구분됩니다. 2 ≤ roads의 길이 ≤ 500,000 roads의 원소의 길이 = 2 roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b) 동일한 정보가 중복해서 주어지지 않습니다. 동일한 [a, b]가 중복해서 주어지지 않습니다. [a,..

문제 링크 풀이 비어 있는 방을 하나하나 찾아가면 k가 10^12 이하 이므로 시간초과가 나는 문제이다. 방문체크도 배열로 하면 시간초과가 나서 딕셔너리를 활용하면 된다. 제한사항 k는 1 이상 10^12 이하인 자연수입니다. room_number 배열의 크기는 1 이상 200,000 이하입니다. room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다. room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다. 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다. 정답 코드 import sys sys.setrecursionlimit(10**8) ..

문제 링크 풀이 heap을 사용해서 heap크기가 k보다 같거나 커졌을 경우 젤 작은 값과 비교해서 클 경우 넣어준다. 현재 heap에서 가장 값이 작은 0번째 인덱스를 answer에 넣어주면 정답. 제한사항 3 ≤ k ≤ 100 7 ≤ score의 길이 ≤ 1,000 0 ≤ score[i] ≤ 2,000 정답 코드 import heapq def solution(k, score): answer = [] heap = [] for i in range(len(score)): if len(heap) >= k: if heap[0] < score[i]: heapq.heappop(heap) heapq.heappush(heap,score[i]) else: heapq.heappush(heap,score[i]) answe..

문제 링크 풀이 딕셔너리를 사용해서 해당 종류의 귤의 개수를 저장한다. 딕셔너리에 저장된 개수를 이용해 내림차순으로 배열을 정렬한다. k개 만큼 담을때까지 계속 담고 담긴 종류의 개수를 리턴한다. 제한사항 1 ≤ k ≤ tangerine의 길이 ≤ 100,000 1 ≤ tangerine의 원소 ≤ 10,000,000 정답 코드 def solution(k, tangerine): answer = 0 dic = {} arr = [] for item in tangerine: if item in dic: dic[item] +=1 else: dic[item] = 1 arr.append(item) arr.sort(key=lambda x : -dic[x]) cnt = 0 for i in range(len(arr)): ..

문제 링크 풀이 토핑의 종류에 따라 방문 체크를 한다. 앞에서 나오지 않았던 토핑의 종류였다면 앞에서 나온 종류의 개수를 +1 을 해준다. 앞에서 부터 체크를 해주고 뒤에서 부터 체크를 한번 더 해주고 arr[i] == arr2[i+1] 일경우 answer+1 을 해준다 제한사항 1 ≤ topping의 길이 ≤ 1,000,000 1 ≤ topping의 원소 ≤ 10,000 정답 코드 def solution(topping): answer = 0 visited = [0 for i in range(10001)] n = len(topping) arr = [0 for i in range(n)] arr2 = [0 for i in range(n)] cur_cnt = 0 for i in range(n): if visi..

문제 링크 풀이 LRU 알고리즘을 사용하요 캐싱을 구현하는 간단한 문제이다. deque를 사용하면 편하게 구현이 가능했지만 LFU 알고리즘을 생각하고 구현을 해버렸다... dic 에는 마지막에 참조되었던 번호를 넣어준다. 캐시가 꽉 찼을때 dic안에 있는 마지막 참조된 인덱스를 기준으로 정렬을해서 0번째를 교체하는 방식으로 했다. 제한사항 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다. cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다. cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다. 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 ..

문제 링크 풀이 브루트 포스로 가능한 문자열을 모두 구하고 정렬해서 index를 찾으면 됩니다. 제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 정답 코드 import sys def solution(word): answer = 0 arr = ['A','E','I','O','U'] words = [] cword = [] def dfs(index): if index == 5 and len(cword): words.append(''.join(cword)) return for i in range(5): cword.append(arr[i]) dfs(index+1) cword.pop() for i in range(5): ..