하노정의 개발 공부

문제 https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 문제 풀이 1. 입력받은 두 문자열의 알파벳 개수를 저장할 두 개의 int형 배열(알파벳 수만큼의 크기)을 선언한다. 2. 입력받은 두 문자열을 전부 문자 배열로 바꾼다. 3. 전부 소문자이기에 대/소문자를 구별할 필요는 없으며, int형 배열 인덱스를 '문자 배열의 아스키 코드 값'을 이용해 접근한다. 4. 두 개의 int형 배열을 돌면서 값을 비교해 개수가 같은 ..

📌 목차 Matrix Computaton 🍀 Matrix Computaton a 행렬의 행의 개수가 m개, 열의 개수가 k개이다. b 행렬의 행의 개수가 k개, 열의 개수가 n개이다. a*b = c일 때, c 행렬은 행의 개수가 m개, 열의 개수가 n개이다. a 행렬의 열의 개수 = b 행렬의 행의 개수 이어야 한다. a 행렬은 행을 선택하고, b 행렬은 열을 선택해서 a 행렬은 왼 -> 오, b 행렬은 위 -> 아래로 차례대로 곱해서 더한다. a 행렬의 첫 번째 행, b 행렬의 두 번째 열을 선택하여 결과 행렬 c 행렬의 첫 번째 행의 두 번째 열에 배치된다. -> 행렬 a의 행의 인덱스가 i, 행렬 b의 열의 인덱스가 j 이면 결과는 C의 i,j에 들어간다. 연산 순서는 두 단계이다. 첫 번째 단계를..

📌 목차 Data Mining K-Means Clustering Data Mining 알고리즘 중에서 K-means clustering을 하둡 MR로 어떻게 구현할지 설명한다. 🍀 Data Mining 데이터 마이닝은 데이터로부터 이미 알려지지 않은, 그러나 잠재적으로 유용한 정보를 추출하는 작업이다. 의미 있는 패턴을 발견하기 위해, 자동 혹은 반자동 기술을 사용해 대용량 데이터를 탐색 및 분석하는 작업이다. 🔅 데이터 마이닝으로 볼 수 없는 것은? sql로 DB에 쉽게 접근해 데이터를 조회하는 류의 작업들 🔅 데이터 마이닝으로 볼 수 있는 것은? 특정 성씨가 특정 지역에서 보다 빈도 수가 높은 경우를 찾는 것 검색 엔진에서 검색된 문서들을 문맥에 따라 그룹핑 하는 것 예, 삼성전자로 검색하여 결과를 ..

📌 목차 Relatoinal Processing 🍀 Relatoinal Processing Spark에서 join, left outer join, right outer join, full outer join이 어떻게 동작하고 코드로 어떻게 작성하는지 본다. 테이블의 데이터 사이즈가 굉장히 크고 분석하고자 하는 응용에 적합하다. 결제, 웹 브라우징에는 적합하지 않다. 큰 데이터를 한 번에 읽어서 원하는 정보를 가공하는 것에 적합한 것이다. 하둡으로 relational processing 하려면 map, partition, sort, .. , reduce를 하고 이 경우는 너무 복잡하고 번거롭다. 🔅 Join in Spark RDD에 기본적으로 join 연산을 제공한다. join(inner join), le..

📌 목차 ReduceSideJoin Optimizing ReduceSideJoin MapSideJoin 🍀 ReduceSideJoin DB에서 사용하는 join을 MR에서 어떻게 구현하는지 살펴본다. Relational Operator 중에서 join이다. 같은 속성을 갖는 테이블 두 개이상이 있을 때 합치는 연산이다. 물건 테이블과 코드 테이블을 합칠 건데 코드 테이블을 기준으로 합쳐서 id, price, des를 출력하는 것이다. 데이터 파일은 테이블마다 하나씩 생긴다. relation_a, relation_b 파일로 저장한다. map은 파일 별로 mapper가 생성되기 때문에 각각 하나씩 mapper가 뜬다. mapper 속 map 함수는 어떤 테이블을 대상으로 수행하는지는 파일 이름으로 구별한다...

📌 목차 Introduction to Spark Spark WordCount 🍀 Introduction to Spark large scale data 처리를 위한 분석 엔진 Java, Scala, Python, R 등으로 Spark를 이용할 수 있다. 하둡을 백엔드 스토리지 시스템으로 사용할 수 있다. 🔅 Motivation MapReduce가 대형 데이터의 분석을 쉽게 만들어 준 것은 사실인데, 뭔가 좀 부족한 면이 있다. PageRank 처리 시 iteration을 돌고, matrix의 곱을 할 때도 두 단계의 MapReduce를 거쳐 결과를 얻어냈다. PageRank, Matix Mul과 같이 stage가 여러 개인 경우는 MapReduce로 작성하는 것이 쉽지 않다. 데이터 분석을 하고자 하는 쿼..

📌 목차 Relational Data Projection Selection Real Java Code (Projection + Selection) Top-k 🍀 Relational Data MapReduce를 활용해서 Relational Data를 처리한다. Relational Data는 DB Table에 저장되어 있는 형태를 말한다. entity, relation을 갖고 DB를 모델링한다고 학습했을 것이다. 예를 들어 entity는 학생, 과목, 교수이고 개별 table로 관리가 될 것이다. relation은 entity 사이의 관계를 말한다. 학생이 과목을 '수강'하고, 교수가 과목을 '강의'한다. Relational DB는 entity와 relation을 모두 table 형태로 모델링한다. DB에서..

📌 목차 Addition Product Product Real Java Code 🍀 Addition 행렬 덧셈은 행의 크기, 열의 크기가 정확하게 같아야 한다. 두 행렬의 같은 위치에 있는 값끼리 더해서 결과 행렬의 같은 위치에 배치하면 된다. Am*n + Bm*n = Cm*n 이런 행렬의 크기가 매우 클 때 덧셈을 어떻게 할 것인가? 거대한 행렬을 상상하기 쉽지 않은데, SNS에서 친구관계를 표현하는 것을 행렬로 나타낼 수 있다. 인덱스를 user의 id로 생각할 수 있다. 0번 user가 1번 user를 알게 되면 A01 = 1, A10 = 1로 표시한다. 거대한 행렬의 덧셈이나 곱셈을 하게 되면 한 대의 기계에서 데이터 처리를 할 수 없게 된다. MapReduce로 거대한 행렬 계산을 할 때, re..