y_lime 님의 블로그

BFS : Breadth-First Search (너비 우선 탐색) 이란?- 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다. - DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다. -  queue(큐)를 이용해서 구현할 수 있다. - ex) 1을 큐에 넣고 빼면서 1과 인접한 2와 3을 큐에 넣는다. (이런 방식으로 계속 반복)🏷️ 변수 설명변수와 input은 DFS 설명한것과 다를 바가 없다.https://jaslime.tistory.com/24 🏷️ 코드 예시[Parameters]int v, e; // 정점의 개수, 간선의 개수vector> graph; // 인접 리스트vector visited; // 정점 방문 여부 저장 [..

DFS : Depth - First Search (깊이 우선 탐색)그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다.넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다.stack 또는 recursive(재귀 함수)로 구현할 수 있다.🏷️ 변수 설명그래프를 구현하는 방법에는 두 가지 방법이 있다.인접 리스트 (상대적으로 효율적)인접 행렬 (직관적 but 비효율적)1. int v, ev : 정점의 개수e: 정점 사이를 잇는 간선의 개수입력받은 정보를 통해 인접 리스트와 방문 여부를 저장하는 변수의 크기를 할당할 수 있다. 2. vector> graph이중 vector를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있으며, 유동적으로 사..

정제 (Cleaning) : 데이터 사용 목적에 맞추어 노이즈를 제거 ⇨ 인간의 주관적인 생각이 아직까지 필요하긴 함 1) 대문자 vs 소문자 똑같은 단어여도, 대소문자를 구별하여 다른 언어로 처리되기 때문에, Language에서 L을 소문자 l로 바꾸면 같은 언어로 처리된다.BUT!!! US(United States)같은 경우, 소문자로 바꾸면 us(우리)로 되게 때문에 Cleaning할 때는 주의를 해야한다.즉, Cleaning을 하지 않도록 예외 처리를 걸어줘야한다.   2) 출현 횟수가 적은 단어의 제거키워드, 킬링워드가 아니면 차라리 지워버리는게 더 효율적이다.3) 길이가 짧은 단어, 지시(대)명사, 관사의 제거 추출 (Stemming): Stemming이란 어형이 변형된 단어로부터 접사 등을 ..

텍스트 전처리 과정 (3단계)토큰화 : 문장을 단어 기준으로 자르는 과정 → I / love / you / for / always / Do / n’t / be / afraid정제 및 추출 : 중요한 단어만 냅두고 불필요한 단어들은 다 자르는 과정 → I was wondering if you can help me on this problem인코딩 : 2단계에서 남겨진 단어들을 숫자로 바꾸는 과정 → [1,5], [1,3], [1,2,5], [1,0,0,0,0], [0,1,0,0,0] 언어의 형태소문장 : 화분에 예쁜 꽃이 피었다위 문장을 토큰화 진행 → 화분에 / 예쁜 / 꽃이 / 피었다.BUT 화분"에" 가 아닌 "은","이"등등 될 수 있기 때문에 이와 같은 단어들은 조사나 어미도 토큰화에서 분리를 해..

자연어 처리란 ?우선 자연어란, 일상 생활에서 사용하는 보편적인 언어이다. 즉, 자연어 처리(NLP)는 컴퓨터가 자연어를 처리하는 일이다.종류 : 음성 인식, 번역, 요약, 분류(스팸 메일 분류 : 광고성 문자, 느낌표 등등 컴퓨터가 잡아낼 수 있음) 자연어 처리가 활용되고 있는 예시들Chatbot : A program for InteractionSentiment Analysis : 텍스트에 녹아 있는 감성 또는 의견을 파악Tokenization : 단어의 최소한의 의미를 파악하는 쪼개기Named Entity Recognition : 텍스트로부터 주제 파악하기Normalization : 의도된 오타 파악하기Dependency Parsing : 문장 구성 성분의 분석SIRI : An assistant fo..

📄 문제세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열..

📄 문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.여러분은 입력으로 주어진 괄호 문자..

📄 문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 🏷️ 입력첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다..

📄 문제N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.🏷️ 입력첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. 3 3 1 1 1 2 2 20 1 0 3 3 3 4 4 4 5 5 100🏷️ 출력첫째 줄부터 N개의 줄에 행렬 A와 B를 더한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.4 4 4 6 6 6 5 6 100 🎈 풀이N, M을 입력 받고 각각의 NxN, MxM크기의 행렬 A,B를 만든다. 우선 "N과 M은 100보다 작거나 ..

📄 문제아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다.이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다. A A B C D Da f z z 0 9 1 2 1a 8 E W g 6P 5 h 3 k x한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 심심해진 ..