프로그래머스: 문제 코딩테스트 연습 - 10주차 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 상당히 쉽다고 생각했던 문제였는데 푸는 데 꽤 걸렸고, 힌트를 사용할 수 밖에 없었다. 우선 중복적으로 교점이 생기는 가능성을 고려하지 않아서 로직에 누수가 발생했고, 자료..

문자열 인코딩이란 2진법을 사용하는 컴퓨터가 인간의 언어를 일정한 규칙에 따라 2진수로 변환하는 방식이다. 위의 이미지처럼 컴퓨터는 Hello라는 문장을 그대로 읽거나 처리할 수 없기 때문에 사람들이 만든 2진수와 문자를 일대일로 대응하는 규칙을 통해 2진수로 문자를 처리한다. 규칙은 크게 아스키 코드, EUC-KR, UTF-9, UTF-16, UTF-32 등이다. 그런데 어떠한 규칙을 적용하는지에 따라 글자가 깨지거나 보이지 않는 문제가 발생한다. 왜 이러한 문제가 발생할까? 컴퓨터가 처음 등장했을 때 모든 프로그램은 영어와 일부 특수문자만 지원했다. 하지만 여러 국가에서 컴퓨터를 사용하기 위해 국가별로 사용하는 언어를 표현하고자 독자적인 규칙을 만들기 시작했다. → 즉 여러 언어를 구현하기 위해 다양..

Index란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조이다. 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아보는 것은 오래걸린다. 그래서 책의 맨 앞이나 두에 색인을 추가하는데, 이와 비슷한 역할을 수행한다. 데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 한다. 인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 만약 Index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하..

백준: 문제 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 내일 코테를 대비하기 위해 평소에 잘 풀어보지 않은 유형들 위주로 풀고 있다. 이번에는 위상정렬(Topological Sort)! 그래프 노드별로 선후가 정해져있어서 순서를 정하기 위해 크게 2개의 배열을 사용해야 한다. 만약 a → b 식으로 선수, 후수가 정해진다면, 1. 각 노드별 진입차수 inDegree, 즉 b 노드를 방문하기 위해 이전에 방문해야하는 a 노드 개수 기록 2. 각 노드별 후수 노드들, 즉 a에 대한 b 노..

백준: 문제 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 오늘 아예 작정하고 슬라이딩 윈도우 문제를 풀고 있다. 이전 두 문제는 별도의 배열을 사용해 조금 어렵게 접근했어야 했던 문제라면 이번 문제는 풀이 방식은 쉬우나 배열 처리가 어려운 문제였다. 왜냐하면 우선 전체 배열 크기를 문제에서 제시하지 않고 주어진 수의 범위를 통해 계산해야했기 때문이다. 여기서 K의 범위가 0이상 2,000,000이므로 전체 배열의 크기는 2,000,000 * 2 + 1이다. 이제 주어진 양동이를 알맞게 위치시키고, 앨버트를 한칸씩 옮기면서 2 * ..

백준: 문제 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 처음에 보면 매우 간단한 문제로 보이나, 생각보다 메모리와 제한 시간이 빡빡해서 알고리즘을 여러 번 바꾸어가며 코드를 작성해야 했다. 1. 반복문 첫 번째로 시도한 방법은 정말 단순한 방식으로 시간복잡도가 최악의 경우 O(N^2)가 되는 반복문을 사용하였다. 쉬운 만큼 디버깅도 필요없이 단번에 작성해냈으나, 바로 시간 초과를 당했다. #include #include using namespace std; vector students..