알고리즘

문제 링크https://www.acmicpc.net/problem/10986 사실 문제를 보자마자 너무 놀랐다. 삼성 SDS Pro 시험 2차 시험 문제가 거의 똑같았기 때문이다. 그리고 티어를 보고 다시 한번 놀랐다. 시험장에서 4시간 동안 고민했던 문제가 고작 골드3이라니.. 뭔가 허무하기도 했고 실력이 많이 늘었다고 생각했는데 아직 많이 부족하구나 라는 겸손이 생기게 된 문제였다... (+ 시험장에서 쫄지 말자!) 아직 문제 푸는 속도도 그렇고 아이디어를 떠올리는 것도 그렇고 골드 위주의 문제들을 많이 풀어봐야 할 것 같다.문제 접근이 문제는 모든 경우를 구하고자하면 시간초과가 발생하게 된다. N의 범위를 살펴보면 1 ≤ N ≤ 10^6로 전체 구간 길이의 경우의 수는 NC2이기 때문이다. 때문에 ..

SQL 동작 순서💡 'FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY'정규 표현식https://schatz37.tistory.com/39CTECTE는 쿼리 내에서 임시 테이블을 정의하여, 후속 SELECT문에서 사용할 수 있도록 하는 구조-> 임시로 쿼리 결과를 저장해 놓고, 여러번 참조해서 사용하는 용도로 사용사용 방법WITH 키워드와 AS로 cte_name에 맵핑할 쿼리를 작성한 후 cte_name으로 지정한 테이블을 조회한다.WITH CTE_NAME AS ( -- CTE 정의 부분 SELECT column1, column2, ... FROM some_table WHERE condition)-- CTE 사용 부분SELECT..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 효율성 테스트 실패 코드효율성을 고려하지 않고 Brute Force 방식으로 코드를 작성한다면, 굉장히 쉬운 문제다.class Solution { public int solution(int[][] board, int[][] skill) { for (int[] s : skill) { if (s[0] == 1) { // 공격 for (int i=s[1]; i 0) { ..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석시간 복잡도를 줄이는 것이 관건인 문제이다. 문제에서 주어진 변수들의 범위는 5 ≤ n ≤ 1,000,000과 1 ≤ cmd의 원소 개수 ≤ 200,000이다. 명령어 'U' 또는 'D'가 입력되었을 때, 주어진 숫자 X만큼 이동하는 것이 핵심이다. 이때, 삭제된 행으로 이동하는 것은 이동했다고 간주하지 않기 때문에, 배열로 선언하여 순차 탐색으로 포인터를 움직인다면 주어진 X보다 더 많이 반복문을 돌며 포인터를 이동해야하기 ..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사고 과정해당 문제는 문자열에서 110을 추출하여 다시 삽입하는데 문자열 중 사전 순으로 가장 앞에 오는 문자열이 되도록 삽입해야 한다.사전 순으로 가장 앞에 와야 한다. 가 이 문제의 핵심 요구사항이다. 어떻게 하면 사전 순으로 가장 앞에 오게 만들 수 있을까?일단 추출 과정부터 살펴보자. 주어진 예시 중 하나인 "100111100"에서 110을 추출해보자. 추출 후 문자열은 "100110"이 된다. 즉, 처음의 문자열에서 110을 ..

문제 링크https://www.acmicpc.net/problem/2887고민한 점문제에서 N개의 행성과 N-1개의 간선, 모든 행성이 연결되도록, 최소 비용 이 3가지 키워드를 보면 최소 스패닝 트리 (MST) 문제구나! 라는 것이 쉽게 파악 된다.다만, 주어진 N의 최대 범위는 100000 으로, 만약 모든 간선을 구하여 풀고자 한다면, 최대 간선의 개수는 $100000C2$로 시간 초과에 더해 메모리 초과까지 발생할 것이다. 때문에 두 행성 간의 터널 비용을 모두 구하는 단순한 방식으로는 이 문제를 해결할 수 없다.간선의 개수를 줄여보자.크루스칼 알고리즘 플로우를 살펴보면, 간선의 비용이 작은 간선부터 연결하여 연결된 간선의 총 개수가 n-1개가 될때까지 두 노드를 union하는 로직이다. 즉, 간..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법처음 문제를 읽어보면, 복잡하다고 생각할 수 있지만 예시와 상황을 찬찬히 살펴보면 그리디적으로 접근하면 쉽게 해결할 수 있다는 것을 금방 눈치챌 수 있다.최소 거리로 이동하면서 모든 집에 배달 및 수거하기 위해서는, 가장 멀리 떨어진 집에 배달을 하면서 물류창고로 돌아올 때, 멀리 떨어진 집부터 택배 상자를 함께 수거해야 한다. 즉, 가장 거리가 먼 집부터 방문하고 돌아오면서 최대한 멀리 있는 집들의 택배 상자도 함께 수거하..