감자는 아직 꿈을 꾼다.

https://www.acmicpc.net/problem/3860  🤔 풀기 전의 문제에 대한 생각☑️ 문제를 읽으며문제를 읽고 생각한 것은 좌표를 간선을 이용해서 연결하여 그래프로 만들자 였다.BFS에서 4방향으로 이동하는 것을 간선을 통해서 표현하고벨만 포드 알고리즘을 통해서최단거리를 구하려 했다.문제 자체도 계속해서 과거를 돌아가는 것을 출력하라고 하기에대놓고 벨만 포드 문제라고 생각했다. 물론 해당 문제를 가지고 플로이드는 실행하지 못한다. N 이 900가 되기에 3제곱이 되면 시간복잡도가 무조건 터진다.핵심결국 이 문제의 핵심은 개인적으로 바라볼때 구현력이다.좌표를 간선으로 연결해서 그래프로 만드냐이 부분에서 나는 처음에 가로 → 이 방향과 세로 위 방향을 순회하면서연결시켰지만 끝내 오류가 계..

🤔 풀기 전의 문제에 대한 생각☑️ 문제를 읽으며주어진 STR 문자 배열을 사용해서 최솟값으로 원하는 문자열을 완성처음 봤을때 아예 생각이 떠오르지 않는 문제생각한 추상적인 접근법접근법1. 해당 문자열의 자릿수의 DP문자열이 주어졌을때 apple이라고 치면 a까지의 가능한 최솟값을 기준으로주어진 STRS 문자열 배열을 SET으로 전환시켜 contains 확인하는 식으로 가면 어떨까??2.문자열의 시작을 찾는다.우선 문자열의 시작을 이룰수 있는 문자열을 찾는다.N번 순회해서 시작을 이룰수 있는 문자열 찾기시작을 이루는 문자열을 기준(최대 100개)잡기남은 문자열을 기준으로 문자열을 잘라가면서 set에 contains인지 확인작성하다보니 둘다 안되는 것같다.🥸단순하게 생각하자DP는 결국 점화식을 구해서 ..

🤔 풀기 전의 문제에 대한 생각☑️ 문제를 읽으며뭔가 BFS에서는 이런 문제 유형이 따로 있지 않을까 생각이 든다..기본 상황모든 칸을 방문 상 하 좌 우 한칸씩 -> 칸의 높이차가 Height 이하 Height보다 많이 나면 사다리 설치 => 비용 : 높이 차만큼 최소 비용 -> BFS 사다리 갯수 제한 x 철거도 x 재사용이 가능하지 않을까? 어딘 가를 갈때 다른 곳을 경우해서 가능한 곳이면 사다리 안써도 된다.우선 처음에 BFS 를 해서 사다리를 쓰지 않고 방문 가능한 곳 찾기.그 후 사다리를 이용해서 가능한 곳을 찾아야 되지 않나.문제 풀이1 . cost 로 오름차순 정렬→ 이거 시도 중 (메모리터짐)cost로 오름차순 정렬해서 방문할 순서를 정한다즉 cost가 작은 것부터 우선순위 큐에서 뽑아..

알고리즘 : 최소비용신장트리 최소비용신장트리를 완성해가는 데 union find 알고리즘을 사용해서 사이클을 피하는 방식이다.Find에서 경로압축을 진행한다. 처음에 루트를 찾아가는 find함수에서 루트노드까지 재귀로 찾아가고나중에 return 되면 자식 노드들의 부모가 전부 루트노드로 갱신되며 추후의 탐색비용이 줄어드는 경로압축이 진행된다. find함수로 루트 노드를 찾아 다를 경우 union한다.이 과정에서 간선 사이 비용을 오름차순으로 정렬하여, 최솟값을 선택하면서 계속한다.최종적으로 간선의 수가 n-1 개일 경우 트리가 완성되었으므로 break한다. 문제설명https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한..

알고리즘 : 유니온 파인드 유니온 파인드는 말그대로 합치기와 탐색입니다.여기서 상호 배타적인 집합 관계가 나옵니다. 말 그대로 둘이 어떠한 교집합도 없는 집합입니다.그래프로 생각하면 둘이 완전히 분리된 그래프 인거죠. 파인드는 자기 자신의 부모로 계속 올라가서 루트 노드까지 가는 과정이고 여기에서 만약 서로 다른 두 점을 파인드 했는데 루트 노드가 같을 경우는 이미 같은 집합 인것이고다를 경우는 다른 집합인 것이겠죠 유니온은 말 그대로 두 집합을 합치는 과정인데 여기서 중요한 게 깊이 차이를 신경써야됩니다.그냥 막무가내로 붙여버리면 깊이가 깊어져서 비효율적이게 됩니다.그래서 두 루트노드의 랭크를 확인해서 더 큰 랭크인 루트노드를 부모 루트 향하게 작은 랭크의 루트노드를 바꿔주면 트리의 깊이 차가 안생기므..

알고리즘 : DP 한번에 바로 풀지 못했다.오히려 Lv.4인 도둑질 문제는 풀었지만 레벨 2인 문제는 못푸는 게 아이러니 한거같다.처음엔 접근을 완전히 잘 못했다. 틀린 코드도 같이 설명할 예정이다.문제 설명링크 참조https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr틀린 코드  상당히 난잡하고 무조건 시간복잡도가 터질 수밖에 없는 코드다.일단은 이 방법 밖에 떠오르지않아서 구현했지만 , 잘못된 방식이란거는 어느정도 알았고 그냥 정확성테스트만 어느정도테스트 해보고싶었다.행을 기준으로 인접해서 1이..

알고리즘 : DP DP는 거의 아이디어 문제 인것 같다.내 방식대로 풀고나서 다른 사람들의 블로그 글을 보았는데 솔직히 잘 이해 안되는 부분도 있었다.하지만 내 방식은 그래도 이해하기 쉽지 않나? 싶다.한번 천천히 읽어 보길 권장합니다.사실 처음 풀어보는 Lv.4문제라서 겁먹었는데 생각만큼은 아니였다.문제설명링크참조https://school.programmers.co.kr/learn/courses/30/lessons/42897# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr내 풀이 우선 코드에 해당 설명의 주석을 달아 놓았다.혹시 모르거나 피드백할 부분 있으면 답글 부탁드립니다. 처음으로 연상할 수 있..

알고리즘 : BFS토마토 시리즈로서 2차원인 7576번과 3차원인 7569번을 설명하도록 하겠다.문제설명 : 7576번 토마토https://www.acmicpc.net/problem/7576링크 참조 내 풀이 이 문제는 시작점이 여러개 일경우의 BFS 문제이다.문제에서도 주어진 것처럼 토마토의 위치가 여러군데에서 시작하고BFS를 따로따로 진행하면 dist배열 초기화가 먼저 이루어져서 겹치는 부분에 대해 처리가 정확히 되지 않는다.간단하게 이 문제를 풀이하면 시작점들을 큐에 집어넣고 BFS를 시작하면 된다.왜냐하면 큐의 특성상 FIFO 이므로 시작점들을 넣고 BFS를 돌리면 순차적으로 각 시작점 위치에서 BFS가 돌아가면서 실행이 되기 때문이다. 큐의 특성으로 거리순으로 저장되는 것 만약에 스택이였으면 하..

이분 탐색은 순차탐색으로 풀면 시간복잡도가 터져서 풀지 못하는 문제를 시간 복잡도를 LogN으로 줄여서 탐색의 시간을 줄여준다. 기본적으로 시작 인덱스와 끝 인덱스를 활용해서, 중간 인덱스 값을 구해서 값을 비교하면서 진행한다.기본 조건으로 정렬이 되어 있어야한다.당연한 말이지만 정렬이 되어있지 않으면, 탐색 과정에서 숫자의 대소 비교가 의미없다. 알고리즘에서 이분 탐색을 활용하는 것을 설명하겠다.문제의 해답 코드로 설명한다. Ref : https://blog.encrypted.gg/985 1. 가장 기본적인 이분 탐색-> 시간복잡도 lgN이 필요할 경우 사용 문제 백준 1920번 https://www.acmicpc.net/problem/1920  import java.io.BufferedReader;i..

String 문제예외상황만 잘 처리하면 되는 문제다. https://www.acmicpc.net/problem/3613  내 풀이 StringBuilder의 사용법을 익힐수 있는 좋은 문제다.deleteCharAt() -> 해당 인덱스 문자 삭제insert() -> 해당 인덱스 앞에 문자 삽입indexOf() -> 포함 되있으면 해당 시작 인덱스 반환 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Solution { public static void main(String[] args) throws IOException { ..