개발 쥬스

🔗 문제 링크: https://www.acmicpc.net/problem/13549  🔍 해결 과정일차원 배열을 활용한 BFS 유형의 문제로 다음과 같은 과정으로 문제를 해결하였습니다.1️⃣ 각 좌표에 도달할 때 나올 수 있는 최소 시간의 정보를 저장할 정수형 배열 d를 정의한다.2️⃣ d 테이블의 초기값을 무한으로 초기화해준다. (코드에서는 10억으로 설정)3️⃣ BFS를 활용하여 왼쪽, 오른쪽, 순간이동 하는 경우에서의 시간을 계산해 준 다음 d 테이블에서 최소 시간을 계속 계산해준다.4️⃣ BFS 완료후 d 테이블에서 동생이 위치한 d[k] 값을 반환해준다.  ✏️ 코드import java.io.*;import java.util.ArrayDeque;import java.util.Arrays;im..

🔗 문제 링크: https://www.acmicpc.net/problem/24955 🔍 해결 과정문제에서 주어진 그래프는 MST의 형태를 이루고 있습니다. 그래서 시작점에서 끝점까지의 숫자를 단순히 이어붙여서 문제를 해결할 수 있을 것이라고 생각하기 쉬우나 집의 대문에 주어지는 값의 최댓값은 10억이고, 두 개의 10억을 단순히 문자열 형태로 이어 붙여서 이를 누적해나가면 메모리 초과 문제에 걸립니다. 따라서 문자열이 아닌 Long 형태의 정수로 계산하면서 BFS를 이어가야 합니다. 설계 과정은 다음과 같습니다.1️⃣ 정수형 이중 리스트 homes를 만들어 집들과의 연결 관계를 나타낸다. 2️⃣ 정수형 배열 homeValues를 만들어 집 대문에 적혀 있는 값 정보를 담는다.3️⃣ BFS를 활용하여 ..

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  🔍  해결 과정💡 해결 요약: BFS를 통한 해결 시간 복잡도 문제로 고민을 엄청 했었던 문제입니다. 처음에는 반복문을 통해 출발지마다 BFS를 활용하여 특정 도착 지점마다 최소 intensity를 계산하는 방식으로 생각을 했지만 시간 복잡도로 인해서 이 방식은 사용할 수 없다고 판단했었습니다. 왜냐하면 최대 노드의 개수가 5만이고, 출발지도 최대 5만이기에 인접리스트에서 시간 복잡도 O(n + e) (n: 노드의 개수..

🔗 문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com해당 사이트의 문제는 로그인을 진행한 후 확인할 수 있습니다.  🔍 해결 과정문제를 처음 봤을 때 언뜻 보면 평범..

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  🔍  해결 과정문제를 보았을 때 dp를 활용하여 문제를 해결해야겠다는 생각을 가지긴 했지만, 어떤 것을 기준으로 잡아서 점화식을 세우는 것이 적절한지 고민이 많았던 문제였습니다. 그렇게 몇 시간 동안 고민한 끝에 타일의 오른쪽 맨 끝 삼각형을 기준으로 잡고 이 삼각형이 마름모로 묶여 있는 경우와 묶여 있지 않는 경우 두 가지 경우를 생각해서 점화식을 세웠습니다. 즉 2차원 배열의 dp를 활용하여 마름모 또는 정삼각형으로 ..

🔗 문제 링크: https://www.acmicpc.net/problem/17470 🔍 해결 과정배열 돌리기 3 문제와 내용은 같으나 연산의 수 R의 최댓값이 200만이라는 점에서 차이가 있습니다.직접 배열의 내용 자체를 가지고 연산을 활용하기에는 시간복잡도 O(NMR)을 가지기 때문에 최악의 경우 200만 x 10000 = 200억의 연산이 진행이 되기에 일반적인 풀이로는 시간초과가 발생합니다. 그래서 처음에는 배열의 내용들을 바탕으로 연산하기보다는 배열의 영역을 매핑하여 압축시키고 이를 바탕으로 연산을 진행해야겠다는 생각을 했습니다. 즉 그림으로 표현하자면 다음과 같습니다.  위 네 가지의 영역을 바탕으로 2 x 2 압축된 배열을 만들고 R번 연산을 진행을 하게 된다면 최대 2 X 2 X 200만..