일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- 자바스크립트
- 채권
- 지혜를가진흑곰
- 알고리즘공부
- 재테크
- 책알남
- 프로그래머스 알고리즘 공부
- 독후감
- 백준알고리즘
- 프로그래밍언어
- 경제
- 서평
- 자바
- 투자
- C++
- algorithmStudy
- 책을알려주는남자
- 알고리즘 공부
- 다독
- 주식
- 독서
- 알고리즘트레이닝
- algorithmtraining
- 화장품
- Java
- JavaScript
- C
- 성분
- 돈
- algorithmTest
- Today
- Total
목록[Snow-ball]프로그래밍(컴퓨터)/Algorithm (9)
탁월함은 어떻게 나오는가?
문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe"선수가 1등, "mumu" 선수가 2등으로 바뀝니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players 와 해설진이 부른 이름을 담은 문자열 배열 callings 가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요. 문제 풀이 1..
[개념과 원리] 최대 용량 M인 하나의 배낭과 n개의 물체가 있고, 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pi가 부여되었다고 가정한다. 배낭(kanpsack) 문제는 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제이다. 여기서는 물체를 쪼개서 넣을 수 있다고 가정한다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include using namespace s..
for문에서 ++i와 i++의 차이는 속도이다. 내부 operator 로직을 보면 i++ 연산이 한번 더 연산을 거치게 된다. 물론 요즘 컴파일러와 하드웨어가 워낙 빨라져서 거의 차이가 없지만 ++i가 미세하게 빠르다. 코드로 확인해보자. C계열에서 확인해보면 i++의 경우에 임시 변수를 생성하기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1) ++i 의 경우 for (int i = 0; i
알고리즘의 시간 복잡도 중에서 자주 접할 수 있는 형태를 정리한 것이다. O(1) : 상수 시간 알고리즘(Constant-time algorithm)의 수행 시간은 입력의 크기에 영향을 받지 않는다. 상수 시간 알고리즘의 예로는 공식을 이용하여 답을 바로 계산해내는 알고리즘이 있다. O(log n) : 로그 시간 알고리즘(Logarithmic algorithm)은 대체로 단계마다 입력의 크기를 절반씩 줄여 나간다. n을 계속 2로 나눠가면서 1이 되도록 하는 데에 필요한 단계 수는 log2 n이고, 따라서 이러한 알고리즘의 수행 시간은 로그 시간이다. 로그의 밑수가 시간 복잡도에 나타나 있찌 않음을 유의하라. O(로그 n) : 제곱근 시간 알고리즘(Square root algorithm)은 O(log n..
퀵 정렬(Quick Sort) 알고리즘 개념 - 퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. - 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. - 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. - 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. ..
퀵 정렬(Quick Sort) 알고리즘 개념 - 퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. - 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. - 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. - 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. ..
삽입 정렬(Insertion Sort) 알고리즘 개념 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 카드게임을 할때와 유사하게 생각하면 좋다. 새로운 카드를 뽑을 경우 정렬된 카드 사이에 올바른 자리에 삽입하는 원리이다. 삽입 정렬 알고리즘의 동작 원리 - 상입 정렬은 두 번째 값을 시작으로 첫 번째 값과 비교한다. 비교 후에 삽입할 위치를 지정한 후 값을 알맞는 자리에 삽입하여 정렬한다. - 즉, 두 번째 값을 첫 번째 값과, 세 번째 값은 두 번째, 첫 번째 값과 네 번쨰 값은 세 번째, 두 번째, 첫 번째 값과 비교한다..
버블 정렬(Bubble Sort) 알고리즘의 개념 - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 > 인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. - 선택 정렬과 기본 개념이 유사하다. 버블 정렬 알고리즘의 동작 원리 - 버블 정렬은 첫 번째 값과 두 번째 값을, 두 번째 값과 세 번째 값을 ... 마지막( - 1)값과 마지막 값을 비교하여 자료를 정렬하는 알고리즘이다. - 처음 돌고나면 제일 큰값이 맨 뒤로 이동하게 되며, 2번째돌면 2번째로 큰값이 마지막 - 1 값 위치에 정렬되고 이를 N의 값만큼 전부 수행하게 된다. 이미지로 보는 동작 절차 1) 1번 값과 2번 값을 비교 후 1번 값이 크다면 1번 값과 2번 값의 자리를 바꾼다. 2) 2번 값과 3번 값을 ..