NaEun's Notes

[BAEKJOON / Java] 10807. 개수 세기

Question https://www.acmicpc.net/problem/10807Algorithm정수 N을 입력받는다.이후 각 숫자들을 분리하여 저장할 배열의 크기를 지정할 때 사용정수 N개가 공백으로 구분된 한 줄 입력을 읽는다.StringTokenizer를 사용해 입력된 숫자들을 하나씩 분리하여 배열에 저장한다.arr[i] = nextToken() 방식으로 N개를 저장한다.찾고 싶은 정수 b를 입력받는다.배열을 처음부터 끝까지 순회한다.배열의 요소가 b와 같다면 count를 1 증가시킨다.모든 검사 후 count 값을 출력한다.즉, b가 배열에 몇 번 등장했는지 출력한다.입출력 스트림을 정리하고 종료한다.Codeimport java.io.*;import java.util.StringTokenizer..

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)