문제 파악https://www.acmicpc.net/problem/16953 접근 방법bfs를 통해 접근하면 어떨까?2를 곱하는 경우1을 을 수의 가장 오른쪽에 추가하는 경우두 가지의 경우의 수를 큐에 넣어 준 다음, 만약 a가 b와 같게 된다면 answer를 갱신하고, 반복문을 종료하였다.무한 루프의 반복을 막기 위해, 다음 수가 b값을 넘지 않는 조건에서만 큐에 다음 수를 넣어주었다. 코드 구현첫번째 코드(틀린 코드)import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { public static void main(String[] ar..
BFS
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 백트래킹(dp) 풀이(재귀를 활용한 풀이) import java.util.*;class Solution { String target; String [] words; int answer = Integer.MAX_VALUE; boolean [] visited; int result=0; public int solution(String begin, String target, String[] words..
문제파악https://www.acmicpc.net/problem/14888숫자가 배열로 주어지고, 연산자의 개수가 주어진다.배열 [1,2,3] 와 [1,0,1,0] -> {+:1, *:1} 이 주어졌다면, 1+2*31*2+3 총 두 가지의 식이 나올 수 있음 ! 수와 수 사이에 연산자를 넣어 나올 수 있는 답의 최댓 값과 최소 값을 구한다.연산자 우선 순위 규칙은 무시한다 ! 접근방법전형적인 재귀 문제 ! -> 백트래킹 문제 백트래킹이란? : 가능한 모든 조합을 탐색하되, 이미 잘못된 경우는 중간에 탐색을 중단하는 방식(종료 조건) 이 문제에서의 종료 조건은 n까지의 수의 연산이 끝났을 때이다.그 때, MAX_VALUE와 MIN_VALUE를 갱신시켜주고 return 해주면 된다. 코드 구현..
문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근 방법인접리스트에서 DFS를 사용하는 문제 !DFS를 통해 연결되어 있는 부분을 끝까지 가다가, 연결이 끊어진 곳에서 멈춘다. ( answer ++ )그 후 끊어진 부분 이후에도 연결되어 있는 네트워크가 존재하기 때문에 반복하여 DFS를 몇 사이클을 거쳤는지 count해주면 답이 나올 것이다. ❗DFS에서 조건 유의하기이 문제에서는1) 방문하지 않고,2) 1일 때 (연결되어 있을..
✅ 문제 링크https://www.acmicpc.net/problem/1926 ✅ 문제 파악BFS 기본 문제 (❁´◡`❁)도화지에 1로 연결된 구간(상하좌우)를 한 그림이라고 정의했을 때, 그림의 개수를 구하고, 가장 큰 그림의 넓이를 출력한다. (예외처리 필요) ✅ 접근 방법 visited -> 방문 여부를 확인하기 위한 2차원 배열 dxs, dys -> 상하좌우 방향을 표현하기 위한 리스트 can_go 함수의 조건 1. 주어진 좌표가 그래프 범위 안에 존재해야함 02. 방문하지 않았어야 함 3. graph[x][y] == 1이여야 함 bfs 함수 정의 1. queue를 만들고, 시작 좌표를 큐에 넣는다. 2. 큐가 빌 때까지 다음을 반복 - 큐에서 좌표 (a,b)를 꺼냄 -..
깊이 우선 탐색(DFS)란?: 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘→ 현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식재귀 함수로 구현스택 자료구조 이용시간 복잡도 - O( V + E ) [노드 수: V, 에지 수: E] 깊이 우선 탐색(DFS)의 핵심 이론시작점으로부터 연결된 모든 정점을 전부 방문해야 한다.이미 방문한 정점은 다시는 방문하지 않는다.N = 5 #노드 개수# 인접 리스트 만들기adj_list = [[] for _ in range(N)]adj_list[0].append(1); adj_list[0].append(2)adj_list[1].append(4); adj_..
