분류 전체보기
프로그래머스 - 다단계 칫솔 판매 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/77486# 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 문제를 잘 읽고 방향만 잘 잡으면 쉽게 풀수 있는 문제입니다. 저는 문제를 잘 못 읽고 방향을 잘못 잡아서 고생을 좀했네요 .. 후 잘 읽어야하는 부분은 seller 리스트에 동일한 이름이 나올수 있다는 것입니다. (저는 seller를 ArrayList로 만들고 index를 찾아오는 형태로 처음에 진행했어서 틀리고 있었습니다.) 방향은 위를 파악하면 쉽게 잡을 수 있는..
프로그래머스 - 로또의 최고 순위와 최저 순위 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 최고는 알아볼 수 없게 된 수가 모두 유효한 경우이고 최저는 알아 볼 수 없게 된 수가 모두 유효하지 않은 경우 이므로 lottos와 win_num의 같은 수의 개수 구하고 lottos에 알아볼 수 없게 된 숫자의 수의 개수를 구하여서 최고는 두 개수의 합 최저는 같은 경우의 개수로 등수를 구하면 된다. ps 로또의 범위가 45까..
프로그래머스 - 행렬 테두리 회전하기 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/77485?language=java 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 직사각형 전체를 map으로 두고 순서대로 변경해가면되는 구현문제 퀴리가 0, 0 위치를 1, 1로 시작하기 때문에 map의 가로 세로를 +1씩하여 생성 x축,y축으로 이동해야하는 거리를 구함(xMove, yMove) 시계방향으로 회전 // 프로그래머스 행렬 테두리 회전하기 문제 class Solution { static int[][]..
프로그래머스 - 헤비 유저가 소유한 장소 (SQL)
programmers.co.kr/learn/courses/30/lessons/77487 코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr 총 3가지 방식으로 풀어 보았습니다. 1. 집계함수 COUNT + PARTITION BY 실행계획을 보면 메인 쿼리와 서브 쿼리 둘다 인덱스를 타지 않고 풀스캔을 하고 둘다에서 filesort가 발생한다. 3가지 방법 중 성능이 가장 별로일거라고 생각이 든다. SELECT PL.ID, PL.NAME, PL.HOST_ID FROM..
프로그래머스 - 점프와 순간 이동 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 개념만 떠올리면 간단하게 해결할 수 있는 문제 특정지점에 도달하기 까지 이상적인 경우는 그 지점의 절반 위치에서 순간이동을 하는 것이다. 순간이동으로 도착하지 못하는 경우만 건전지를 사용하면 된다. 문제의 예시인 5를 보면 5의 절반은 2.5로 나누어 떨어지지 않기 때문에 4에서 건전지를 1만큼 사용해서 이동 4의 절반은 2로 나누어 떨어지기 때문에 2..
프로그래머스 - 스티커 모으기(2) 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 이문제는 첫번째 스티커부터 뜯는 경우와 두번째 스티커부터 뜯는 경우의 dp를 이용해서 해결할 수 있습니다. 점화식은 DP[N] = MAX(DP[N-1], STICKER[N] +DP[N-2]); dpOne은 첫번째 스티커부터 뜯기 때문에 dpOne[0], dpOne[1]은 첫번째 스티커를 뜯는 경우가 됩니다. dpTwo은 첫번째 스티커부터 뜯기 때문에 dpTwo..
인덱스 알고리즘 B tree 간단 개념 정리
B Tree(Balanced Tree) - 균등한 응답속도 유지를 위하여 Leaf Level의 좌우균형을 유지하는 트리 - 데이터베이스와 파일시스템에서 주로 사용되는 트리 자료구조(비선형 자료구조)의 한 종류 - 이진트리를 확장하여 자식 노드의 최대 숫자가 2보다 큰 트리 구조 - 최악의 경우에도 O(longN)의 사간복잡도의 검색 성능 종류 B 트리 높이 균형 m-원 탐색트리 Leaf 노드가 한쪽 방향으로 쏠리는 현상이 적음 노드의 삽입과 삭제시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병)이 필요 1/2 이상 차면 노드 분열 B+트리 Leaf node간 linked list가 구성되어 순차 탐색의 효율이 좋음 leaf node에만 데이터가 있기 때문에 모든 데이터에 도달하는 비용이 거의 같..
프로그래머스 - 모두 0으로 만들기 (자바)
programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 이문제는 위상정렬을 이용해서 풀수 있습니다. 우선 모든 가중치의 합이 0이 안되면 불가능함으로 -1을 리턴 edges를 순회하면 graph에 양방향으로 간선을 연결해주고 간선에 연결된 두개의 노드를 +1해주면서 각 노드의 진입차수를 셋팅합니다. 큐를 만들어서 진입차수가 1인 노드들을 넣어줍니다. 진입차수가 1이라는 의미는 연결된 노드가 하나라는 의미로 모든 ..