문제) 사람들이 일렬로 물건을 사기 위해 줄을 서있습니다. 이 때, 모든 사람들은 앞 사람들에게 돈을 주고 자리를 바꿀 수 있고, 특정 사람이 다른 사람을 매수할 수 있는 최대 횟수는 2회입니다.(즉, 자신의 자리보다 최대한 2칸까지 앞으로 갈 수 있습니다.) 숫자들의 List가 주어질 때, 매수가 일어난 최소 횟수를 구하시오.
[예시]
초기 상태 : [1, 2, 3, 4, 5]
최종 상태 : [2, 1, 5, 3, 4]
* 엄청나게 큰 Input이 테스트 항목에 있으므로, 단순히 풀기만 해서는 안됩니다.(여기서 많은 시간을 보냈습니다. 사실 답을 찾지 못해서 discussion에 들어가서 힌트를 얻었습니다 ㅠㅠ)
1. 방법
* (매수가 일어난 총 횟수) = (각각의 사람들이 매수당한 횟수의 총 합)
-> 각 사람들이 매수당한 횟수는 특정 사람(x)보다 앞에 있지만 뒷번호를 가진 사람(y: y>x)을 찾으면 됩니다.
-> 특정 사람의 순서(x)보다 뒷 번호를 가진 사람(y : y>x)은, 특정 사람의 원래 자리(x) 보다 1자리 앞(x-1)까지 갈 수 있습니다.(y : y≥x-1)
(이 부분을 이해하는 것이 중요합니다. 뒤에 있던 사람이 매수를 하면 뒤에 있던 사람은 자리 (x)로 오게 됩니다.)
-> 즉, 원래 특정 사람이 x에 위치해 있었고 현재 위치가 i라면, x-1부터 i-1까지 위치에 x보다 큰 숫자가 몇개 있는지 찾으면 됩니다.
동일한 테이블 STATION에서 CITY NAME이 모음(a,e,i,o,u)로 시작하는 것들을 찾아내는 문제입니다.
SELECT CITY
FROM STATION S
WHERE S.CITY REGEXP '^[aeiou]';
와 같은 형식으로 찾아낼 수 있습니다. 정규표현식은 다 비슷비슷한가보군요.
비슷한 문제가 두 문제 더 있었습니다.
1) aeiou로 끝나는 CITY NAME을 찾아라
SELECT CITY
FROM STATION S
WHERE S.CITY REGEXP '[aeiou]$';
→ 정규표현식에서 $는 끝을 의미합니다. 따라서 '[aeiou]$'는 aeiou 중 하나로 끝나는 문자열을 의미하게 됩니다.
2) aeiou로 시작하고, aeiou로 끝나는 CITY NAME을 찾아라.
SELECT CITY
FROM STATION S
WHERE S.CITY REGEXP '^[aeiou].*[aeiou]$';
→ .은 문자열 한개를 의미하고, *는 앞의 패턴이 0번 이상 반복됨을 의미합니다. 즉 .*는 0개 이상의 문자가 반복된다는 뜻이죠. 즉, "^[aeiou]" aeiou 중 하나로 시작하며, ".*" 중간에 0개 이상의 문자를 가지고, "[aeiou]$' aeiou로 끝나는 CITY NAME을 찾아라. 라는 뜻입니다.
이번 문제는 MySQL을 통해 아래와 같은 STATION이라는 테이블에서, CITI name(Column명 CITY)이 가장 짧은 것과 긴 것을 출력하는 것입니다. 이때 출력 시 주의할 점은, 같은 길이의 CITY name을 가진 것들에 대해서는 알파벳 순서가 가장 빠른 것을 출력하면 됩니다.
Output : (CITY name), (Length of the CITY name)
SELECT , CHAR_LENGTH(), ORDER BY (DESC, ASC)를 활용하여 문제를 해결하였습니다.
1. 방법
1) CITY Column의 길이 중 가장 가장 짧은 것, 긴 것을 뽑는다.
SELECT CITY, MIN(CHAR_LENGTH(CITY)) FROM STATION;
SELECT CITY, MAX(CHAR_LENGTH(CITY)) FROM STATION;
문자열의 길이를 출력하는 방식은 2가지가 있습니다.
* LENGTH() : BYTE 수를 기준으로 문자열의 길이를 출력합니다.
* CHAR_LENGTH() : 글자 수를 기준으로 문자열의 길이를 출력합니다.
2) 같은 길이를 가진 문자열이 여러 개 있을 수 있으므로, 알파벳 순으로 정렬하여 출력한다.
SELECT CITY, CHAR_LENGTH(CITY) FROM STATION ORDER BY 2 ASC,1 LIMIT 1; SELECT CITY, CHAR_LENGTH(CITY) FROM STATION ORDER BY 2 DESC,1 DESC LIMIT 1;
정렬은 ORDER BY로 진행할 수 있습니다. ASC는 오름차순, DESC는 내림차순입니다. 길이가 가장 짧은 것은 CHAR_LENGTH(CITY)를 오름차순으로 정렬한 뒤 1개만 가져오면 됩니다. 이 때 ORDER BY 뒤에 CHAR_LENGTH, CITY 순으로 입력하면, 우선순위를 가지고 정렬할 수 있습니다.
3.1) 스택 : 지역변수를 선언하는 공간으로 정적으로 공간이 할당됩니다. 프로그램 종료 시 자동으로 소멸됩니다.
3.2) 힙 : 동적으로 할당된 메모리 영역으로, 개발자가 직접 해제해줘야 합니다.(자동 소멸 X)
4) 데이터 패스 : 데이터의 이동 경로
5) 제어 유닛 : 컴퓨터의 실행을 제어하는 역할
예를 들어 CPU 같은 프로세서는 (데이터 패스) + (제어 유닛)으로 나타낼 수 있습니다.(레지스터같은 약간의 메모리도 가지고 있죠) 제어 유닛에서 제어 신호를 생성하여 순서대로 명령을 실행하게 되는데, 명령어가 주어지면 ALU에서 연산을 수행하고 이 수행 과정에서의 데이터가 레지스터에 저장됩니다.
* 메모리 계층구조
: 속도가 빠른 메모리는 비싸기 때문에, 컴퓨터의 메모리는 서로 다른 속도와 크기를 갖는 여러 계층의 메모리로 구성되어 있습니다.
속도 : 레지스터 > 캐쉬 > 램 > SDD > HDD
위와 같은 순서로 속도가 빠르게 되며, 빠를수록 가격이 비싸기 때문에 용량이 작고, 자주 사용되는 메모리입니다.
2. 기계어, 어셈블리어, 고급 언어
우리가 일반적으로 아는 C, Java, Python 과 같은 언어는 고급언어라고 불립니다. 인간이 이해하기 쉽고, 인간에 의해 작성된 알고리즘이 컴퓨터를 제어하게 됩니다. 일반 사람들도 코드만 보고는 이해하기 어려운 알고리즘을 컴퓨터는 어떻게 이해하고 작업을 수행하는걸까요?
우리가 고급 언어로 작성한 알고리즘은 컴파일러에 의해 어셈블리어로 변환되고, 어셈블리어는 다시 기계어로 변환됩니다. 이 때 기계어는 0과 1만의 조합으로 나타내지게 되어, 컴퓨터는 이를 수행할 수 있습니다.
어셈블리어에 대해 조금 더 공부해보면, 어셈블리어는 아래와 같이 opcode(실행코드), operand(실행코드)로 구성되어 있습니다. opcode에는 ADD, BRANCH 같은 명령어를 넣고, ADDRESS는 해당 연산을 수행할 공간(변수 혹은 주소의 절대값)을 입력하게 됩니다. 우리가 C언어로 작성하는 코드들은 컴파일러를 통해 이런 명령어들로 변환되게 됩니다.
http://egloos.zum.com/dreamform/v/2805479
3. 컴퓨터의 성능과 전력
우리는 영상이나 인터넷 서핑 등 다양한 목적을 위해 컴퓨터를 구매합니다. 이런 다양한 목적을 수행하는데 걸리는 시간이 짧아질수록 시간은 절약되기 때문에, 우리는 컴퓨터의 성능(과 가격)을 고려하여 구매를 결정합니다. 가격이 높을수록 컴퓨터의 성능은 좋아지겠지만, 컴퓨터의 성능이란 것은 무엇일까요?
컴퓨터의 성능을 평가하는 다양한 지표가 있지만, 대표적으로 응답시간과 처리량을 바탕으로 평가합니다. 응답 시간은 특정 작업을 수행하는데 걸리는 시간이며, 처리량은 단위시간 내에 처리할 수 있는 작업의 양을 뜻합니다. 응답 시간과 처리량은 일반적으로 반비례하며, 짧은 시간 안에 최대한 많은 작업을 처리하는 컴퓨터의 성능이 좋다고 말합니다. 그렇다면 이런 응답 시간과 처리량은 어떤 기준으로 평가할 수 있을까요?
컴퓨터는 우리에게 시간과 같은 개념으로 클럭이란 개념을 가지고 있습니다. 클럭이란 아래와 같은 일정 주기를 가지고 0과 1을 왔다갔다하는 신호를 말합니다. 이 신호가 1이나 0에 이를 때, 컴퓨터는 특정 작업의 수행을 시작할 수 있습니다. 예를 들어, Clock이 High(1)이 되면 작업을 수행하고, 작업이 끝나면 대기하다가 다른 작업이 들어오면 다음 클럭이 High(1)이 될 때 작업을 시작합니다. 즉, 클럭이란 컴퓨터가 작업을 수행하는 최소 단위(시간)이 되는 것이죠.
클럭의 속도가 높아질수록 컴퓨터는 시간을 더 잘게 쪼개서 작업을 수행할 수 있게 되어, 짧은 시간 안에 더 많은 작업을 수행할 수 있습니다. 하지만 클럭이 높아지면 높아질수록 소비전력과 발열량이 늘어나게 됩니다. 클럭 또한 트랜지스터의 작동으로 인해 생성되는 것인데, 소비전력은 트랜지스터의 스위칭 횟수에 비례하기 때문입니다. 더 많은 스위칭이 일어날수록 소비하는 전력과 발열량은 늘어나게 됩니다. 따라서 클럭의 수는 일정하게 유지하는 동시에, 코어의 수를 늘려 전력을 낮추는 방법을 사용하여 CPU는 발전해왔습니다.
클럭이 동일하더라도 CPU의 개수를 늘려서, 여러개의 CPU에서 병렬적으로 작업을 수행하면 속도는 더욱 빨라지겠죠. 하지만 병렬화도 최적화되지 않으면 싱글코어나 다름없기 때문에, 이 병렬화 작업을 최적화해주는 작업은 매우 어렵다고 합니다.
이렇게 발전해나가는 CPU들 중 우리가 많이 들어본 i3, i5, i7에 대해서 알아보겠습니다.
[ i3 - 2코어 4스레드]
[ i5 - 4코어 4스레드]
[ i7 - 4코어 8스레드]
위와 같이 구성되어 있다고 합니다. 스레드(Thread)는 프로그램을 구성하는 최소 단위로, 나중에 더 자세히 알아보도록 하겠습니다. i3가 싸고 i7이 비싼 것은 , 코어 수와 스레드 수가 증가함에 따라 병렬화하여 작업을 더 효율적으로/빠르게 처리할 수 있기 때문입니다.
4. 컴퓨터의 연산
위의 내용들을 바탕으로 컴퓨터는 덧셈/뺄샘 등의 연산을 진행하게 되는데, 특이한 소수점 연산에 대해 알아보기로 하겠습니다. 소수점을 계산하는 방법은 아래와 같은 두 가지 방법이 있으며, 일반적으로 부동소수점 방식이 사용됩니다.
