SW 공부노트

반복 불필요한 조건문 실행 횟수 줄이기 - 실습 1-10(식 마지막에 등호를 붙이기 위해 n번의 조건문 실행) - 실습 1-11(+, - 번갈아 출력 시 홀수, 짝수 분별위해 n번의 조건문 실행) 위와 같은 실습의 경우, 반복할 때마다 조건문을 실행해야 한다는 부담이 있다. 등호를 마지막에 붙이고, +-를 붙여 출력하는 식으로 수정하면 조건문 실행횟수나 연산 횟수를 줄일 수 있다. 이중 반복문의 경우 외부 반복문이 행, 내부 반복문이 열 내부 반복문의 초기값 및 조건문을 i로 두어 조합 등을 처리할 수 있다. 배열/클래스 배열 길이 = arr.length / 배열 기본값 = 0 기수 변환 소수 판별 -> 정수 n의 소수여부 판별 루트(n)(n 제곱근)이하의 어떤 수(소수)로도 나누어떨어지지 않는다. n-..

동적 프로그래밍(Dynamic Programming)이란? 동적 프로그래밍이란 큰 문제를 작은 문제로 나누어 푸는 문제를 말하며, 작은 부분문제들이 반복되는 것을 이용해 풀어나가는 방법이다. 모든 작은 문제들은 한번만 풀어야 한다. 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 미리 구해놓은 작은 문제의 결과값을 이용한다. 동적 프로그래밍과 일반적인 재귀방식은 매우 비슷하다. 큰 차이점은 일반적인 재귀를 단순하게 사용했을 경우 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 이 차이점이 바로 동적 프로그래밍을 사용하는 이유이다. 동적 프로그래밍을 사용하면 앞서 계산된 값을 다시 반복할 필요가 없어 매우 효율적으로 문제를 해결할 수 있게 된다. 동적 프로그래밍의 조건은..

그래프 관련 문제를 풀던 중 다익스트라(Dijkstra) 알고리즘을 활용한 문제를 풀게 되어 문제 풀이와 함께 알고리즘을 정리해보려 한다. 문제는 백준 1753번(최단경로)으로 다익스트라(Dijkstra)알고리즘 그대로 풀면 되는 문제이지만 생각보다 난이도가 있었다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라(Dijkstra)알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하..

BFS, DFS는 여러 그래프 탐색 문제를 해결할 때 가장 흔히 사용되는 알고리즘들 중 하나이다. 그래프 탐색 문제란 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 정점들을 모두 찾아야 하는 문제를 말한다. 1. 깊이 우선 탐색(Depth First Search) 깊이 우선 탐색(DFS)은 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색한다. 알고리즘의 개요는 시작점에서 시작점에 연결된 정점 -> 위 정점에 연결된 정점 ... 식으로 해당 브랜치에 연결된 간선이 없을 때까지 탐색한 후 다시 되돌아가 방문하지 않은 정점이 없을 때까지 위 방식을 반복하게 된다. (1) 깊이 우선 탐색 구현 DFS를 구현할 때는 직전에 방문했던 정..