목록코딩테스트 | 자료구조 | 알고리즘 (10)

Run with coding

누구나 자료 구조와 알고리즘 | 일상적인 코드 속 빅 오 | Javascript로 배열에 들어 있는 1의 개수 반환하기

이 글은 반드시 끝까지 읽어야 한다! 아주 중요한 내용이 끝에 나오기 때문이다. ✔️ 세기 💡 배열들의 배열을 받고, 이 배열의 안쪽 배열들은 다수의 1과 0으로 이뤄진다. 함수는 배열들에 들어 있는 1의 개수를 반환한다. 예시) 입력 : 아래와 같이 입력된다. 출력 : 1이 7개 있음 = 7 ✔️ 문제 풀이 코드 자, 저번 글을 읽었는데도 이 코드가 O(N^2)로 보인다면 다시 생각해보고 와라. 자세히 보면 아름답..아니 O(N)인 걸 알아채야 한다. forEach()가 중첩 루프로 돌고 있지만 사실 outer_array보다 inner_array 루프가 핵심이란 말이다! 위 예시로 설명을 해보겠다. [0, 1, 1, 1, 0] = 5개 [0, 1, 0, 1, 0, 1] = 6개 [1, 0] = 2개 즉..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 20. 09:00
누구나 자료 구조와 알고리즘 | 일상적인 코드 속 빅 오 | Javascript로 의류 상표 만들기

이 글은 반드시 끝까지 읽어야 한다! 아주 중요한 내용이 끝에 나오기 때문이다. ✔️ 의류 상표 💡 의류 업체가 쓸 소프트웨어를 작성 중이라고 가정하자. (문자열에 저장된) 새로 생산한 의류 품목 배열을 받아 상표에 넣어야 할 텍스트를 생성해야 한다. 즉, 상표에는 품명과 1부터 5까지의 사이즈가 들어가야 한다. 아래 예시를 참고하자. 예시) 입력 : 새로 생산한 의류 품목 배열 ['Purple Shirt', 'Green Shirt'] 출력 : 아래와 같이 출력되면 됨 말만 길었지 막상 풀어보고 나니 정말 별거 아니다! 하지만 이 문제의 핵심은 빅 오를 어떻게 표기하냐다. 코드를 보면 중첩 루프가 보이기 때문에 O(N^2)으로 착각하기 쉽다. 사실은 이 코드의 단계 수(빅 오)는 O(N)이라는 것이 핵심..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 19. 09:00
누구나 자료 구조와 알고리즘 | 일상적인 코드 속 빅 오 | Javascript로 평균 섭씨 온도 구하기

✔️ 평균 섭씨 온도 구하기 💡 나는 일기 예보 소프트웨어를 개발 중이다. 도시의 온도를 알려면 도시에 퍼져 있는 수많은 온도계에서 온도를 읽어 그 온도들의 평균을 구해야 한다. 온도는 섭씨와 화씨 둘 다로 표시하고 싶으나 읽을 때는 화씨다. 섭씨 온도 평균을 구하기 위해 알고리즘은 두가지 일을 한다. 1. 화씨 온도를 섭씨로 변환한다. 2. 섭씨 온도의 평균을 계산한다. 위 코드의 단계 수(빅 오)는 N + N = 2N = O(N)이다. for문 하나가 원소의 개수 N만큼 순회하는 것이 2개가 있음으로 N + N인 것이다. 👉🏻 빅 오가 아직 이해가 안된다면 이 글을 읽어보자! 저번 '단어 생성기' 알고리즘 구현했을 때도 for문이 두 개였는데 빅 오가 O(N^2)이였다. 그때는 중첩 루프였기 때문에 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 18. 09:00
누구나 자료 구조와 알고리즘 | 일상적인 코드 속 빅 오 | Javascript로 단어 생성기 만들기

✔️ 단어 생성기 💡 문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다. 예를 들어 ['a', 'b', 'c', 'd'] 라는 배열이 주어지면 아래와 같은 문자열 조합을 포함하는 새 배열을 반환한다. for문이 중첩되어 있음으로 빅 오는 O(N^2)이 된다. 💡 그렇다면 세 글자짜리 모든 문자열 조합을 계산하도록 알고리즘을 수정하면 어떻게 될까? for문이 3개나 중첩되어 있으니 빅 오는 O(N^3)이다. 아마 엄청나게 무시무시한 알고리즘이라는 것을 눈치챘을 것이라고 생각한다. (당연히 안 좋은 쪽으로..) ✔️ O(N^3) vs O(N^2) 의 차이 N이 커질수록 N^3과 N^2 속도 차이는 어마무시하다. 그니까 내가 O(N^3)였던 알고리즘을 O(N^2)으로 코드를 최적화시켰다면 기..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 16. 09:00
누구나 자료 구조와 알고리즘 | 일상적인 코드 속 빅 오 | Javascript로 짝수의 평균 구하기

✔️ 들어가기 전.. O(N^2) : 알고리즘이 "느리다"로 간주한다. 👉🏻즉, 더 빠른 대안, 최적화할 방법이 있는지 분석하라는 신호다! 아래의 문제들은 모두 Javascript로 풀었으니 다른 언어를 원한다면 다른 글을 찾아보자.. ✔️ 짝수의 평균 구하기 💡 수 배열을 받아 모든 짝수의 평균을 반환하자. 위 코드의 최악의 경우 빅 오 : 3N + 3단계 = O(3N + 3) = O(N) 👉🏻 빅 오 표기법은 상수를 무시한다. 자세한 내용은 이 글을 확인해보자!
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 15. 09:00
누구나 자료 구조와 알고리즘 | 긍정적인 시나리오 최적화 | 삽입 정렬 알고리즘

✔️ 삽입 정렬 1. 인덱스 1의 값을 변수에 담아둔다. 2. 왼쪽의 값과 변수에 담아둔 값을 비교한다. 3. 왼쪽 값이 더 크다면 오른쪽으로 쉬프트, 작다면 해당 패스스루 끝내기 4. 쉬프트하여 빈 자리에 변수로 담아둔 값을 넣는다. 5. 마지막 인덱스까지 반복 ✔️ 삽입 정렬 코드 구현 ✔️ 삽입 정렬의 효율성 원소가 N개인 배열 비교 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 시프트 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교 삭제 : N-1번 삽입 : N-1번 총 단계 수 : N^2 + 2N - 2단계 원소가 5개인 배열 비교 : 1 + 2 + 3 + 4 = 10번 시프트 : 1 + 2 + 3 + 4 = 10번 삭제 : 4번 삽입 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 6. 14. 14:45
누구나 자료 구조와 알고리즘 | 빅 오를 사용하거나 사용하지 않는 코드 최적화 | 선택 정렬

✔️선택 정렬 선택 정렬 방법 앞에서부터 순서대로 돌면서 최솟값이 있는 인덱스를 변수에 저장 다 돌았을 때 시작 인덱스와 변수에 저장된 인덱스의 값을 바꾼다. 배열 끝에서 시작하는 패스스루에 도달할 때까지 계속 반복 선택 정렬 실제로 해보기 선택 정렬의 효율성 버블 정렬의 단계 수 / 2 = 선택 정렬의 단계 수 즉, 선택 정렬의 단계 수는 O(N^2) / 2이다. 상수 무시하기 O(N^2 / 2) 이지만 빅오 표기법은 상수를 무시한다. 즉, /2를 버리고 O(N^2)로 표기한다. 그래서 버블 정렬과 선택 정렬의 실제 성능 차이는 크지만 빅 오 표기법만 봤을 땐 둘의 단계 수가 같다. 👉🏻 빅오만 보고 성능을 판단하기 쉽지 않다는 뜻이다. 빅 오의 또 다른 개념 빅 오 표기법은 일반적인 카테고리의 알고리..
코딩테스트 | 자료구조 | 알고리즘 2023. 5. 20. 09:00
누구나 자료 구조와 알고리즘 | 빅 오 표기법 | 빅 오로 코드 속도 올리기

✔️버블 정렬 : 매우 기본적인 정렬 알고리즘 버블 정렬 방법 배열의 첫 번째 원소부터 다음 원소와 비교하며 오른쪽 값이 더 크면 두 항목을 교환 교환이 일어나지 않는 패스스루가 생길 때까지 반복 버블 : 각 패스스루마다 정렬되지 않는 값 중 가장 큰 값 버블 정렬 실제로 해보기 버블 정렬의 효율성 버블 정렬 알고리즘 = 비교 + 교환 ex) 원소가 5개라면.. ⇒ 총 20단계 비교 : 4 + 3 + 2 + 1 = 10번 교환 : 4 + 3 + 2 + 1 = 10번 ex) 원소가 10개라면.. ⇒ 총 90단계 비교 : 9 + 8 + 7 + … + 1 = 45번 교환 : 9 + 8 + 7 + … + 1 = 45번 ex) 원소가 20개라면.. ⇒ 총 380단계 비교 : 20 + 19 + 18 + … + 1 ..
코딩테스트 | 자료구조 | 알고리즘 2023. 5. 19. 09:00
이전 Prev 1 2 Next 다음