참고 문제https://www.acmicpc.net/problem/17182 포스팅 목적플로이드 워셜과 다익스트라의 개념을 알고 있다면 두 개를 혼용해서 사용할 수 있는걸 알 수 있습니다.그래서 위 문제 풀이를 위해 플로이드 워셜이 아닌 다익스트라를 N번 수행했습니다.다익스트라 코드는 평소와 같이 작성을 했지만 제출했을 때 메모리 초과가 발생하여 이유를 찾는 과정에서 다음번에도 실수할 수 있을 것 같은 반례를 찾아서 기록하기 위해 작성합니다.최초 다익스트라 코드static void Dijkstra(int start) { PriorityQueue pq = new PriorityQueue(((o1, o2) -> o1[1] - o2[1])); pq.offer(new int[]{start, 0}); ..

글을 작성하는 이유최근 문제를 풀면서 키워드 유추 -> 접근법 생각 -> 검증 -> 코드로 구현 순으로 풀이를 진행하는 연습을 하고 있습니다.이 과정에서 접근법에 대해 코드로 구현하는게 잘 되지 않는다고 느껴져서 이유를 생각해보고, 어떻게 개선해나갈지 정리하고자 글을 작성하게 되었습니다. 참고 문제https://school.programmers.co.kr/learn/courses/30/lessons/77886  키워드 유추0과 1로 이루어진 어떤 문자열 xx를 최대한 사전 순으로 앞에 오도록x에 있는 "110"을 뽑아서임의의 위치에 삽입접근법 생각문자열 x에서 "110"을 추출추출 후 남은 문자열에 대해서도 계속해서 추출최종적으로 남은 문자열에서 마지막 0의 위치를 탐색추출한 "110"을 순차적으로 마지..

문제https://www.acmicpc.net/problem/3109풀이그리디 + DFS접근법처음 접근은 완전탐색 방식으로 접근했습니다.문제를 해석해보면 왼쪽 열에서 오른쪽 열까지 벽(x)을 제외한 나머지 통로들에 파이프를 설치하여 연결할 수 있는 길의 개수를 구하는 문제입니다.주어진 조건에 의한 행동은 3가지로 다음과 같습니다.오른쪽 상단 대각선오른쪽오른쪽 하단 대각선또한 겹치게 설치 할 순 없다는 조건이 있습니다.탐색해야하는 경우의 수는 그럼 총 N개로 시작 열의 격자칸 개수만큼 탐색을 해야합니다.또한 백트래킹을 통해서 완성된 길에 대해서는 기록을 하고, 끝까지 도달하지 못하는 경우에는 원상복귀를 시켜야 한다고 생각했습니다.위와같은 로직을 구현하기 위해서 처음 0,0에서 탐색을 시작하여 길이 완성될 ..

최근 “객체지향의 사실과 오해”라는 책을 통해서 객체지향에 대해 다시금 공부를 하고 있습니다.지난 내용에 대한 간단한 언급을 보고 이해를 하지 못했던 순간문득 책을 읽고 있다는 사실을 “나는 지금 공부를 하고있다”라고 오해하고 있는 저의 모습이 보였습니다.쉽게 설명하자면 글을 읽고만 있었지, 이해하진 않고 있었다. 라는 말이 될 것 같습니다.그래서 책 읽는 것을 멈추고, 무엇이 잘못되었는지 생각해보았습니다.여담 : 이런 비슷한 경우가 있었는데?최근에 Youtube Short 컨텐츠에 대해 우스갯소리로 이야기를 나눈 적이 있습니다.대화 속에서 “최근에 본 쇼츠 기억나?”라는 질문이 나왔고, 순간 아무것도 떠오르지 않아서 헛웃음만 자아냈었습니다.이 경험에서 ‘쇼츠는 시각적인 요소로 이해하기 쉽고, 투자하는 ..