QQ의 다이어리

# DFS (Depth First Search) '깊이 우선 탐색'이라는 이름에서 알 수 있듯이, 최대한 깊숙이 들어가서 확인하고, 돌아가서 또 반복하며 트리나 그래프를 탐색한다. 가장 마지막에 만났던 갈림길의 정점으로 돌아가서 다시 DFS를 진행해야 하므로 후입 선출 구조의 스택을 사용한다. input 사이즈가 너무 크지 않다면 스택뿐만 아니라 재귀 호출로도 구현 가능하다. - 재귀를 이용한 코드 void recur_dfs(int node) { visited[node] = true; for(int next=0; next

문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 2차원 벡터를 생성해서 입력값들을 저장했다. 2차원 벡터로 문자열과 1차원 정수 벡터를 짝으로 묶었으므로, 아래와 같이 저장된다. v.first v.second[0] v.second[1] v.second[2] 이름 국어 점수 영어 점수 수학 점수 그 후, comp 함수를 생성하여 정렬했는데, comp 함수에는 문제가 요구하는 내용을 바탕으로 정렬하도록 했다. 국어 ..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 DLL을 이용하여 풀 수 있는 문제이다. 포인트는, 첫 번째로 현재 커서의 위치를 나타내는 cur 포인터가 연산이 끝나고 제자리를 잘 가리키도록 해야 한다는 것이다. 추가 연산을 한 후에는 새로 생성된 노드를 가리키고, 삭제 연산을 한 후에는 가리키던 노드의 이전 노드를 가리키도록 한다. 왼쪽이나 오른쪽으로 이동하는 연산을 할 때는 연결리스트의 범위를 넘어가지 않도록 한다. 두 번째는 연..

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 입력으로 주어지는 배열의 원소 개수가 최대 8개이므로, 브루트포스로 하나하나 확인해가며 최댓값을 찾으면 된다. 이때 모든 경우의 수를 찾기 위해 next_permutation 을 사용했다. 입력받은 배열을 오름차순으로 정렬한 후, 계속해서 다음 순열을 찾으면서 원소들의 절댓값을 더한다. 끝날 때까지 반복하고 나면 max 변수에 최댓값이 저장된다. 코드 #include #include #include ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 R이 입력되었을 때, 매번 배열을 뒤집으면 시간 초과가 발생할 것이다. R이 입력될 때마다 flag를 설정해서 처리해줬다. 뒤집힌 상황 -> D가 입력됨 -> 뒤에서 노드를 제거 뒤집히지 않은 상황 -> D가 입력됨 -> 앞에서 노드를 제거 즉, 앞 뒤에서 노드를 제거할 수 있어야 하므로 더블리 링크드 리스트를 사용했다. 더블리 링크드 리스트로 구현하면 값을 출력할 때도 맨 뒤 노드부터 prev로 접근하면서 역순으로 출력하거나, head부터 ..

# javascript 기초 강의 전공 교수님이 강의해주시는 자바스크립트 강의를 들었다. DB 이용한 웹페이지 만들때 html과 css는 좀 접해봤지만 javascript는 처음이라 재밌었다. js에서는 문자열을 나타낼 때 " ", ' ', ` ` 의 3가지 방법으로 표현할 수 있다. 이때 backtick(` `)은 console.log( ) 안에서 입력한 그대로 출력된다. 만약 줄을 바꾸고 싶다면 backtick은 그냥 코드 안에서 엔터를 넣어주면 되지만, 그 외의 따옴표들은 \n을 추가해줘야 줄이 바뀐다. 그냥 엔터를 쳐버리면 에러가 난다. 또 typeof 명령어를 사용하면 자료형의 이름을 알 수 있다. 이때 정수든 소수든 상관없이 모두 number로 출력된다. js에서 문자열 + 숫자를 한다면(co..

◎ html 의 구성 html 문서는 head 태그와 body 태그로 이루어져 있다. head 부분에는 페이지의 제목이나 문서의 형태와 같은 정보가 들어가고, body 부분에는 웹페이지에 실제로 출력되는 내용이 들어간다. head 부분을 살펴보면, 이라고 되어 있는데, 이는 한글을 출력하기 위함이다. 영어나 숫자와 같은 문자는 ascii 코드로 출력할 수 있지만 한자, 한글과 같은 문자들은 utf-8을 이용해야 한다. hello world,, bye world,, 위 코드를 실행하면 아래와 같은 페이지가 생성된다. 웹페이지의 주소를 보면 127.0.0.1:5500이 보이는데, 여기서 127.0.0.1은 자기 자신을 가리키고, 5500은 포트 번호를 가리킨다. vscode에서 html 코드를 작성한 후, ..

◎ html 의 구성 html 문서는 head 태그와 body 태그로 이루어져 있다. head 부분에는 페이지의 제목이나 문서의 형태와 같은 정보가 들어가고, body 부분에는 웹페이지에 실제로 출력되는 내용이 들어간다. head 부분을 살펴보면, 이라고 되어 있는데, 이는 한글을 출력하기 위함이다. 영어나 숫자와 같은 문자는 ascii 코드로 출력할 수 있지만 한자, 한글과 같은 문자들은 utf-8을 이용해야 한다. hello world,, bye world,, 위 코드를 실행하면 아래와 같은 페이지가 생성된다. 웹페이지의 주소를 보면 127.0.0.1:5500이 보이는데, 여기서 127.0.0.1은 자기 자신을 가리키고, 5500은 포트 번호를 가리킨다. vscode에서 html 코드를 작성한 후, ..

문제 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 풀이 여러 문자열을 입력받아서 오름차순으로 정렬하고, 각 문자열의 백분율을 옆에 출력하면 된다. 오름차순으로 정렬하고, 입력받는 문자열의 개수를 세야 하므로 map을 이용해줬다. 이 문제에서는 입력받는 문자열의 개수나 입력을 마치는 조건이 없으므로 입력이 없을 때까지 입력을 받아야 하는데, 이때 while(cin>>s) 나 while(getline(cin, s))와 같은 형태를 사..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 이전에 게시했던 MST 관련 포스팅을 익혔다면 그냥 해결할 수 있는 문제이다. MST를 구현해서 가중치의 합을 출력하면 된다. ◎ MST를 구현하기 위한 알고리즘에 대한 설명은 -> https://qqs-diary.tistory.com/106 MST (Minimum Spanning Tree) MST란 그래프의 모든 vertex를 최소 edg..