NaEun's Notes

Question https://school.programmers.co.kr/learn/courses/30/lessons/120897 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krAlgorithm정수 n 약수 구하기n % i == 0 이면 약수이므로 count++약수 개수만큼 크기를 가진 배열을 생성다시 1부터 n까지 반복하면서 실제 약수들을 배열에 저장n을 나누어 떨어뜨리는 숫자(i)를 배열에 순서대로 넣는다.Codeclass Solution { public int[] solution(int n) { // 약수 개수 저장할 변수 int count = 0; ..

Question https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krAlgorithm1부터 number까지 약수의 개수 구하기반복문을 이용하여 i = 1부터 number까지 순회한다.각 약수의 개수 중 limit 초과인 수는 power 로 계산divisorCount(i) 결과가 limit 이하라면 → 해당 값을 그대로 사용한다.limit 초과라면 → 약수 개수 대신 power 값을 사용한다.제곱근을 이용한 약수 개수 계산 (divisorCount 메서드)1부터 √num까지만 반복하여 시간복잡도 O(√N)..

Question https://www.acmicpc.net/problem/1152Algorithm표준 입력으로 한 줄을 입력받아 양 끝 공백을 제거한다.문자열이 빈 경우, 단어 수 0을 출력하고 프로그램을 종료한다.빈 문자열이 아니면 단어가 최소 1개 있다고 가정하고 count를 1로 초기화한다.문자열을 한 글자씩 순회하면서, 공백 문자가 나오면 count를 1 증가시킨다.순회가 끝나면 count(단어 개수)를 출력한다.Codeimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static ..

Question https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krAlgorithmf(n) = f(n-1) + f(n-2)n번째 칸에 도달하는 방법은 두 가지 경로로만 가능하다(n-1)번째 칸에서 1칸 점프(n-2)번째 칸에서 2칸 점프경우의 수n경우의 수점화식결과1(1)-12(1,1), (2)-23(1,1,1), (1,2), (2,1)f(2)+f(1)34(1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)f(3)+f(2)55...f(4)+f(3)8Codeclass Solutio..

Question https://school.programmers.co.kr/learn/courses/30/lessons/12969 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krAlgorithm첫 번째 정수 입력 : sc.nextInt()를 호출하여 사용자가 입력한 첫 번째 정수를 읽어 변수 a에 저장두 번째 정수 입력 :다시 sc.nextInt()를 호출하여 사용자가 입력한 두 번째 정수를 읽어 변수 b에 저장덧셈 연산 및 출력 : a + b를 계산한 결과를 System.out.println()을 통해 콘솔에 출력Codeimport java.util.Scanner;class Solution { public..

BFS와 최단경로 💡BFS와 최단경로BFS는 s에서 출발해서 모든 노드를 방문할 뿐만 아니라, 출발점 s에서 부터 각각의 노드까지 가는 가장 짧은 경로를 구할 수 있다.가장 짧은 경로란, 경로의 길이를 에지(edge)의 개수로 본다면 그 수가 가장 적은 경로를 의미모든 노드에 대해 최단 경로의 길이와 predecessor를 구할 수 있다.BFS 최단경로 수도코드 💡수도코드로 이해하는 BFS 최단경로 구하기입력으로 그래프 G와 출발 노드 s를 지정했다고 가정한다.BFS 구현을 위한 큐 Q를 만들어주고, Q는 비어있는 상태이다. d[s]출발점으로 부터의 최단 경로처음에는 출발점이 자신이기때문에 0π[s]특정 노드에 도착하기 직전 노드처음에는 그런 노드가 없기 때문에 null어떤 것을 Q에 넣는 것을 En..

그래프 순회 💡순회그래프의 모든 노드들을 체계적으로, 중복 없이 방문하는 것을 의미💡대표적인 순회 방법 2가지BFS (Breadth-First Search, 너비우선순회)DFS (Depth-First Search, 깊이우선순회)BFS, 너비우선순회 💡BFS, 너비우선순회노드들을 동심원의 형태로 순회하는 알고리즘즉, 출발 노드 방문 후, 출발 노드에 인전합 노드들을 다 방문하는 방식인접하다는 것은, 에지(edge)로 직접 연결되어있다는 의미 = 거리가 1인 노드거리가 1인 노드 방문 후에는 거리가 2인 노드들을 방문, 즉, 거리가 1인 노드와 또 다시 에지로 연결되는 노드들을 방문그래프의 모든 노드들을 방문하기 위해 출발 노드를 지정해줘야 한다. (위 그림에서는 s)💡Queue를 이용한 BFS우선,..

무방향 그래프 주요 용어 정리 💡경로와 연결성경로 (path)무방향 그래프에서 노드 사이의 경로라는 것은, 예를 들어, 4에서 3까지 에지(edge)들을 따라 가는 경로를 의미한다.연결두 노드 사이를 연결하는 경로가 있을 때, 연결되어있다고 말한다.ex. 위 그림에서 4와 2는 에지로 직접 연결되어있으므로 인접(adgacent)한 것이고, 4에서 7처럼 두 노드 사이에 에지들을 거쳐 도달할 수 있는 경우 연결되었다고 한다.연결된(connected) 그래프모든 노드들이 서로간 다 연결이 되어 있는 경우를 연결된 그래프라고 한다.연결 요소 (connected component)연결된 그래프 덩어리아래 그림과 같이 A, B, C가 하나의 그래프 라면, 각각의 3개의 연결요소로 구성되어있다고 한다.출처http..

무방향 그래프(Graph)의 표현 💡인접행렬 (Adjacency Matrix)정점의 개수가 n개인 그래프를 n x n 인 2차원 배열(행렬)로 표현하는 방식i 번째 행, j 번째 열을 𝑎ᵢⱼ 라고 한다면, 정점 i와 j 사이에 에지가 있으면, 1 없으면 0으로 표시한다.모든 정점 쌍에 대해서 에지가 있는지의 여부를 표로 표현할 수 있다.대칭행렬 : 대각선으로 접었을 때, 대칭이 된다는 뜻사용하는 메모리 저장 공간은 O(n2)💡인접리스트 (Adjacency List) 방향 그래프(Directed Graph)의 표현 💡인접행렬 (Adjacency Matrix) 가중치 그래프(Weighted Graph)의 표현 💡인접행렬 (Adjacency Matrix)

그래프(Graph) 💡그래프(Graph) 란?그래프(G)는 V와 E 두개의 집합에 의해 구성된다.보통 그래프라고 칭하면, 방향이 없는 그래프를 의미하는 경우가 많다.방향이 없다는 것은 순서쌍 (1, 2)와 (2, 1)을 동일한 쌍으로 본다는 것을 의미한다. = Edge의 방향이 없다.이진관계 (binary relation)두 개의 객체(정점) 사이의 관계를 순서쌍(ordered pair)으로 표현하는 수학적 개념그래프가 정점들 사이의 쌍으로 이루어진 관계를 나타낸다.이 강의에서 정점의 개수는 n으로, 에지의 개수는 m으로 표현한다.💡방향 그래프(Directed Graph) 란?에지 (u, v)와 (v, u)는 서로 다른 것이 방향 그래프이다.💡가중치 그래프(Weighted Graph) 란?가중치 그..