Daily Log

0612 #01. 자바스크립트 알고리즘 스터디 문제 풀며 필요 개념 정리 1. var, const, let const, let은 ES6 문법이며 var는 ES6 이전의 문법이다. var 는 {} 단위의 scope이 아닌 function 단위의 scope을 가진다. var : 같은 변수를 두번 선언했는데도 오류가 나지 않음 ;;;;;; => 많은 오류 발생 보통 프로그래밍 언어들이 가지는 변수 scope과 다름. var hello = "hello world"; var hello = "bye world" console.log(hello); // bye world const: constance의 약자. 한번 선언된 상수의 값을 변경 할 수 없다. const hello = 'hello'; hello = 'cha..

1. 먼저 간선을 가중치 값으로 오름차순으로 정렬한다. 2. 간선을 선택해가면서 싸이클이 되어버리면 선택하면 안된다! 아무리 간선 가중치 값이 적다고 해도! 3. 2번 정점과 9번 정점은 최소비용신장트리의 원소로 들어옴 => 이때 Union & Find로 집합을 만들어서 연결시켜버린다. 4. 2와 3을 연결하는 가중치값 10 인 간선 => 이 간선을 선택하느냐 마느냐에서 2번 정점을 find로 하고, find 3을 하여 둘이 서로 다른 집합이면 연결한다. 2와 3도 Union 한다. 5. 이런식으로 계속 간선값을 누적한다. 6. 이미 2번과 8번 정점은 연결되어 있는 상태이기 때문에 선택하지 않는다. => 회로가 되면 안된다! 싸이클을 피해라! 7. find 8 find 9는 이미 트리의 집합의 원소로 ..

11번 - 숫자의 총 개수(small) 자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까요? 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였음을 알 수 있습니다. 자연수 N이 입력되면 1부터 N까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작 성하세요. * i를 바로 나눠주면 안됨. i는 계속 돌아가고 temp에 넣어서 temp를 쪼개서 한 숫자의 자릿수를 세야함 // 11번 - 숫자의 총 개수(small) #define _CRT_SECURE_NO_WARNINGS #include int main() { int N, count = 0, temp;..

알골 연습문제 90제 : 6~10번 6번 - 숫자만 추출 문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2her”에서 숫자만 추출하면 0, 0, 1, 2이고 이것을 자연수를 만들면 12가 됩니 다. 즉 첫 자리 0은 자연수화 할 때 무시합니다. 출력은 12를 출력하고, 다음 줄에 12의 약 수의 개수를 출력하면 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다. ▣ 입력설명 첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 50을 넘지 않습니다. ▣ 출력설명 첫 줄에 자연수를 출력하고, 두 번째 줄에 약수의 개수를 출력합니 * 문자 배열 끝에는 ..

백준2164 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net c++ deque를 이용하면 쉽게 풀 수 있다. // BJ 2164 #define _CRT_SECURE_NO_WARNINGS ..

https://www.acmicpc.net/problem/10219 10219번: Meats On The Grill 각 테스트 케이스마다 각 고기덩이를 뒤집은 후의 불판의 상태를 H줄에 걸쳐서 출력한다. 각 줄에는 W개의 문자가 있어야 하며, 입력에서 주어진 각 고기 덩이가 뒤집힌 채로 있어야 한다. 이를 만족하는 어느 답을 출력해도 정답으로 인정한다. www.acmicpc.net 문제 abbb aabb aa.. 이런식으로 고기 모양이 주어지는데, 같은 영어 소문자는 고기 한덩이다. 이 고기들을 90도/180도/270도/반전 하여 겹치지 않게 주어진 그리드 안에서(h*w) 고기를 뒤집는 것 => 고기 한덩이가 붙어 있도록 회전 or 반전 시키면 됨 reverse() #include int a[5] = {..

삽입정렬 - 적절한 위치에 삽입 하는 것 - 처음부터 왼쪽에 있는 원소와 비교해서 해당 원소가 비교값보다 작다면 왼쪽으로 이동하는 식으로 더 큰 수를 만날때까지 반복해준다. - 항상 왼쪽에 있는 것은 정렬되어 있다고 가정되어 있음. 즉, 멈출 코드를 알고 있다는 것. (왼쪽의 원소값보다 해당값이 크면 멈추면 된다.) - 시간 복잡도(Big O) : 10 + 9 + 8 + 7 ... + 1 => O(N^2) - Big O는 선택/버블과 같지만 실제로는 선택/버블/삽입 중에서는 삽입이 제일 연산이 적다. - 거의 정렬된 상태의 정렬을 삽입 정렬로 한다. => 삽입 정렬이 굉장히 빨라짐 // 삽입정렬 insertion sort #include using namespace std; int main(void) {..

- 입력받을 배열을 공간을 선언한다. - 입력받은 배열을 for문을 통해서 %42 해준다. - %42한 값은 set container에 넣어준다. 이때, set container는 중복 값을 받지 않기 때문에 나머지 중 같은 수는(이미 담긴 수) 제외되고 담긴다 - set container의 size를 구하면 담긴 원소 개수를 알 수 있다. => 10개의 값을 각 %42를 한 후, 나머지 값들 중 중복을 제외한 서로 다른 값의 나머지 개수만 구하기 // BJ 3052 #include #include using namespace std; int main(void) { int array[10]; int count = 0; for (int i = 0; i > array[i]; ..

버블 정렬 - 당장 옆에 값과 비교 - 1회차가 끝나면 가장 큰수가 가장 뒤에 정렬돼있다. 5 3 4 1 2 6 1회차 3 5 4 1 2 6 3 4 5 1 2 6 3 4 1 5 2 6 3 4 1 2 5 6 3 4 1 2 5 6 2회차 - 맨 뒤에 정렬된 6 제외한 나머지 앞 5개의 수만 비교 => 6 + 5 + 4 + 3 + 2 + 1 (등차수열) => n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거) => n*n => 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가 시간복잡도 빅오 : O(N^2) 데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘 *시간복잡도는 선택정렬과 같지만, 실제 수행 시간은 버블정렬이 더 느리다. 매번 바로 ..

- 선택정렬 : 전체 배열 중 가장 작은 것을 선택해서 맨 앞으로 보내는 것 (맨 앞에 숫자는 제일 작은 것에 있던 숫자의 자리로 값을 스와핑한다.) 5 2 6 1 3 4 1 2 6 5 3 4 1 2 6 5 3 4 1 2 3 5 6 4 1 2 3 4 6 5 1 2 3 4 5 6 - 1회차 : 6번 비교 - 2회차 : 5번 비교 - 3회차 : 4번 비교 ... => 6 + 5 + 4 + 3 + 2 + 1 (등차수열) => n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거) => n*n => 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가 시간복잡도 빅오 : O(N^2) 데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘 //선택정렬 Sel..