그래프그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조여러 요소(정점) 간의 관계를 나타내기 위해 사용구성요소로는 정점, 간선, 가중치가 있음.분류방향 그래프(Directed Graph): 간선에 방향이 있습니다. (A,B)는 A→B를 의미하며, B→A는 별개의 간선으로 취급됩니다.무방향 그래프(Undirected Graph): 간선에 방향이 없으며 (A,B)와 (B,A)가 동일합니다.가중치 그래프(Weighted Graph): 간선에 가중치가 포함된 그래프입니다.비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.트리계층적 구조를 표현하는 특수한 형태의 그래프무방향이면서 사이클이 없는 연결 그래프임의의 두 정점을 연결하는 Simple Path가 유일한 ..

글을 작성하는 이유최근 문제를 풀면서 키워드 유추 -> 접근법 생각 -> 검증 -> 코드로 구현 순으로 풀이를 진행하는 연습을 하고 있습니다.이 과정에서 접근법에 대해 코드로 구현하는게 잘 되지 않는다고 느껴져서 이유를 생각해보고, 어떻게 개선해나갈지 정리하고자 글을 작성하게 되었습니다. 참고 문제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에서 탐색을 시작하여 길이 완성될 ..

문제https://www.acmicpc.net/problem/17485 풀이다이나믹 프로그래밍 풀이접근법처음에는 다익스트라로 최소비용 구하면 되는 것 아냐? 라는 생각을 잠깐 했지만 출발지점이 1000개가 될 수 있기에 DP로 풀었다. 문제 조건해당 문제에서 각 원소의 위치에서 할 수 있는 행동은 3가지다.왼쪽 아래중간오른쪽 아래또 다른 조건으로는 이전 행동과 같은 행동을 취하지 못한다. dp로 풀이를 하기로 했으니 각 원소의 위치의 최선의 값을 어떻게 찾을지 생각하는 것 뿐이다.간단하게 생각하면 dp[i][j]는 3가지 이전해 + 현재값 중 최소값을 선택하면 될 것으로 보인다. 그러나 다음해를 구하기 위해서 이전해가 어떤 방향에서 진행된 값인지 알 필요가 있다.이를 위해 3차원 배열로 dp배열을 구성했..