티스토리

웨일의 블로그

검색하기

블로그 홈

웨일의 블로그

dev-forward.tistory.com/m

https://github.com/sangeon-ahn

구독자: 4

방명록 방문하기

주요 글 목록

리트코드 Top Inteview 150 후기 리트코드는 알고리즘 문제 사이트이다.그중 좋은 문제 150개를 엄선해서 모아놓은 분류가 있는데 이게 Top Interview 150이다.이거를 생각날 때마다 하나씩 풀다보니 어느새 다풀었다. 누구는 알고리즘이 현업에서 쓸 데 없다고도 하고누구는 알고리즘 잘하는 사람이 현업 개발 못하는걸 본 적 없다고 한다. 현업 개발을 많이 겪진 못했지만 지금까지 경험으로 보면일단 도메인을 많이 아는게 중요하다. 선임 개발자분들을 보면 개발 40 디버깅 40 회의 20의 비중을 두고 있다.디버깅 비중이 크다.예상치 못한 예외케이스가 발생할 수 있다는걸 알기 위해서는 일단 도메인에 대한 지식이 필요하다. 그리고 미처 처리하지 못한 예외케이스가 발생해 디버깅을 해야하는 경우에도 문제 발생 원인을 파악할 때 도메인 지식이 필.. 공감수 1 댓글수 1 2024. 7. 7.
99클럽 코테 스터디 17일차 TIL - 중복, 연속적으로 계산할 땐 누적합 문제 - 우박수열 정적분 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 우박수열 만드는법 양의 정수 k가 주어지고, k에서 시작하는 우박수열을 만듭니다. 이후, 우박수열을 y값으로 하고 x값은 0부터 각 수열 생성시마다 x = 1, x = 2 이런식으로 1씩 증가하도록 해서 (x, y)가 정해지며, 그래프를 그릴 수 있습니다. 마지막으로 넓이를 구해야 하는 x의 범위들이 주어지는데, 이때 해당 x 범위와 x축, y축, 그래프가 형성하는 영역의 넓이를 구하면 됩니다. 제한 사항 k: 1만 이하 ranges 길이: 1만 이하 풀이 과정 이.. 공감수 0 댓글수 0 2024. 4. 10.
99클럽 코테 스터디 16일차 TIL - 비슷한 문제가 생각날 때 문제1 - 부대 복귀 문제링크 문제 설명 양방향 그래프가 주어지고 출발지 노드들과 목적지가 주어질 때, 각 출발지에서 목적지 노드까지의 최단경로 거리를 구하는 문제입니다. 목적지에 도달할 수 없다면 -1입니다. 제약조건 노드n: 최대 10만개 간선roads: 최대 50만개 출발지sources: 최대 500개 풀이 과정 처음엔 그래프상에서 최단경로 길이를 구하는 문제라서 다익스트라를 사용해서 출발지 노드에서 목적지 노드까지의 최단경로거리를 구했습니다. 시행착오1(다익스트라, 실패) import heapq def solve(graph, dists, src, dest): q = [] dists[src][src] = 0 heapq.heappush(q, (0, src)) while q: curDist, curPo.. 공감수 0 댓글수 0 2024. 4. 9.
99클럽 코테 스터디 15일차 TIL - 이미 방문한 곳도 다시 가는 DFS 문제 - 양과 늑대 문제링크 문제 설명 이렇게 생긴 이진트리가 주어집니다. 0번 루트노드부터 탐색을 시작하는데, 노드에 양이 있으면 양 누적 카운트를 + 1 해주고, 늑대가 있으면 늑대 누적 카운트를 + 1 해줍니다. 그런데 [양 누적 1 해서 일단 왼쪽 양을 구한 후, 1->0->8->7->8->9 이렇게 이동해서 우측 서브트리의 양까지 다 구할 수 있습니다. 지금까지의 카운트는 양:4마리, 늑대:1마리이므로, 4번, 6번 늑대까지 방문해도 4대3으로 아직 괜찮습니다. 그래서 5번 양까지 구할 수 있습니다. 제한사항 트리의 노드 개수는 최대 17입니다. 풀이 과정 일단, 어떻게든 트리를 순회하면서 양과 늑대를 카운트해서 최대로 구할 수 있는 양을 구해야 합니다. 그리고, 한번 방문한 노드를 다시 방문할.. 공감수 0 댓글수 0 2024. 4. 8.
99클럽 코테 스터디 14일차 TIL - Brute Force같은 DFS 문제 - 타겟 넘버 문제링크 문제 설명 이렇게 numbers와 target이 입력으로 주어지면, numbers의 모든 숫자들을 각각 더하든지 빼든지 해서 target값을 만들어내는 경우의 수를 구하는 문제입니다. 첫번째 예시 입력에 대해 다음과 같은 경우의 수들이 있습니다. 이런식으로 각 숫자 앞에 +를 붙일건지 -를 붙일건지 선택해서 다 계산한 결과가 target이면 됩니다. 풀이 과정 각 숫자에는 부호가 할당되어야 합니다. 그리고 각 숫자마다 붙는 부호는 다른 숫자들과 독립적입니다. 이러면 각 숫자마다 +-의 두가지 경우가 있습니다. 모든 숫자에 대해 +-를 붙이는 경우의 수를 구하는 데 좋은 알고리즘은 DFS가 있습니다. """ 각 숫자에 대해 -, + 할당 dfs(order, val) """ de.. 공감수 0 댓글수 0 2024. 4. 7.
99클럽 코테 스터디 12일차 TIL - 한계가 있는 풀이는 과감히 버리기 오늘 배운 점 갑자기 떠오른 아이디어가 실마리가 될 수 있습니다. 빠를거라고 예상한 풀이가 예상외로 느릴 수 있습니다. 문제 - 디펜스 게임 문제링크 문제 설명 병사 n명으로 enemy([n1, n2, n3,...])을 상대해야 합니다. 1라운드에는 n1, 2라운드에는 n2... 이런식으로 각 라운드마다 상대해야 하는 적의 수가 enemy에 담겨 있습니다. 그리고 병사와 적은 1대1 교환비로 적을 처리할 수 있습니다. k개의 무적권이 주어지는데, 무적권 1개를 사용하면 해당 라운드는 병사를 사용하지 않고 다음 라운드로 넘어갈 수 있습니다. 이때, 승리할 수 있는 최대 라운드를 구하면 됩니다. 제약 조건 n이 10억인 점은 문제가 되지 않지만 enemy가 100만이기 때문에 O(N)이나 O(NlogN) 과.. 공감수 0 댓글수 0 2024. 4. 5.
99클럽 코테 스터디 11일차 TIL - 알고리즘의 원리를 정확히 알고있기 문제 - 등산코스 정하기 문제링크문제 설명산이 있고 산에는 지점들이 있습니다. 지점은 여러 개의 출발지와 여러 개의 정상, 그리고 일반 지점들이 있습니다. 출발지에서 시작해서 정상을 찍고 다시 원래 출발지로 돌아오는 경로가 있을 때, 해당 경로는 시작 출발지와 끝 출발지는 같고, 중간에 다른 출발지를 거치지 않고, 정상은 무조건 한번만 거쳐야 합니다. 이때, 위 조건을 만족하는 모든 경로 각각에서 각 지점을 건너는데 걸리는 시간 중 가장 긴 시간이 있을텐데 이를 intensity라 하고, 모든 경로를 통틀어 최소 intensity를 구하는 문제입니다. 풀이 과정처음에는 같은 지점을 여러번 반복해서 방문할 수 있으므로, 비트마스킹을 이용헤서 중복 경로 체크를 해야 하는 줄 알았습니다. 하지만 이전에 방문한.. 공감수 0 댓글수 2 2024. 4. 4.
99클럽 코테 스터디 10일차 TIL - 익숙한 문제는 빠르게 풀기 문제 - 무인도 여행 문제링크 문제 설명 2차원 격자 maps가 주어지고, 격자는 바다를 의미하는 'X'와 1~9 사이의 숫자로 이루어져 있습니다. 해당 칸이 숫자라면 땅을 의미하고, 상하좌우로 서로 연결된 땅은 하나의 섬입니다. maps 내의 모든 섬에 방문할 때, 각 섬에 적혀있는 모든 숫자를 다 더한 값을 담아 반환하면 됩니다. 풀이 과정 일반적인 BFS 섬 찾기 문제입니다. maps를 2중 for 문 순회하며 섬을 찾아 마킹하며 숫자를 더한 후 BFS가 끝나면 더한 값을 저장해 놓다가 모든 순회가 끝나면 반환하면 됩니다. from collections import deque def solution(maps): answer = [] n = len(maps) m = len(maps[0]) dx = [.. 공감수 0 댓글수 0 2024. 4. 3.
99클럽 코테 스터디 9일차 TIL - 획기적인 풀이는 이해하고 넘어가자 문제 - 택배상자 문제링크 오늘 배운 점스택의 활용도는 무궁무진하고 어렵습니다. 획기적인 풀이가 답이 될 수 있는 이유를 알고 넘어가는건 재밌습니다. 문제 설명메인 컨베이어 벨트에 1부터 n의 번호가 달린 상자가 n,n-1,...3,2,1 이런식으로 정렬되어 왼쪽에서 오른쪽으로 이동하고 있습니다. 그리고, 택배원은 자기가 생각한 순서대로 상자를 트럭에 실어야 합니다. 택배원은 보조 컨베이어벨트에 상자를 차곡차곡 옮길 수도 있습니다. 보조 컨베이어벨트는 스택같은 LIFO 구조라고 보면 됩니다. 이때 택배원은 최대 몇개의 상자를 트럭에 실을 수 있는지 구하는 문제입니다. 풀이 과정세 가지 경우로 나누어 풀이했습니다. 1. 메인 컨베이어 벨트의 맨 앞 상자가 자신이 처리해야 하는 상자와 같을 때 2. 보조 컨.. 공감수 0 댓글수 0 2024. 4. 2.
99클럽 코테 스터디 8일차 TIL - 좀 더 구조화된 답을 내보자 오늘 배운 점 중복코드는 함수화해보자. 문제1 - 이중 우선순위 큐 문제링크 문제 설명 이중 우선순위 큐를 구현해야 한다. 이중 우선순위큐란 큐 내의 최댓값과 최솟값을 모두 구할 수 있는 자료구조입니다. 3가지 연산이 주어집니다. 풀이 과정 일단, 우선순위 큐 하나만 가지고는 최대힙이나 최소힙 하나만 구현할 수 있을거라고 생각해서 최대힙, 최소힙을 각각 하나씩 가지는 Depq 클래스를 만들었습니다. 이후 숫자를 삽입할 땐 양 쪽 힙에 모두 넣어주고, 최댓값을 제거할 땐 최대힙에서 pop하고, 최솟값을 제거할 땐 최소힙에서 pop하면 되겠다고 생각했습니다. 하지만 이대로 코드를 작성한다면 한쪽 힙에서 제거한 숫자가 여전히 다른쪽 힙에 남아있게 되기 때문에 추가 작업이 필요했습니다. 그래서 각각의 힙에서 삭.. 공감수 0 댓글수 0 2024. 4. 1.
99클럽 코테 스터디 7일차 TIL - 풀 수 있는 방법으로 바로 풀자 문제 - 피로도 문제링크 오늘 배운 점 일단 최적화 신경쓰지 말고 풀어놓고 생각하자 문제 설명 최대한 많은 던전을 탐험해야 하는 문제입니다. 던전 정보 리스트 dungeons는 [[최소 필요 피로도, 소모 피로도], ...]로 주어지며 현재 가지고 있는 피로도 k가 최소 필요 피로도 이상이어야 소모 피로도를 소비하고 던전에 입장할 수 있습니다. 가지고 있는 피로도k와 던전 리스트dungeons가 주어질 때, 최대 던전 탐험 횟수를 구하면 됩니다. 풀이 과정 처음 이 문제를 봤을 때는 DFS 풀이가 생각났습니다. 생각난 대로 풀면 되는데 뭔가 최적화를 하고싶어서 뭔가 피로도를 정렬한 후 for문과 힙을 사용하면 스케쥴러나 철로문제처럼 풀 수 있지 않을까 싶어 더 생각해보았지만 예외케이스를 처리할 방법이 생.. 공감수 0 댓글수 0 2024. 3. 31.
99클럽 코테 스터디 6일차 TIL - 코테에 비슷한 문제가 나왔다. 문제 - 삼각 달팽이 문제링크 오늘 배운 점 어렵게 생각하지 말자 문제 설명 이렇게 밑변의 길이와 높이가 n인 삼각형이 테두리부터 시계 반대방향으로 숫자가 1부터 시작해서 1씩 증가하며 채워집니다. 다 채운 후 맨 윗줄부터 정답배열에 넣어 반환하는 문제입니다. 접근 과정 결국 n이 주어질 때, 저 삼각형을 어떠한 자료구조에 넣어서 표현한 후 반환하는 문제입니다. 삼각형이라서 헷갈리기 때문에 왼쪽으로 정렬하고 봐 보면, 각 줄을 리스트로 하는 2차원 리스트로 표현할 수 있다고 생각했습니다. 우선 초기값을 모두 0으로 하고 리스트 크기는 1부터 n까지 증가하도록 만들었습니다. 이후 (0, 0)부터 시작해서 한칸씩 전진해나가며 숫자를 채우다가 더이상 못 채우는 조건일 때 끝납니다. cannotGo = ( la.. 공감수 0 댓글수 0 2024. 3. 30.
99클럽 코테 스터디 5일차 TIL - 컴퓨터에게 일을 다 시키지 말자 문제 - 점 찍기 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 배운 점 때로는 컴퓨터에게 일을 다 시키기보다 수학적 해법을 찾아봅니다. 더 빠른 풀이는 없는지 찾아봅니다. 문제 설명 제한 사항 입출력 예 k: 몇 배수로 점프할지를 나타냅니다. k = 2라면 0, 2, 4, 6, ... 이 됩니다. d: 원점 기준 최대 허용 거리를 나타냅니다. 접근 과정 사실 문제에서 원이 주어지진 않았지만 원점으로부터 거리가 $d$가 넘는 지점에는 점을 찍지 않는다는 규칙이 있기 때문에 반지름을 $d$로 하는 원을 그렸습니다. 다시말해 $ xy $ 좌표계.. 공감수 4 댓글수 2 2024. 3. 29.
99클럽 코테 스터디 4일차 TIL - 타인의 풀이를 통해 배우기 문제 1 - 당구 연습 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 배운 점 타인의 배울 점을 배웁니다. 수학적 직관을 사용해야 할 때가 있습니다. 문제를 똑바로 읽습니다. 문제 설명 흰 공이 당구대에 원쿠션 해서 검은 공을 맞추는 경우 중 가장 이동 경로가 가장 짧은 경우의 경로 길이를 구하는 문제입니다. 점선이 바로 경로입니다. 입출력 예 m: 당구대의 가로 길이 n: 당구대의 세로 길이 startX: 흰 공의 x 좌표 startY: 흰 공의 y 좌표 balls: 검정 공들의 위치 접근 과정 우선 처음에는 당구대의 테두리를 순회하면서 .. 공감수 1 댓글수 0 2024. 3. 28.
99클럽 코테 스터디 3일차 TIL - 문제에 맞는 알고리즘을 떠올리기 문제 1 - 배달 문제링크 오늘 배운 점 문제의 장식을 치워버리고 어떤 알고리즘을 적용할 수 있는지 생각하자. 여러 가지의 풀이 방법이 떠오를 땐 가장 쉽게 구현할 수 있는 것을 택하자. 문제를 꼼꼼히 읽어보자. 사고 과정 1번 마을에서 다른 마을까지 K시간 내에 배달할 수 있는 마을들을 구하는 문제다. 마을과 통행시간으로 해당 문제를 장식해 놓은 것을 확인했다. 따라서 장식을 제거하여 그래프상의 노드와 간선 가중치로 치환한다. 즉, 1번 노드로부터 최소 거리가 K 이하인 모든 노드들을 구하면 된다. 이에 맞는 알고리즘은 다익스트라 알고리즘이다. 다익스트라 알고리즘을 알고 있었다면 바로 눈에 보이는 문제였다. """ 다익스트라 문제 특정 점에서 다른 모든 지점까지의 최단거리를 구하면 된다. """ imp.. 공감수 0 댓글수 0 2024. 3. 27.
99클럽 코테 스터디 2일차 TIL - 반복 학습의 힘 문제 1 - 다리를 지나는 트럭 문제링크 오늘 배운 점 복습의 힘은 대단하다. 이는 일반적인 공부에만 적용되는 것이 아니라 코딩테스트 문제를 풀 때도 마찬가지로 적용된다. 변수의 초깃값을 제대로 설정하는 건 매우 중요하고 때때로는 까다롭다. 이러한 까다로움은 배열의 인덱스를 정확히 설정하는 것과 유사하다. 과정 이 문제는 지금까지 총 3번 마주쳤다. 첫번째는 문제 이해를 못해서 넘어갔고, 두번째엔 여러번의 제출을 통해 엣지케이스들을 처리하면서 통과했다. 오늘은 아는 문제라는 걸 깨닫고 머리속으로 어떤 식으로 로직을 짜야 할지 구상한 후 바로 그대로 코드를 짜고 제출을 했고 바로 통과했다. 첫번째로 마주쳤을 때 문제 이해가 어려웠던 이유는 위 그림에 있다. 위 그림에서 경과시간이 1~2 이렇게 되어있는 건.. 공감수 1 댓글수 2 2024. 3. 26.
99클럽 코테 스터디 1일차 TIL - 문제를 관통하는 키 찾기 뭐 하고 있는지: 99클럽 이게 뭔지: 항해99에서 운영하는 코테 스터디 어떻게 하는 건지: 매일 주어진 문제를 풀고, 월목은 게더타운에서 다같이 풀기 계기: 개발자 오픈카톡방에 99클럽 홍보 메시지가 올라왔고, 재밌겠다 싶어서 신청했다. 가격도 무료였다. 기간: 3/25 ~ 4/25 매주 월,목 9pm~11pm 난이도: 상(챌린저) 등급 신청 오늘 배운 점 1. 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙성을 찾아라. 2. 사이클은 어디에서나 시작해도 사이클 내의 모든 노드를 방문할 수 있다. 문제 1 - 마법의 엘리베이터 문제 링크 문제를 관통하는 키: 최우항 자리수부터 0으로 만들기, 예제에 대해 답을 구하는 과정을 단계별로 작성하며 규칙을 찾기 임의의 숫자 n이 주어질 때, +-10^x.. 공감수 0 댓글수 1 2024. 3. 25.
백준 11724 연결 요소의 개수 문제: https://www.acmicpc.net/problem/11724 문제 간단 설명 방향 없는 그래프가 주어질 때, 간선으로 연결되어 있지 않고 서로 떨어진 Connected Component컴포넌트의 개수를 구하면 된다. 간단히 말해 섬이 몇개 있는지 구하는 문제 시행착오 vis 배열을 fill 함수로 초기화할 때, vis는 1번 인덱스부터 N개를 사용하므로 fill(vis, vis+N+1, -1)을 해줘야 했는데 이 점을 고려하지 못하고 fill(vis, vis+N, -1)으로 초기화를 해준 탓에 오류가 발생하게 되었다. 처음에 그래프 배열을 선언할 때 main함수 내에서 vector graph[N]으로 그래프의 크기를 동적으로 할당하고자 하였지만 오류가 발생해서 전역변수로 main 외부에 N.. 공감수 0 댓글수 0 2023. 1. 1.
백준 11286번 절대값 힙 문제 간단 설명 1. N개의 정수를 입력받는다. 2-1. 도중에 입력으로 0이 들어오면 저 지금까지 들어온 숫자 중에서 절대값이 가장 작은 수를 출력해준다. 2-2. 만약 절대값이 같은 수가 존재한다면(1과 -1과 같이), 실제 값이 더 작은 수를 출력해준다.(-1 출력) 시행착오 arr[i][0]에는 절댓값 i의 음수 개수를, arr[i][1]에는 절댓값 i의 양수 개수를 저장해서 풀이를 하려고 했다. 하지만 입력값이 -2의 31승 ~ 2의 31승 인 점을 고려해서 arr의 1차원의 크기를 1 0 && -2 < 0 == true 이므로 입력과 반대 순서로 swap된다. 공감수 0 댓글수 0 2022. 12. 31.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.