뭘 배웠지?

알고리즘 공부하며 배운내용 마라톤 경기 트랙에 N명이 달리고 있다. 모든 선수는 각자 실력인 S가 있고 자신보다 실력이 낮은 사람을 추월이 가능하다 예를 들면 선두에 달리는 선수부터 나타내면 이렇다 1 3 2 4 4 3 5 여기서 실력이 3인 두 번째 선수는, 실력이 1인 첫 번째 선수를 앞질러 1등을 할 수 있다. 하지만 세 번째 선수는 아무리 빨리가도 2등이 최고다 이럴 때, 각 선수가 기록하는 최대 등수를 출력을 해보자 들어오는 값 실력 S가 선두부터 차례대로 입력된다. 예) 1 3 2 4 4 3 5 구할 값 최대 등수를 입력과 같은 순서로 출력 예) 1 1 2 1 2 4 1 생각 바로 생각났던 방법은 for문으로 두 번째부터 앞의 번호와 비교하는 방법 핵심 포인트 병합 정렬(Merge Sort)을..

인공지능 강의 6화를 보며 배운내용 KEYWORDS 연언표준형: 리터럴의 논리합으로 이루어진 절들의 논리곱 형식으로 표현된 논리식 연언 표준형을 잘 알아두자 선언표준형: 리터럴의 논리곱으로 이루어진 절들의 논리합 형식으로 표현된 논리식 연역추론: 이미 알고 있는 전제를 이용해서 정확한 결론을 이끌어내는 추론 방법 긍정논법(modus ponens): P와 P -> Q가 참일 때 Q가 참이라는 결론을 내리는 추론 과정 부정논법(modus tollens): P->Q와 ~Q가 참일 때 ~P가 참이라는 견론을 내리는 추론 과정 삼단논법(law of syllogism): P->Q와 Q->R이 참일 때 P->R가 참이라는 결론을 내리는 추론 과정 술어논리: 객체와 술어로 나누어 명제를 표현하는 방식, 객체를 표현하기..

알고리즘 공부하며 배운내용 크레인 크레인에 달려 있는 줄을 이용해 무거운 물건을 들어올린다. 200kg까지 들어올릴 수 있는 줄을 3개 사용하면 600kg을 들 수 있다. 줄의 강도가 섞이면 약한 줄에 맞춰진다. 100kg 150kg 두 줄을 같이 쓰면 200kg까지 들 수 있다. 가지고 있는 줄이 올릴 수 있는 무게가 들어오면, 들어올릴 수 있는 가장 무거운 무게를 알아보자 들어오는 값 가지고 있는 줄이 올릴 수 있는 무게 예) 100 300 400 보여줄 값 주어진 줄로 올릴 수 있는 최대 무게 예) 600 핵심 포인트 1줄을 사용하면 가장 강도가 센 줄을 사용한다. 2줄을 사용하면 첫 번째로 강도가 센 줄과 두 번째로 센 줄을 사용한다, 무게는 두 번째 줄이 기준이 되겠고 i개를 사용하면 i 번째까..

알고리즘 공부하며 배운내용 문자열 압축 0과 1로 이루어진 문자열이 있다. 다음 규칙으로 압축을 해보자 모든 문자가 1이면 1로 압축 모든 문자가 0이면 0으로 압축 그 외 문자열을 절반으로 나누어 '( + 압축된 왼쪽 문자열 + 압축된 오른쪽 문자열 + )'로 압축 예를 들어 1111 은 1 0000 은 0 1100 은 (10) 들어오는 값 0과 1로 이루어진 문자열 문자열은 짝수 길이로 주어진다 예) 1111000011110000 보여줄 값 압축된 문자열 출력 예) ((10)(10)) 핵심 포인트 재귀함수 접근하면, 1이나 0이 반복될 때 정리해줄 베이스 케이스를 정해두고, 반복이 안될 시 왼쪽, 오른쪽 절반씩 재귀함수로 불러준다 => 이를 분할정복이라고 하나보다 코드 // VSCode에서 JavaS..

알고리즘 공부하며 배운내용 손에 손잡고 올림픽 개막식에 손에 손잡고 공연을 한다. 우선 모든 사람이 옆 사람과 손을 잡을 수 있는지 확인을 하고, 모두와 잡을 수 있으면 얼마나 떨어져 있는지 알아내려고 한다. 각 사람의 위치는 (x, y) 좌표로 표현된다. y 좌표가 같으면 같은 줄에 서있는 거다. 들어오는 값 첫 번째 줄에는 전체 사람 수 N이 입력된다. 두 번째 줄부터는 사람들 차례대로(x, y)가 입력된다. 예) 5 1 3 2 3 3 5 1 5 7 5 보여줄 값 모두가 옆 사람과 손을 잡을 수 있는 경우 SUCCESS 출력, 그 다음줄에 가장 먼 거리를 출력 아니면 FAIL 출력 예) SUCCESS 4 핵심 포인트 전부 다 비교하지 않고, 왼쪽 오른쪽만 비교하면 된다. y좌표가 같으면 x좌표를 비교..

알고리즘 공부하며 배운내용 계단 오르기 계단을 한 칸씩 or 두 칸씩 올라간다. 계단을 오르는 경우의 수를 구하는 문제 입력 계단의 높이 N이 입력된다. 예) 4 출력 N까지 경우의 수 출력 예) 5 계단 높이 4의 경우의 수는 이렇게 되겠다 1칸 - 1칸 - 1칸 - 1칸 1칸 - 1칸 - 2칸 1칸 - 2칸 - 1칸 2칸 - 1칸 - 1칸 2칸 - 2칸 풀이 방법 문제를 보고 이해가 안되는 알고리즘은, 작은 숫자를 대입해보고, 규칙을 찾으려고 해봐야 되는 것 같다. 밑에 풀이 방법을 적어놨지만, 어떻게 이런 방법으로 계단 오르는 방법의 수가 나오는지 이해는 안가고 놀랍기만 하다. 그럼 규칙을 찾아보자 계단의 높이가 1일 때 올라갈 방법은 1 2일 때 올라갈 방법은 1칸 1칸 그리고 한번에 2칸 그래서..

선형대수 7화를 듣고 배운내용 2부 시작 / 핵심: 벡터공간이란 무엇인가? 벡터(vector) 컴퓨터과학에서 벡터는 좌표값이다. Rn공간 벡터의 정의 영어로 유클리드 n차원 공간(Euclidean n-space) n개의 실수들의 순서조 전체의 집합 순서조: 순서가 있다. 크기와 방향이 같으면( or 0점으로 옮기면) 벡터A와 벡터B는 같다. 벡터의 거리(크기) R2 벡터의 크기 a2 + b2 의 루트 씌운거 => 삼각형 윗면 구하는 피타고라스 정리 R3 벡터의 크기 루트 a2 + b2+ c2 Rn 벡터의 크기 루트 a2 + b2 + c2 + . . . + n2 벡터의 실수 곱 kA = (ka1, ka2, ... kan) 벡터의 합 A + B = (a1 + b1, a2 + b2, . . . , an + b..

알고리즘 공부하며 배운내용 마트 계산대 마트에는 여러 대의 계산대가 있다. 손님들이 계산을 마치는 데 얼마나 걸리는지 궁금하다. 어떤 계산대는 빨리 끝나고, 어떤 계산대는 오래 걸린다. 그래서 비어있는 계산대로 가는 것보다, 빨리 끝나는 계산대에 기다리는게 더 빠른 경우도 있다. 예를 들어 6명의 손님이 5분, 7분 걸리는 계산대에 있다고 해보자. 5분 계산대가 3명 => 15분 7분 계산대가 2명 => 14분 여기서 남은 1명이 7분 계산대로 가면 21분 1분 기다려서 5분 계산대로 가면 20분에 끝난다. 즉 20분이면 계산이 다 끝난다 입력 두 줄을 받는다. 첫번째 줄: 손님 수 N 두번째 줄: 각 계산대에서 걸리는 시간이 공백으로 구분 예) 6 5 7 출력 모든 손님이 계산이 끝나는 최소 시간 핵심..

자료구조 7화를 듣고 배운내용 KEYWORDS 트리: 논리적 계층이 있는 구조, 트리를 구성하는 항목을 노드 혹은 점(vertex)라고 한다. 루트 노드: 최상위 노드, 부모가 없는 노드(진입 차수 = 0) 서브 트리: 부모 노드를 삭제하면 생기는 트리들 리프 노드: 최하위 노드, 서브 트리를 갖지 않는 노드(진출 차수 = 0) 진입 차수: 트리의 어떤 노드에 들어오는 선의 개수 진출 차수: 트리의 어떤 노드에 나가는 선의 개수 내부 노드: 루트도 잎도 아닌 노드 형제(sibling): 같은 부모를 갖는 노드 포화 이진 트리: 이진 트리에서 각 레벨에 최대 개수(노드당 2개씩) 노드를 가지는 트리 완전 이진 트리: 높이 k 이진트리에서 k-2까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노..

자료구조 6화를 듣고 배운내용 KEYWORDS 단순 연결 리스트: 링크 부분이 하나, 각 노드는 후행 노드만 가리킨다. 후행 노드는 쉽게 접근 가능, 선행 노드는 접근하기 복잡하다 이중 연결 리스트: 선행 노드와 후행 노드에 접근할 수 있는 구조 원형 연결 리스트: null 값을 갖는 마지막 노드의 링크 부분을 활용해서 프로그램 성능 주기위해 제안 모든 노드가 원형으로 연결되어 있기 때문에 한 노드에서 어떤 노드로든 접근 가능 원형 이중 연결 리스트 head에도 Llink와 Rlink를 주고 Rlink는 제일 뒤의 노드에 연결 => 앞에서부터 찾아갈 수도 있고, 맨 뒤 노드에서부터 왼쪽으로 찾아올 수 있다.