6.26 13시 알고리즘 스터디 (1회차)
정리

시간복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수입니다.
연산횟수 = 알고리즘 시간 복잡도 * 데이터의 크기(가장 클 때 = 최악일 때)

배열과 리스트

리스트

값과 포인터를 묶은 노드를 포인터로 연결한 자료구조

특징

1. 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근 --> 속도느림
2. 포인터로 연결되어 있으므로 데이터 삽입 및 삭제하는 연산 속도 빠름 --> 중간에 데이터 삽입 및 삭제가능 (배열은 크기를 지정해주면, 바꿀 수 없음)
3. 다시말해, 리스트는 배열과 다르게 크기를 별도로 선언해주지 않아도 됩니다.
   --> 리스트의 크기는 정해져 있지않고, 크기가 변하기 쉬운 데이터를 다룰때 적합
   이유: 포인터로 연결되어있기 때문에.
4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함

[문제 1]

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String sNum = br.readLine();
char[] cNum = sNum.toCharArray();
int sum = 0;
for (int i = 0; i < cNum.length; i++) {
sum += cNum[i] - '0';
}System.out.print(sum);}}

구간 합

구간 합의 알고리즘은 먼저 합 배열을 구한 후, 배열 A가 있을 때 배열 S는
S[i]=A[0]+A[2]...+A[i-1]+A[i]

합배열 공식

S[i]= S[i-1]+A[i]

구간 합 공식

S[j]-S[i-1]

문제순서

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
이 순서대로 문제 푸시면 구간 합 part 알고리즘을 어느정도 깨우쳤을 것입니다.

형 변환

String -> 숫자형(int,double,float,long,short)

String sNum = "1234";

int i1 = Integer.parseInt(sNum);
int i2 = Integer.valueOf(sNum);

double d1 = Double.pasreDouble(sNum);
double d2 = Double.valueOf(sNum);

float f1 = Float.parseFloat(sNum);
float f2 = Float.valueOf(sNum);

long l1 = Long.parseLong(sNum);
long l2 = Long.valueOf(sNum);

short s1 = Short.parseShort(sNum);
short s2 = short.valueOf(sNum);

숫자형 -> String 형

int i= 1234;
String i1 = String.valueOf(i);
String i2 = Iteger.toString(i);

double d = 1.234;
String d1 = String.valueOf(d);
String d2 = Double.toString(d);

float f = (float)1.234;
String f1 = String.valueOf(f);
String f2 = Float.toString(f);

long l = 1234;
String l1 = String.valueOf(l);
String l2 = Long.toString(l);

short s =1234;
String s1 = String.valueOf(s);
String s2 = Short.toString(s);