1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출발지를 들렀다고 표시한다. 2. 들르지 않은 노드 가운데 가장 가까운 노드를 선택한다. 3. 선택한 노드를 거쳐서 직접 연결된 다른 노드까지 도달하는 거리가 이미 저장된 거리보다 짧다면 최단 거리를 갱신한다. 4. 2~3을 모든 노드를 방문할때가지 반복한다. 모든 노드를 들르면서 위의 과정을 진행하기 때문에 O(N) 의 연산이 필요하다. 거기에 2번을 완탐으로 탐색하게 되면 매번 O(N)이 걸리므로 총 O(N^2) 이 필요한 알고리즘이다. 2. 최소힙 사용 2. '기장 가까운 노드 찾기'를 더 빠르게 수행하기 위해 최소힙을 사용해..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 다양한 풀이 방법 (행단위, 열단위, 스택) 매우 다양한 풀이로 해결할 수 있는 문제인 것 같습니다. 전 두가지 방법을 시도해봤고 접근법은 코드에 주석으로 달아놨습니다. 1. 행단위로 해결하기 2. 열단위로 해결하기 2번이 가장 많이 알려진 풀이인 것 같습니다. 2번의 경우 max(slicing)으로 해결할 수 있고 그게 코드상 훨씬 간결하긴한데 모든 칸에 대해서 왼쪽, 오른쪽의 max 값을 구하면 O(N*N)이라 O(N)으로 해결해보려고 메모이..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr where절 서브쿼리, IN 기간 안에 5회 이상 대여된 차량 번호를 서브쿼리로 먼저 구하고, IN 절로 해당 차량 정보만 추려서 조건에 따라 출력합니다. date 기간의 경우 AND로도 해결할 수 있고 DATE_FORMAT으로 포맷을 맞춘 후 BETWEEN으로도 해결할 수 있습니다. "2022-08-00"
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 여러 필드 기준 GROUP BY, 삼중 JOIN, date필드에 조건 걸기 3개의 테이블을 조인해서 해결합니다. 여러 필드 기준으로 ORDER BY 하듯 , 로 연결해서 여러 필드 기준으로 GROUP BY를 할 수 있습니다. YEAR이나 DATE, LIKE 등으로 date 필드 조건을 걸어줍니다. 쿼리문 SELECT a.AUTHOR_ID, a.AUTHOR_NAME, b.CATEGORY, SUM(bs.SALES*b.PRICE) AS TOTAL_SALES FROM BOOK_SALES bs JOIN BOOK b ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CONCAT으로 문자열 붙이기, WHERE절 서브쿼리, ORDER BY JOIN으로 해결할수도 있지만 JOIN보다는 WHERE절 서브쿼리가 빠르다고 생각돼서 WHERE절 서브쿼리문만 작성했습니다. CONCAT으로 행마다 동적으로 문자열을 붙여서 출력할 수 있습니다. SELECT CONCAT("/home/grep/src/",BOARD_ID,"/",FILE_ID,FILE_NAME,FILE_EXT) AS FILE_PATH FROM USED_GOODS_FILE WHERE BOARD_ID = ( SELECT BOAR..
2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 유의미한 탑만 남기자 유의미한 탑은 신호가 도달할 가능성이 있는 탑이다. 자기자신보다 큰 탑에 신호가 완전히 막힌 탑은 앞으로 무의미한 탑이된다. 그런 탑들을 제외하면서 정보를 가져가면 빠르게 탐색할 수 있다. 스택을 이용해서 관리할 수 있다. 앞에서부터 탐색을 진행하면서 스택의 가장 위에 있는 탑보다 현재 탑이 더 높은 경우 스택에 있는 탑은 무의미한 탑이 되므로 pop해서 모두 제거한 뒤 현재 탑을 스택에 추가한다. 시간복잡도 시간복잡도는 O(N)으로 대..
