코딩테스트

[Java/백준] 주몽 #1940

문제 풀이 (1) 문제 분석하기 두 재료의 번호의 합, 크기를 비교하므로 먼저 정렬하고 시작 N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘(=정렬 알고리즘)을 사용해도 문제없음 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 접근(데이터가 유니크하고 한 번 쓰면 없어진다? → 투 포인터) (2) 손으로 풀어 보기 재료 데이터를 A[N]에 저장한 후 오름차순으로 정렬 투 포인터 i, j를 양쪽 끝에서부터 포인터 이동 원칙에 맞게 탐색 2단계를 i와 j가 만날 때까지 반복, 반복이 끝나면 count 출력 (N번만에 탐색이 끝남, 투 포인터는 시간 복잡도에 영향이 거의 없음) // 투 포인터 이동 원칙 A[i] + A[j] > M : j--; // 번호의 합이 M보다 크면 큰 번호..

[Java/백준] 연속된 자연수의 합 구하기 #2018

문제 풀이 (1) 문제 분석하기 N의 최댓값(10,000,000)이 매우 크므로 O(n)의 시간 복잡도 알고리즘 사용해야 함 → 투 포인터! 시작 인덱스와 종료 인덱스를 투 포인터로 지정하여 접근 (2) 손으로 풀어 보기 N값을 입력받아 변수에 저장하고, 사용할 변수(sum, count, start_index, end_index) 모두 1로 초기화 (count를 1로 초기화하는 이유는? 연속된 수가 자기 자신인 경우를 미리 포함한 것) 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구함 2단계를 end_index가 N이 될 때까지 반복 포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count를 1만큼 증가 // 투 포인터 이동 원칙 sum > N : s..

[Java/백준] 구간 합 구하기 #11659

문제 풀이 (1) 문제 분석하기 수의 개수 N과 합을 구해야 하는 횟수 M은 최대 100,000 임 최악의 경우, 1억 회 이상 연산을 해야 하므로 1초 안에 계산을 끝낼 수 없음 → 구간 합 사용! (2) 손으로 풀어보기 // 합 배열 공식 S[i] = S[i-1] + A[i] // 구간 합 공식 S[j] - S[i-1] N개의 수를 입력받으면서 바로 합 배열 생성 i부터 j까지 구간 합 공식으로 정답 출력 배열의 index는 0부터, 합 배열의 index는 1부터 시작한다는 것에 주의하기! (3) 슈도코드 작성하기 N(숫자의 개수), M(질의 개수) 저장하기 for(1부터 N 까지) { 합 배열 생성하기(S[i] = S[i - 1] + A[i] } for(0부터 M 전까지) { 질의 범위 받기(i ~..

[TIL] 알고리즘 구간 합

✍ Today I Learned 구간 합 구간 합이란? 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 구하기 // 배열 A가 있을 때 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 // 합 배열을 만드는 공식 S[i] = S[i-1] + A[i] 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 구간 합 구하기 // 구간 합 구하는 공식 S[j] - S[i-1] // i에서 j까지 구간 합 // A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정 S[5] = A[0] + A[1] + A[2] + A[..

[Java/백준] 평균 구하기 #1546

문제 풀이 (1) 문제 분석하기 모든 점수를 입력받은 후, 최고점 별도로 저장해야 함 최고점으로 다시 계산해야 하는 변환 점수는 계산식을 정리하면 한 번에 평균을 구할 수 있음 ( A / M * 100 + B / M * 100 + C / M * 100 ) / 3 = ( A + B + C ) * 100 / M / 3 (2) 손으로 풀어보기 모든 점수를 1차원 배열에 저장 최고 점수와 점수의 총합을 구함 '총합 * 100 / 최고 점수 / 과목 수'를 계산 (3) 슈도코드 작성하기 변수 N에 과목의 수 입력받기 길이가 N인 1차원 배열 A[] 선언하기 for(A[] 길이만큼) { A[i]에 각 점수 저장하기 } for(A[] 길이만큼) { 변수 max에 최고 점수, 변수 sum에 총합 저장하기 } sum *..

[TIL] 알고리즘 배열과 리스트(Java)

✍ Today I Learned 배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스를 사용하여 값에 접근 선언한 자료형의 값만 저장 가능 배열의 크기는 선언할 때 지정, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하려면 해당 인덱스 주변에 있는 값을 이동시켜야함 구조가 간단하므로 코딩 테스트에서 많이 사용 리스트 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 인덱스가 없으므로 접근하려면 Head 포인터부터 순서대로 접근 → 값에 접근하는 속도가 느림 포인터로 연결되어 있어 데이터를 삽입하거나 삭제하는 연산 속도 빠름 선언할 때 별도의 크기 지정 필요X, 크기가 변하기 쉬운 데이터 다룰 때 적절 포인터를 저장..

[TIL] 알고리즘 디버깅(Java)

✍ Today I Learned 디버깅은 왜 중요할까? 디버깅이란? 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정 알아두기만 하는 것이 아니라 문제를 풀면서 반드시 해야 하는 과정 디버깅하는 법 디버깅하고자 하는 줄에 중단점 설정(여러 개 가능) IDE의 디버깅 기능 실행 → 코드를 1줄씩 실행(step over) or 다음 중단점까지 실행 추적할 변숫값을 지정하거나 원하는 수식을 입력해 의도하는 대로 작동하는지 파악 디버깅 활용 사례 코딩 테스트를 진행하며 실수하기 쉬운 4가지 오류 변수 초기화 오류 반복문에서 인덱스 범위 지정 오류(로그를 사용하면 계속 다시 실행해야 하기 때문에 시간이 많이 걸림) 잘못된 변수 사용 오류 자료형 범위 오류(이건 답이 음수가 나올 수 없는데..? →..

[TIL] 알고리즘의 시간 복잡도(Java)

✍ Today I Learned 시간 복잡도 표기법 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수 일반적으로 1억 번의 연산 = 1초의 시간으로 간주하여 예측 시간 복잡도를 정의하는 3가지 유형 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 (1번) 빅-세타 : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 (2/n번) 빅-오 : 최악 일 때(worst case)의 연산 횟수를 나타낸 표기법 (n번) 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 왜? 모든 테스트 케이스를 통과해야 하기 때문 시간 복잡도 활용 알고리즘 선택의 기준으로 사용하기 문제에서 주어진 시간제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘..