알고리즘 문제풀이210 [프로그래머스] 오랜 기간 보호한 동물(1) 문제 풀이 과정 1) 문제 이해 및 접근 두개의 테이블에서 데이터가 필요하여 조인 사용하는 방식으로 접근했습니다. 2) 풀이 코드 사용 언어 - MySQL SELECT ai.NAME, ai.DATETIME -- 출력 열 FROM ANIMAL_INS AS ai -- 기준 테이블 LEFT JOIN ANIMAL_OUTS AS ao -- 조인할 테이블 ON ai.ANIMAL_ID = ao.ANIMAL_ID -- 조인 조건 WHERE ao.DATETIME IS NULL -- 입양 데이터가 없는 데이터들만 ORDER BY ai.DATETIME -- 가장 오래 보호소에 있었던 순서대로 정렬 LIMIT 3; -- 상위 세개의 데이터만 출력 결과 및 학습한 내용 1) 어려웠던 내용 특별히 없습니다. 2) 새롭게 학습한 .. 2021. 12. 24. [백준] 14503 로봇 청소기 문제 풀이 과정 1) 문제 이해 및 접근 청소기가 현재 위치를 기준으로 하여 동, 서, 남, 북의 4개의 방향을 바라보며 이동하므로 델타 탐색을 이용하는 방식으로 접근하였습니다. 특정 조건에 충족되면 앞으로 진행을 하기 때문에 재귀를 이용한 DFS 탐색으로 접근했습니다. 2) 알고리즘 델타 탐색 DFS 재귀 호출 구현, 시뮬레이션 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def DFS(y, x, direction): # 좌표, 바라보는 방향 global answer for k in range(1, 5): # 왼쪽 방향을 4번 확인 해야 하므로 4번 반복 new_direction = (direction - k) % 4 # 새로운 방.. 2021. 12. 24. [HackerRank] Population Census 문제 풀이 과정 1) 문제 이해 및 접근 두개의 테이블이 있어 JOIN 하여 데이터를 조건에 따라 출력하려고 접근했습니다. 2) 풀이 코드 사용 언어 - MySQL SELECT SUM(city.population) -- 출력 열 (모든 도시들의 인구의 합) FROM city -- 조인할 기준 테이블 JOIN country ON city.countrycode = country.code -- country 테이블과 조인 WHERE country.continent = 'Asia'; -- 대륙이 아시아인 데이터들만 결과 및 학습한 내용 1) 어려웠던 내용 특별히 없습니다. 2) 새롭게 학습한 내용 특별히 없습니다. 문제 링크 - https://www.hackerrank.com/challenges/asian-po.. 2021. 12. 23. [백준] 1715 카드정렬하기 문제 풀이 과정 1) 문제 이해 및 접근 가장 작은 수들을 우선으로 더해주면 되므로 그리디로 접근했습니다. 연산한 수를 리스트에 다시 넣고 그 중 가장 작은 수를 다시 빼서 사용해야 하므로 최소 힙을 사용했습니다. 2) 알고리즘 그리디 알고리즘 최소 힙 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 숫자 개수 heap = [] # 힙으로 사용할 리스트 answer = 0 # 정답 변수 for _ in range(N): # 숫자들을 모두 최소힙에 푸시 heapq.heappush(heap, int(sys.stdin.readline())) while len(he.. 2021. 12. 23. [HackerRank] Weather Observation Station 15 문제 풀이 과정 1) 문제 이해 및 접근 위도 값 중 제일 큰 값의 경도를 구해야 하므로, 위도 크기 순서대로 정렬 후 상위 1개만 출력하는 방식으로 접근했습니다. 2) 풀이 코드 사용 언어 - MySQL SELECT ROUND(long_w, 4) -- 출력할 열 FROM station -- 테이블 WHERE lat_n < 137.2345 -- 위도의 조건 ORDER BY lat_n DESC -- 큰 위도부터 순서대로 정렬 LIMIT 1; -- 가장 큰 위도의 경도이므로, 상위 1개의 결과만 출력 결과 및 학습한 내용 1) 어려웠던 내용 특별히 없습니다. 2) 새롭게 학습한 내용 특별히 없습니다. 문제 링크 - https://www.hackerrank.com/challenges/weather-observ.. 2021. 12. 22. [백준] 10868 최솟값 문제 풀이 과정 1) 문제 이해 및 접근 여러번 구간에 따라 최솟값을 구해야하므로 세그먼트 트리로 접근하였습니다. 2) 알고리즘 세그먼트 트리 (Segment Tree) 3) 풀이 코드 사용 언어 - Python import sys from math import log2, ceil sys.stdin = open('input.txt') def initial_tree(node, left, right): # 현재 노드 / 범위 시작 / 범위 끝 if left >= right: # 리프 노드일때 segment_tree[node] = lst_num[left] # 현재 노드에 숫자 값 할당 return segment_tree[node] # 할당된 현재 노드의 값 반환 left_node = initial_tree(n.. 2021. 12. 22. [HackerRank] Weather Observation Station 13 문제 풀이 과정 1) 문제 이해 및 접근 조건에 해당하는 행들의 위도의 합을 구하고, 소수점 자리를 4째자리까지만 표현해야하므로 sum 함수와 trunc 함수를 이용하는 방법으로 접근했습니다. 2) 풀이 코드 사용 언어 - Oracle SELECT TRUNC(SUM(lat_n), 4) -- 출력하는 열 (위도의 합을 구하고 소수점 4자리에서 자름) FROM station -- 테이블 WHERE lat_n > 38.7880 AND lat_n < 137.2345; -- 위도가 38.7880 보다 크고 137.2345 보다 작은 경우 결과 및 학습한 내용 1) 어려웠던 내용 특별히 없습니다. 2) 새롭게 학습한 내용 특별히 없습니다. 문제 링크 - https://www.hackerrank.com/challen.. 2021. 12. 21. [백준] 2357 최솟값과 최댓값 문제 풀이 과정 1) 문제 이해 및 접근 여러가지 경우의 범위를 여러번 조회를 하여야 하므로, 세그먼트 트리를 이용하여 접근했습니다. 이전에 학습한 숫자의 합을 저장하는것과 다르게 최솟값, 최댓값을 구해야했기에, 노드의 값으로 숫자가 아닌 리스트를 저장하는 형태로 접근했습니다. 2) 알고리즘 세그먼트 트리 (Segment Tree) 3) 풀이 코드 사용 언어 - Python import sys from math import ceil, log2 sys.stdin = open('input.txt') def initial_tree(node, start, end): # 세그먼트 트리 만들기, 현재 노드 번호 / 범위 시작 / 범위 끝 if start >= end: # 리프 노드에 도달했을때 segment_tre.. 2021. 12. 21. [프로그래머스] 오랜 기간 보호한 동물(2) 문제 풀이 과정 1) 문제 이해 및 접근 두개 테이블의 각 열을 비교하여 연산이 필요하므로 조인으로 접근하였습니다. 마지막에 상위 2개의 값이 필요하여 조인한 결과를 서브쿼리로 이용했습니다. 2) 풀이 코드 사용 언어 - Oracle SELECT ANIMAL_ID, NAME -- 출력 열 FROM ( SELECT ai.* FROM ANIMAL_INS ai, ANIMAL_OUTS ao WHERE ai.ANIMAL_ID = ao.ANIMAL_ID ORDER BY (ao.DATETIME - ai.DATETIME) DESC ) -- 서브쿼리 (두개의 테이블 조인하여 보호기간이 긴 순서대로 출력) WHERE ROWNUM 2021. 12. 20. [프로그래머스] 트리 트리오 중간값 문제 풀이 과정 1) 문제 이해 및 접근 세개의 노드를 선택하여야 하므로, 모듈을 이용해 조합의 경우의 수를 구하는 방식으로 접근했습니다. 또한 모든 점에 대해서 어떤 점을 향하는 거리의 값이 필요하여 다익스트라를 이용하는 방식으로 생각했습니다. 그러나 노드의 개수가 너무 많아, 너무 많은 다익스트라 함수를 실행하여 시간 초과가 발생하였습니다. 이 문제를 해결하기 위해 고민하던 중 트리의 지름에 관한 문제를 접하고, 활용하게 되었습니다. 세개의 노드의 길이 중 최댓값을 구하면 되었으므로 트리의 지름을 구하고 트리의 지름 -1 의 길이를 구하는 방식으로 접근하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python (1) 다익스트라, 조합 이용한 접근 - 시간 초과 import hea.. 2021. 12. 20. [프로그래머스] 없어진 기록 찾기 문제 풀이 과정 1) 문제 이해 및 접근 보호소에 들어온 동물 ID 리스트를 서브쿼리로 만든 후 그 리스트 안에 입양간 동물의 ID 값이 없는 경우를 찾는 방식으로 접근했습니다. 2) 풀이 코드 사용 언어 - Oracle SELECT ANIMAL_ID, NAME-- 출력 열 FROM ANIMAL_OUTS WHERE ANIMAL_ID NOT IN (-- 보호소에 들어온 동물 ID 리스트 안에 입양된 동물 ID 번호가 없으면 SELECT ANIMAL_ID FROM ANIMAL_INS ) ORDER BY ANIMAL_ID;-- 정렬 결과 및 학습한 내용 1) 어려웠던 내용 특별히 없었습니다. 2) 새롭게 학습한 내용 특별히 없었습니다. 문제 링크 - https://programmers.co.kr/learn/c.. 2021. 12. 19. [백준] 2042 구간 합 구하기 문제 풀이 과정 1) 문제 이해 및 접근 초기에 구간합 문제로 누적합을 이용하여 접근을 시도했습니다. 누적합을 구하고 계속되는 추가 값 수정 및 구간합을 구하는 과정에서 많은 연산이 진행될거라 예상해서 예상 연산 횟수를 고려해봤습니다. 그러나 중간에 어떠한 수가 변경하게 되면 특정 수 이후의 모든 누적합이 변경해야 하거나, 다른 변수에 저장할 경우 특정 구간의 모든 수를 확인해야하는 단점이 예상되었고, 문제 조건에 따라 수의 개수 (최대 1,000,000) X 구간합 구하는 횟수 (최대 10,000) 으로 최악의 경우 10,000,000,000(10억의 연산)번으로 시간 초과 발생을 예상했습니다. 이후 다른 알고리즘을 알아보던 중 '세그먼트 트리' 알고리즘을 알게 되어 학습 후 적용시켰습니다. 2) 알고.. 2021. 12. 19. 이전 1 ··· 14 15 16 17 18 다음
