CodingTest

코딩테스트 기본 유형 정리

Lcoding 2024. 1. 1. 23:24
반응형

에라토스테네스의 체 - 소수구하기 // 해당 수를 제외하고 배수를 모두 지운다

아나그램 - 같은 단어로 배열만 바꾼것 [해시 + 슬라이딩윈도우 ]

팰린드롬 - 앞으로해도 뒤로해도 같은 단어 [ 문자열(StringBuilder.reverse) + replaceAll ]

최대매출 - [ SlidingWindow ] 창문 형태로 밀어내기 창문의 첫번째 값을 빼고 마지막값을 더한다 반복

배열 합치기, 공통원소 구하기 - [ twopointer ] p1,p2 혹은 lt,rt로 두가지 포인트를 잡아서 진행한다.

후위식연산 - 스택으로 넣어서 진행 먼저들어간 숫자 lt, 나중에 들어간숫자 rt로 연산

피보나치수열 - [ Array ] (i-1) + i 값은 i+2 값과 일치한다.

K번째큰수 - 중복제거가 필요할땐 HashMap이 아닌 TreeSet을 사용한다.

스택문제 - 괄호 연산 등 리포

큐문제 - 라우터문제 피포

선택정렬 - 첫번째수를 반복문으로 다음 수들과 비교하면서 제일 작은수를 첫번째 인덱스에 넣음. -> 한바퀴 돌았을때 제일 작은수가 맨앞 인덱스로 이동

버블정렬 - 첫번째수와 바로 다음수를 비교하여 큰수를 뒤로 밀음 -> 한바퀴 돌았을때 제일 큰수가 맨뒤 인덱스로 이동

삽입정렬 - i가 0이아닌 1부터 시작하며 i번째수를 tmp에 넣고 i보다 작은 인덱스들에 있는 수와 비교하여 작으면 i번째수를 i-1번째로 이동하고 tmp를 i번째에 넣음

이분탐색 - 반복문이 시간초과할때 대체할 수 있으며, 0부터 N까지 반복하는게 아니며, lt,rt,mid를 설정하여 mid값과 비교하여 크거나 작음에따라 lt,rt의 범위를 이동시켜 절반씩 줄여나간다.

재귀함수 - 본인을 호출하는 함수이며, 메서드 첫부분에 if문을 만들어서 끝나는 조건을 넣고 else일때 재귀 로직을 타게한다.

트리 - 이진트리 유형.

반응형