웨일의 블로그 웨일의 블로그

오늘 배운 점 중복코드는 함수화해보자. 문제1 - 이중 우선순위 큐 문제링크 문제 설명 이중 우선순위 큐를 구현해야 한다. 이중 우선순위큐란 큐 내의 최댓값과 최솟값을 모두 구할 수 있는 자료구조입니다. 3가지 연산이 주어집니다. 풀이 과정 일단, 우선순위 큐 하나만 가지고는 최대힙이나 최소힙 하나만 구현할 수 있을거라고 생각해서 최대힙, 최소힙을 각각 하나씩 가지는 Depq 클래스를 만들었습니다. 이후 숫자를 삽입할 땐 양 쪽 힙에 모두 넣어주고, 최댓값을 제거할 땐 최대힙에서 pop하고, 최솟값을 제거할 땐 최소힙에서 pop하면 되겠다고 생각했습니다. 하지만 이대로 코드를 작성한다면 한쪽 힙에서 제거한 숫자가 여전히 다른쪽 힙에 남아있게 되기 때문에 추가 작업이 필요했습니다. 그래서 각각의 힙에서 삭..

문제 - 피로도 문제링크 오늘 배운 점 일단 최적화 신경쓰지 말고 풀어놓고 생각하자 문제 설명 최대한 많은 던전을 탐험해야 하는 문제입니다. 던전 정보 리스트 dungeons는 [[최소 필요 피로도, 소모 피로도], ...]로 주어지며 현재 가지고 있는 피로도 k가 최소 필요 피로도 이상이어야 소모 피로도를 소비하고 던전에 입장할 수 있습니다. 가지고 있는 피로도k와 던전 리스트dungeons가 주어질 때, 최대 던전 탐험 횟수를 구하면 됩니다. 풀이 과정 처음 이 문제를 봤을 때는 DFS 풀이가 생각났습니다. 생각난 대로 풀면 되는데 뭔가 최적화를 하고싶어서 뭔가 피로도를 정렬한 후 for문과 힙을 사용하면 스케쥴러나 철로문제처럼 풀 수 있지 않을까 싶어 더 생각해보았지만 예외케이스를 처리할 방법이 생..

문제 - 삼각 달팽이 문제링크 오늘 배운 점 어렵게 생각하지 말자 문제 설명 이렇게 밑변의 길이와 높이가 n인 삼각형이 테두리부터 시계 반대방향으로 숫자가 1부터 시작해서 1씩 증가하며 채워집니다. 다 채운 후 맨 윗줄부터 정답배열에 넣어 반환하는 문제입니다. 접근 과정 결국 n이 주어질 때, 저 삼각형을 어떠한 자료구조에 넣어서 표현한 후 반환하는 문제입니다. 삼각형이라서 헷갈리기 때문에 왼쪽으로 정렬하고 봐 보면, 각 줄을 리스트로 하는 2차원 리스트로 표현할 수 있다고 생각했습니다. 우선 초기값을 모두 0으로 하고 리스트 크기는 1부터 n까지 증가하도록 만들었습니다. 이후 (0, 0)부터 시작해서 한칸씩 전진해나가며 숫자를 채우다가 더이상 못 채우는 조건일 때 끝납니다. cannotGo = ( la..

문제 - 점 찍기 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 배운 점 때로는 컴퓨터에게 일을 다 시키기보다 수학적 해법을 찾아봅니다. 더 빠른 풀이는 없는지 찾아봅니다. 문제 설명 제한 사항 입출력 예 k: 몇 배수로 점프할지를 나타냅니다. k = 2라면 0, 2, 4, 6, ... 이 됩니다. d: 원점 기준 최대 허용 거리를 나타냅니다. 접근 과정 사실 문제에서 원이 주어지진 않았지만 원점으로부터 거리가 $d$가 넘는 지점에는 점을 찍지 않는다는 규칙이 있기 때문에 반지름을 $d$로 하는 원을 그렸습니다. 다시말해 $ xy $ 좌표계..

문제 1 - 당구 연습 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 배운 점 타인의 배울 점을 배웁니다. 수학적 직관을 사용해야 할 때가 있습니다. 문제를 똑바로 읽습니다. 문제 설명 흰 공이 당구대에 원쿠션 해서 검은 공을 맞추는 경우 중 가장 이동 경로가 가장 짧은 경우의 경로 길이를 구하는 문제입니다. 점선이 바로 경로입니다. 입출력 예 m: 당구대의 가로 길이 n: 당구대의 세로 길이 startX: 흰 공의 x 좌표 startY: 흰 공의 y 좌표 balls: 검정 공들의 위치 접근 과정 우선 처음에는 당구대의 테두리를 순회하면서 ..

문제 1 - 배달 문제링크 오늘 배운 점 문제의 장식을 치워버리고 어떤 알고리즘을 적용할 수 있는지 생각하자. 여러 가지의 풀이 방법이 떠오를 땐 가장 쉽게 구현할 수 있는 것을 택하자. 문제를 꼼꼼히 읽어보자. 사고 과정 1번 마을에서 다른 마을까지 K시간 내에 배달할 수 있는 마을들을 구하는 문제다. 마을과 통행시간으로 해당 문제를 장식해 놓은 것을 확인했다. 따라서 장식을 제거하여 그래프상의 노드와 간선 가중치로 치환한다. 즉, 1번 노드로부터 최소 거리가 K 이하인 모든 노드들을 구하면 된다. 이에 맞는 알고리즘은 다익스트라 알고리즘이다. 다익스트라 알고리즘을 알고 있었다면 바로 눈에 보이는 문제였다. """ 다익스트라 문제 특정 점에서 다른 모든 지점까지의 최단거리를 구하면 된다. """ imp..

문제 1 - 다리를 지나는 트럭 문제링크 오늘 배운 점 복습의 힘은 대단하다. 이는 일반적인 공부에만 적용되는 것이 아니라 코딩테스트 문제를 풀 때도 마찬가지로 적용된다. 변수의 초깃값을 제대로 설정하는 건 매우 중요하고 때때로는 까다롭다. 이러한 까다로움은 배열의 인덱스를 정확히 설정하는 것과 유사하다. 과정 이 문제는 지금까지 총 3번 마주쳤다. 첫번째는 문제 이해를 못해서 넘어갔고, 두번째엔 여러번의 제출을 통해 엣지케이스들을 처리하면서 통과했다. 오늘은 아는 문제라는 걸 깨닫고 머리속으로 어떤 식으로 로직을 짜야 할지 구상한 후 바로 그대로 코드를 짜고 제출을 했고 바로 통과했다. 첫번째로 마주쳤을 때 문제 이해가 어려웠던 이유는 위 그림에 있다. 위 그림에서 경과시간이 1~2 이렇게 되어있는 건..

뭐 하고 있는지: 99클럽 이게 뭔지: 항해99에서 운영하는 코테 스터디 어떻게 하는 건지: 매일 주어진 문제를 풀고, 월목은 게더타운에서 다같이 풀기 계기: 개발자 오픈카톡방에 99클럽 홍보 메시지가 올라왔고, 재밌겠다 싶어서 신청했다. 가격도 무료였다. 기간: 3/25 ~ 4/25 매주 월,목 9pm~11pm 난이도: 상(챌린저) 등급 신청 오늘 배운 점 1. 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙성을 찾아라. 2. 사이클은 어디에서나 시작해도 사이클 내의 모든 노드를 방문할 수 있다. 문제 1 - 마법의 엘리베이터 문제 링크 문제를 관통하는 키: 최우항 자리수부터 0으로 만들기, 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙을 찾기 임의의 숫자 n이 주어질 때, +-10^x..