●문제●입출력 문제해석 : 현재 begin의 단어가 words 안에서 target단어로 가는데 한번에 한 단어씩만 바꿔서 target으로 바뀌는 최소한의 변환절차를 카운팅 해서 returnbfs로 풀어도되고 dfs로 풀어도되는데 필자는 dfs로 풀었습니다#include #include #include using namespace std;int answer = 0;vector checked(51, 0); //방문여부void DFS(int count, const string& current, const string& target, const vector& words){ //다른 글자수 찾기 for (int i = 0; i words){ DFS(0, begin, target, words); return a..

그래프는 정점과 간선으로 이루어져있다정점 (Vertex) 는 노드라고 불리며 그래프를 형성하는 기본 단위이다간선 (Edge)는 정점을 잇는 선을 의미한다. 관계 가 간선의 경우이다 방향 그래프노드 A와 B를 잇는 간선이 한방향으로만 갈수 있을때 방향 그래프라고함 양방향 그래프 노드 A와 B를 잇는 간선이 양 방향으로 갈수 있을때 양방향 그래프라고 함 가중 그래프간선에 가중치가 부여되며 이러한 그래프를 가중 그래프라고 한다 그래프의 순회그래프의 순회에는 크게 DFS, BFS 가 있다 그래프의 최단 경로 알고리즘크게 벨만-포드, 다익스트라, 플로이드-워셜 이 있다 사이클이 없는 방향 그래프 (DAG)그래프에서 정점 A와 B중에 누가 먼저냐고 대한 답을 할수없다배열인 경우에는 인덱스가 낮은값이 먼저라고 할수..

자료구조데이터를 효과적으로 관리하기위한 구조와 알고리즘 사용하는 이유 : 특정연산 ( 삽입, 삭제, 검색 ) 등을 효율적으로 수행하여 메모리를 최적으로 활용 사용되는 자료구조 : 배열, 스택, 큐, 리스트, 트리, 그래프, 해시 테이블, 맵 , 셋, 우선순위큐, 힙 등등이 있다배열 (Array)같은 타입으로 된 여러 객체를 한번에 다루고자 할때 사용고정된 크기를 가지는 선형 자료구조이다 #include using namespace std;int main(void){ array testArr = { 1, 2, 3, 4 };} 동적 배열 (Dynamic Array) Vector크기가 동적으로 조절 가능한 선형 자료구조중간 삽입 / 삭제 가 느리다메모리 효율이 좋고 캐시 친화적이다 (인덱스로 빠른 탐색 ..

●문제 ●입출력 문제해석 :갈수있는길 1 갈수없는길 0인 2차원배열이 주어졌을때 처음 좌상단 (0,0)에서 좌하단 목적지까지 갈수있는 최단 거리값을 return 푼 방법 : BFS를 사용하여 최단루트 계산#include#include #include using namespace std;int solution(vector > maps){ //0 -> 벽 / 1 -> 갈수있는길 //start는 왼쪽상단 (1,1) 도착은 우측하단 (n,m) 도착할수없으면 -1 최소값 return //최단거리문제 -> bfs문제 (queue) //(x좌초, y좌표), 현재까지 이동한 걸음 수) queue , int>> q; //visited이름의 2차원 배열 만들기 행 : maps.size() (행의갯수) , 열 : maps[..

●문제 ●입출력 문제이해 : 문제를 이해하는데 꽤나걸렸다 이차원 배열 computer의 숫자가 의미하는건[[1, 1, 0], [1, 1, 0] ,[0, 0, 1]]이 의미하는건 //1번 컴퓨터는 자기자신, 2번연결 o / 3번연결 x [1, 1, 0] //2번 컴퓨터는 자기자신, 1번연결 o / 3번연결 x [1, 1, 0] //3번 컴퓨터는 자기자신, 1번연결 x / 2번연결 x [0, 0, 1] 을 의미한다 네트워크의 갯수는 독립적으로 [1,2] 는 네트워크 연결되었음으로 한개[3] 은 서로 연결안되어있음으로 독립적으로 한개 이렇게 총 두개이다 문제풀이 : dfs로 서로 연결되어있거나 방문하지않았을때 dfs 재귀호출을 하였다#include #include #include using namespace ..

●문제 ●입출력 문제해석 : numbers에 있는 숫자들로 더하거나 빼서 target숫자를 만들수있는 경우의수를 return푼방법 : dfs 재귀함수를 사용하여 ind 현재 처리중인 숫자 인덱스와 dfsSum 누적 합을 매개변수로 가지고 계산주의할점 : 문제에서 주어진 numbers는 vector이니 그냥 값을 dfs에서 복사하면 너무 많이 복사하니vectornumbers는 &참조로 가져오고 int같은 작은 변수값은 그대로 복사해도 무방#include #include #include using namespace std;int answer = 0;//ind -> 몇번째 숫자를 처리중인가 , dfsSum -> 누적 합void DFS(int ind, vector& numbers, int target, int ..

DFS (Depth First Search) 깊이 우선 탐색 동작방식구현방식재귀함수 혹은 스택 으로 구현 구현순서 1. 탐색 시작 노드를 스택에 삽입한뒤 방문(Visited)여부 체크2. 1번노드에서 인접한 노드중 가장 작은 곳 2번 방문 ->2번노드에서 인접한노드3 방문 ->인접한노드 4 방문 -> 깊은 노드가 없으므로 1번으로 복귀3. 1번노드에서 가보지 않은 더 깊은 노드는 5번 5번 노드로 방문--이후 반복-- 규칙1. 가보지 않은 더 깊은 노드가 있다면 숫자가 작은 곳을 우선시하며 방문2. 더이상 가보지 않은 더 깊은 노드가 있다면 이전 노드로 돌아간다3. 방문 가능한 모든 노드를 방문할 떄 까지 반복한다. 주의할점노드 방문시 방문 여부를 반드시 검사해야한다그렇지 않으면 무한루프에 빠질수 있다 ..

●문제●입출력 문제풀이 : 가로길이, 세로길이의 지갑이 주어질때 최소한의 지갑 크기를 return푼방법 : 세로 > 가로 일때 서로 swapswap한뒤 가로와 세로의 가장 큰값을 서로 곱한뒤 값을 return#include #include #include using namespace std;int solution(vector> sizes) { //가로와 세로중에 세로가 더 길다면 해당 번호의 위치를 swap 즉 가로 레벨 : 1점수 : 1-----후기 : 분명 완전탐색 알고리즘에 있는 문제인데 그리디 문제같다 이게 왜 완전탐색 문제인가..???

●문제 ●입출력 사용 알고리즘 : DFS, 백트래킹, 완전탐색문제풀이 : dungeons에는 첫번째로 최소 필요 피로도, 두번째로 소모 피로도가 주어짐k가 내가 가진 피로도, k현재피로도에서 최소 필요 피로도가 충족되면 던전을 사용가능던전 사용뒤에는 소모 피로도를 깎음 푼방법 : DFS를 사용하여 재귀함수로 k - dungeons[i][1] 만큼 뺀뒤 클리어를 +1백트래킹을 사용하여 방문여부를 관리#include #include #include using namespace std;int dfs(int k, vector> dungeons, vectorvisited, int clear){ int result = clear; for (int i = 0; i k) continue; //..

●문제●입출력 사용 알고리즘 : 완전탐색문제해석 : 갈색(brow), 과 노랑색(yellow)가 주어졌을때 갈색으로 둘러쌓인 노란색 도형을 만들때나올수있는 가로 세로 값을 return푼방법 : 전체넓이를 구한다전체넓이 = 갈색 + 노란색가로 길이는 세로 길이보다 같거나 길기때문에 세로는 최소 3칸이 되어야지만 조건을 충족함( 가로 - 2 ) + (세로 - 2) 는 노란색이다#include #include #include using namespace std;vector solution(int brown, int yellow) { int area = brown + yellow; for (int height = 3; height 점수 : 1레벨 : 2