공부의 발자취를 남기는 블로그

문제분석 오랜만에 레벨 3 문제를 풀어보았다. 문제를 요약해보자면 1.적당한수 e 가 주어지고, e보다 작은 여러개의 start지점이 주어집니다. 2.서로다른 start지점에서 e부터 최대 출몰하는 숫자를 입력합니다. 3. 최대 출몰하는 숫자가 여러개라면 작은숫자를 우선 First Try: 1.먼저, 최대 출몰하는 숫자를 알려면, 그 숫자가 몇번 출몰하려는지 알아야 합니다. 억억단에서 그 숫자가 출몰하는횟수는 약수의 갯수 라는걸 알았고, 약수의 갯수를구합니다. 2.약수의 갯수를 구하여 약수 배열에 저장합니다. 매번 그 약수를 다시 구하는건 비효율적이니 dp 방식처럼 배열에 저장을 해놓았습니다. 약수의 갯수를 구하는 로직이 여러개 있지만, 해당문제는 여러개의 약수를 동시에 구해야하기때문에 다음 로직을 사용..

문제분석 문제를 이해해보자. 니니즈 친구들 :무한 징검다리 갯수 : 최대 20만 징검다리 카운트: 최대 2억 니니즈들의 점프력: 0

문제분석 문제목표 : 출발점과 산봉우리의 intensity가 최소가되는 등산코스를 정해주세요. 특징1. Intensity는 각노드마다 휴식없이 이동하는 거리다. 노드마다는 휴식공간이 있다. 특징2. 산봉우리는 코스에 단 1개만 존재해야한다. 처음 접근: 플로이드 와샬 사용 -> 여러개의 출발점과 여러개의 산봉우리가 존재하기때문에, 모든 정점과 모든 정점의 최소거리를 구하는 알고리즘을 사용했다. 단, 이 문제는 최소거리가 아닌 Intensity를 구해야하므로 알고리즘을 고쳐 사용해야한다. -> 결과: 정확성 O 효율성 에러 생각되는 이유: 원하는 출발점 -> 산봉우리의 Intensity는 구할수있지만, 그외의 경우, 경유지->경유지, 산봉우리->산봉우리, 출발점 -> 출발점 과같은 케이스들의 쓸데없는연산은..

문제분석 목표: 모든 노드의 값(가중치)을 0으로 만든뒤 최소 연산의 횟수를 구해주세요. 특징1. 인접한 노드끼리는 값을 주고받을수있다. 모든 값을 0으로 만들기위해선 노드와 노드끼리 값을 교환할수밖에 없기때문에, 그래프를 그릴필요가있다. 그래프를 그리는법은 여러방법이있다. Graph 리스트를 하나 만들어 저장하거나, 객체를 만들어서 저장하거나.. 필자는 객체 Node를 만들어서 그래프를 그려보려고한다. 전략은 각 노드마다 child 리스트를 생성한다. 그 노드가 갖고있는 자식노드를 통해 연결고리를 만드는것이다. 문제에서 데이터를 주고받는건 양방향이니 (자식 ->부모 , 부모 ->자식) 양방향으로 잡아주자. 사실 부모 -> 자식으로 데이터가 들어오는게 100%확정이라면 양방향으로 안해도 되지만, 그렇게 ..

문제분석 문제 목표: 모든 아파트에게 전파 송신하기위한 최소 전파탑의 갯수 특징 1. 이미 설치된 전파가 있음. 이 문제를 읽어보고 풀기전에 제한사항을 보면 아파트의 갯수가 2억이다. 저 어마어마한 숫자를 보고 아파트 갯수는 for문 돌리면 안대겟구나 라고 느낄것이다.. 따라서, 조금 아이디어가 필요하다. Ex) 만약 이미 설치된 전파가 없으면 어떨까? -> 그렇다면 전체 아파트 갯수 / 전파의범위가 될것이다. (단, 나머지가 존재하면 +1) 예로 아파트가 24며 전파가 1이면, 전파범위는 3이될것이고 최소 8개가 필요하다. 전파탑이 미리 설치된 경우의 전략은 어떻게 하면될가? 전파탑을 마치 배열을 절단하는도구??로 생각해보자. 예시로, 아파트가 20개 전파가 1, 미리 전파탑이 10지역에 설치됫다면 아..

https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제분석: 문제목표: 모든 문제를 풀 수 있을때까지 알고력과 코딩력을 단련시키자! 처음에 주어지는 초기 알고력과 코딩력이 있습니다. 이 알고력과 코딩력을 증가시키기위해선 다음과 같은 (선택지)방법이있습니다. 1. 트레이닝 트레이닝의 경우는 시간 1을소비해, 알고력 또는 코딩력중 1을 높일 수 있습니다. 2. 문제풀기 문제풀기의 경우는 일정한 시간을 소비해, 효율이 좋은 알고력 , 코딩력을 얻을수..

문제분석: 문제 목표: 두 사람이 Start 지점으로부터 A와 B로 가려고합니다. 하지만 두 사람은 이동 경로가 비슷 하다면 합승을 할 수 있습니다. 합승을 한다면, 합승한 경로만큼 택시비가 안들어갑니다. 그러므로, A와 B의 택시비가 최소로 나오는 택시비를 구해주세요. 이 문제는 Level4는 줘야하지 않나... 그 이유는 특수알고리즘의 지식 때문이다. 뭐.. 해당 문제를 처음부터 끝까지 코딩을 할수야 있겠지만, 어설프게 코딩을 치다간 놓치는 케이스와 효율성때문에 즉시 에러를 뱉을것이다. 여기서 특수 알고리즘이란 바로 "플로이드 와샬" 알고리즘이다. 최단거리 경로 구하는 문제에서 거의 치트키급의 존재 플로이드 와샬 이란? 정점과 정점 으로 가는 모~~~든 케이스의 최단거리를 구해주는 알고리즘이다. 구현..

문제분석: 문제목표: 무작위로 주어진 자연수를가진 A팀과 B팀이 있습니다. B팀이 최대 승점으로 이길때의 승점을 구해주세요. 문제의 핵심풀이 : 반복 1번 , IDX 2개 1. A , B 팀의 정렬 2. IDX 분리 A_IDX 와 B_IDX 3. 배열B 반복 작업 -> B[B_idx]> A[A_idx] 이면 A_idx를 증가 아니면 그냥 넘기면된다 그러면 끝이다. Level3 치곤 생각보다 너무 쉽게 풀려서 놀랐다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import java.util.*; class Solution { public int solution(int[] A, int[] B) { int answer = 0; Arrays.sort..

문제분석 정확성 : Level3 효율성 :(체감상) Level4 문제 목표: 갑부 어피치는가 모든 보석의 종류를 구입할 수 있는 최단 구간을 구해주세요. 첫 정확성 풀이: 시작이 될수있는 번호가 예시로 주어진 문제에선 1번부터 8번까지니, 이런 코드를 짯다. for문 안에다 start_shopping으로 시작번호 i 에서부터 최단구간을 구하는것이다. 그렇게나온 여러개의 start_shopping의 결과물들을 제일 구간이 짧고, 시작번호가 낮은 결과를 정렬해서 출력하는식으로 구현했다. But.... 기분 좋아졋다가 팍 식은 .. 시간복잡도를 한번 계산을 추측으로 해보니 O(T(종류)*log(n)*n) 정도 나온것같다. 여기서 최고 효율을 내려면 반복을 단 1번 O(n) 하게 짜야하는데 데이터를 1번만 순회..

문제분석: 문제 목표: x값, y값을 주어지는 노드들을 이진트리로 구성한뒤, 전위순회, 후위순회를 한 결과를 출력하세요. 이 문제의 출제의도는 이진트리를 구현하고 전위,후위 순회를 할 수 있는지를 물어보고있다. 처음에 이 문제가 DFS문제인가 싶어서 풀기시작했다가 이상함을 느꼇다. 당연하다면 당연하다.. 이진트리의 탐색 조건과 DFS/BFS의 완전탐색은 다른 로직이기때문이다. 이진트리를 써보기나했지(Heap), 구현해 본적이 없어서이다.. 그래서 이진트리 만드는법 문서를 참고를했다. 1. Node 생성하기 이진트리를 만드려면 Node가 필요하다. 그 Node 하나엔 노드번호, x좌표,y좌표, 오른쪽 자식노드 ,왼쪽 자식노드 의 정보가 꼭 필요하니 객체를 하나 생성해준다. 2. Node정보 입력 및 정렬 ..