알고리즘

[TIL] 1주차 알고리즘ㅣ주간 시작

알고리즘 주간 시작 4일간의 폭풍 같았던 미니 프로젝트가 끝나고, 오전 9시 발제를 기준으로 알고리즘 주간이 시작되었다. 걷기반과 달리기반으로 나뉘는데 나는 패기 넘치게 달리기반을 선택했다. 마라톤 24문제 + 챌린지 16문제와 함께 할 일들이 쏟아졌다. 오늘 자정까지 주특기 언어 과제 제출 내일 1시 문제풀이 세션 다음 주 화요일 알고리즘 모의고사 다음 주 목요일 알고리즘 테스트 내가 팀장이라니 한 번쯤은 팀장을 할 것 같았지만 막상 팀장이 되니 괜히 무게가 느껴진달까.. 새롭게 만난 팀원분들과 이번 주도 잘 헤쳐나갈 수 있으면 좋겠다. 오늘의 나는 오늘 하루만 약 10개의 알고리즘 문제를 풀었다. 타입을 변환하는 부분이나 Array, ArrayList 등 자료구조를 활용하는 부분이 아직 많이 부족하다..

[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가지 오류 변수 초기화 오류 반복문에서 인덱스 범위 지정 오류(로그를 사용하면 계속 다시 실행해야 하기 때문에 시간이 많이 걸림) 잘못된 변수 사용 오류 자료형 범위 오류(이건 답이 음수가 나올 수 없는데..? →..