live the life you love

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 잘 읽자! 문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다. 테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 ..

기존 깃랩 서버는 Azure VM에 설치해서 사용중이었다. 도메인도 할당받지 않고 ip주소로 접근하여 사용중이었다. 실제 운영을 위해서는 도메인도 필요하고, 이제는 거의 필수가 된 https적용도 필요하다. 예전에 Tomcat에 Let's encrypt를 사용해서 SSL을 적용했던 경험을 토대로 nginx를 앞단에 두고 적용하려고 했다. 하지만, nginx의 기본 포트인 80번을 이미 GitLab에서 사용중이었다. 이를 해결하기 위해 Gitlab의 기본 포트를 변경해볼까 하며 docs를 찾아보던 중 GitLab 자체적으로 ssl 적용을 제공하는 것을 찾았다.SSL Configuration | GitLabSSL Configuration | GitLabSSL Configuration Available SSL..

최장증가부분수열 Longest Increasing Subsequence 문제 예시) 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 관련 문제 백준 11055번 가장 큰 증가 부분 수열 백준 1965번 상자 넣기 백준 11053번 가장 긴 증가하는 부분 수열 LIS를 해결하는 방법은 두가지가 있다. N의 크기, 문제의 조건에 따라 아래 두 방법중 적절한 것을 사용하면 된다. 방법 1 : 이중 for-loop 시간복잡도 : O(n^2) dp 배열은 i 번째 원소가 가질 수 있는 최대증가..

Floyd-Warshall Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다. 또한, 음수 가중치의 경우도 구할 수 있다. 알고리즘은 비교적 간단하다. 관련 문제 백준 11404번 플로이드 기본 개념 3중 for loop 사용 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다 음의 가중치 적용 가능 a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다 아래의 조건문이 핵심이다 if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면 arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신 } 시간 복잡도 O(n^3) floyd 구현 각 반복문의 ..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다. 수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다. 기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다. ..

간혹가다 코딩테스트를 보는 기업들 중, SQL 문제가 1문제씩 나오는 기업들이 있다.(ex. SK C&C, 현대 IT&E, 은행권) MySQL은 정보처리기사 시험공부나 데이터베이스 전공시간에만 다루고 실무에서 사용하지 않는 이상 취준생이라면 잘 만질일이 없다. SQL 관련 문제는 프로그래머스를 참고하면 좋다. 시험보기 1~2주전 한번 다 풀어보면 좋다. 코딩테스트 연습 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr 만약 이걸 다 풀었다면 해커랭크에서도 문제를 풀어 볼 수 있다. Solve SQL Code Challenges A special-purpose language designed for managing data held in a relational database..

DijkstraDijkstra는 비용이 있는 그래프에서 최단 거리를 찾는 알고리즘이다.최단 거리와 관련된 그래프 알고리즘에는 대표적으로 다음의 3개의 알고리즘도 존재한다.다익스트라 알고리즘 : 하나의 시작점에 대해 다른 모든 정점들까지의 최단 경로를 구함벨만포드 알고리즘 : 음의 가중치 고려플로이드 와샬 알고리즘 : 모든 정점에 대해 다른 모든 정점에 대한 최단경로를 구함이 중 기본이 되는 다익스트라 알고리즘을 정리해보았다.참고자료 관련 문제백준 1753번 최단경로SWEA 1249 보급로기본 개념다익스트라 알고리즘은 하나의 시작점에 대해 최단 경로를 찾는다.다시 말해 A에서 시작하면 B,C,D,E,F에 대한 최단 경로를 구한다는 것이다.음의 가중치는 고려하지 않는다.(음의 가중치를 고려한 최단거리 그래프..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 카테고리 분류에 BFS가 있어서 당황했던 문제이다. 이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다. 어려웠고 놓쳤던 부분은 다음과 같다. '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다. 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 ..

list Index l[i] O(1) 인덱스로 값 찾기 Store l[i] = 0 O(1) 인덱스로 데이터 저장 Length len(l) O(1) 리스트 길이 Append l.append(5) O(1) 리스트의 맨 뒤에 데이터 저장 Pop l.pop() O(1) 리스트의 맨 뒤의 데이터 pop Clear l.clear() O(1) 리스트 초기화 Slice l[a:b] O(b-a) 슬라이싱 되는 길이에 비례 Extend l.extend(...) O(len(...)) 확장되는 길이에 비례 Construction list(...) O(len(...)) 리스트 길이에 비례 check ==, != l1 == l2 O(N) 전체 리스트가 동일한지 확인 Insert l[a:b] = ... O(N) 데이터 삽입 Del..

programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제 제목에 나와있듯이 문자열을 파싱하는 문제이다. 문자열의 최대 길이가 1000이므로 완전탐색으로 해도 충분했다. 문제 해결 문자열의 길이가 n이라고 한다면, 문자열을 1부터 n/2개 까지 나눈다 나눈 문자열을 리스트에 넣는다, 리스트에 들어간 n개씩 자른 문자열을 앞뒤로 비교해가며 같다면 1씩 늘린다. 비교 과정에서 문자열이 다르다면 반복횟수와 반복문자열을 붙인다 이..