알고리즘 코딩 테스트 2일차
03-1 배열과 리스트
- 배열
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조.
배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.
배열의 특징
- 인덱스를 사용하여 값에 바로 접근할 수 있다.
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
값을 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요함.
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
- 구조가 간단하므로 코딩 테스트에서 많이 이용됨.
- 리스트
값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조.
리스트의 특징
- 인덱스가 없으므로 값에 접근하려면 Head 포인터 순서대로 접근해야 한다.
다시 말하면 접근하는 속도가 느리다.
- 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
- 선언할 때 크기를 별도로 지정하지 않아도 된다.
다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
- 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.
11720 숫자의 합 구하기
시간제한 1초 브론즈 2문제
1) 문제 분석하기
문자열 형태로 입력값 받기 → 문자 배열로 변환 → 문자 배열값을 순서대로 읽으면서 숫자형으로 변하여 더한다.
2) 손으로 풀어보기
ⓐ 숫자의 개수만큼 입력받은 값을 String형으로 저장한다.
ⓑ String형으로 입력받은 값을 char []형으로 변환
ⓒ 인덱스 0부터 끝까지 배열을 탐색하며 각 값을 정수형으로 변환하고 결괏값에 더하여 누적
✅ 자바에서의 형변환
step1. String형 → 숫자형(long)
String sNum = "1234"; //String형 변수
long l1 = Long.parseLong(sNum); // 기본 자료형(primitive type)
long l2 = Long.valueOf(sNum); // 객체 반환
/* 문자열을 반환할 때 기본자료형이 아닌 객체로 받아오고 싶을 때는 valueOf 사용하기 */
step2. 숫자형 → String형
int i = 1234;
String i1 = String.valueOf(i);
String i2 = Integer.toString(i);
/*
toString을 사용했을 때, null값을 문자열로 형 변화시 NullPointException이 발생
하지만 String.valueOf()를 사용하면 파라미터값이 null일 때 "null"을 반환
String.valueOf() << 사용하기
*/
1546 평균 구하기
1) 문제 분석하기
모든 점수 입력받기 (이 때 최고점은 따로 입력) → 문제에서 제시한 한 과목의 점수를 계산하는 식은 총합과 관련된 식으로 변환
M = 제일 높은 점수, 각각 a, b, c는 점수들이라고 가정(과목 수가 3개니까 3으로 나눔)
(a / M * 100 + b/ M * 100+ c/M*100)/ 3 = average
이는 아래 수식으로 바꿀 수 있음
(a+b+c)*100/M/3 =average
2) 손으로 풀어보기
ⓐ 점수를 1차원 배열에 저장
ⓑ 배열을 탐색 최고점수와 점수의 총합 구하기
ⓒ 총합 * 100 / 최고 점수 / 과목의 수 계산 후 평균값 출력
03-2 구간 합
합 배열 S 정의
S[i] = A[0] + A[1] + A[3] + ... + A[i-1] + A[i]
// A[0]부터 A[i]까지의 합
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
//S[i-1] 이전값
//A[i] 현재 인덱스의 배열값
구간 합을 구하는 공식
S[j] - S[i-1] //i에서 J까지 구간 합
A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]
참고자료 - Do it! 알고리즘 코딩 테스트 자바편