탁월함은 어떻게 나오는가?

문제 설명틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다. 할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.- 혼자서 선공과 후공을 둘 다 맡는다.- 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다. 틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린뒤 다시 게임을 반복했습니다. 그렇게..

문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 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 항목이 정렬된 상태이다. 카드게임을 할때와 유사하게 생각하면 좋다. 새로운 카드를 뽑을 경우 정렬된 카드 사이에 올바른 자리에 삽입하는 원리이다. 삽입 정렬 알고리즘의 동작 원리 - 상입 정렬은 두 번째 값을 시작으로 첫 번째 값과 비교한다. 비교 후에 삽입할 위치를 지정한 후 값을 알맞는 자리에 삽입하여 정렬한다. - 즉, 두 번째 값을 첫 번째 값과, 세 번째 값은 두 번째, 첫 번째 값과 네 번쨰 값은 세 번째, 두 번째, 첫 번째 값과 비교한다..