Computer Science/알고리즘 (18) 썸네일형 리스트형 [LeetCode/Medium] 146. LRU Cache 146. LRU Cache 내 풀이 vs. 답안 풀이 내 풀이 답안 풀이 LRU cache 구현하는 data structure (단, get()과 put()의 시간 복잡도가 $O(1)$이어야 함) Dictionary Dictionary & Double Linked List cf) Key를 가진 Double Linked List는 시간 복잡도가 항상 $O(1)$ Edge case (list is empty and capacity is 1) 생각지도 못한 케이스라 방어로직 만들지 않음 head와 tail에 대한 dummy 노드 생성 Least Recently Used (LRU)에 대한 이해 least랑 latest 헷갈려서 가장 최근에 사용한 key를 삭제해야 한다고 생각함.. ah... 가장 오래 사용하지.. [이코테] 게임 개발 풀이 과정 자그마치 2시간이 넘게 걸린 풀이~^^ 하.. 알고리즘 진짜 만만하게 봤는데 요즘 한없이 작아지는 중이다... 계속하다 보면 늘겠지~ 하하하 그래도 이전 문제 통해서 배운 거 이번엔 써먹었다..! 게임 개발 문제는 시간제한이 40분이었다. 지금까지 풀어본 연습문제 중 최대였다. N x M 직사각형이 있고 각 칸은 육지(0) 혹은 바다(1)이다. 단, 바다는 갈 수 없다. 게임 캐릭터가 있는 칸의 좌표는 (A, B)이고 A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 말을 좀 어렵게 해 놨는데 N x M 직사각형을 행렬로 보고 A랑 B는 그냥 몇 행, 몇 열이라고 보면 된다. (1,1)이면 1행 1 열인 거다. 특이한 건 바라보는 방향 d까지 주어진다. d의 값도 .. [이코테] 왕실의 나이트 풀이 과정 우선 이 문제는 시간제한이 20분인데 20분 안에 풀지 못했다. 시간도 초과되고 풀다가 막히니까 하기가 싫어졌다. 상하좌우 문제와 굉장히 비슷해서 똑같이 풀면 된다고 생각했는데 막상 적용하기가 어려웠다. 머리를 좀 더 써야 했는데 더 이상 생각하기가 싫었다. 그래서 일단 모로 가도 서울만 가면 된다고, 그냥 일일이 case를 나눠 작성해서 통과했다. 1시간 6분 만이었다. 생각하기가 싫을 땐 어떻게 해야 할까? ㅋㅋㅋ 하.. 연습이라 마음이 풀어진 건가.. 실전에서는 보통 괜찮은 해결책이 떠오르지 않을 때 일단 다른 문제로 넘어갔다 다시 온다. 처음 생각나는 풀이가 너무 노가다인 것 같을 때 어떤 규칙이 있는지를 생각해보자. 최대한 규칙을 찾아보려 노력하지만 마땅히 떠오르지 않을 때는 차라리 .. [이코테] 시각 풀이 과정 1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다. 문제의 길이가 굉장히 짧았다. 고등학교 때 확률과 통계에서 경우의 수 문제를 푸는 것 같았다. '하나라도 포함되는'을 보자마자 '하나 이상'일 때는 전체 경우의 수에서 하나도 없을 때를 빼야 한다는 생각의 흐름이 자동적으로 이어졌다. 역시 K-입시.. ^^ 입력 첫째 줄에 정수 N이 주어지므로 정수 N과 입력 조건을 메모했다. 내가 본 입력 조건 중 범위가 작았던 편에 속하는데, 최소 0시 0분 0초이고 최대 23시 59분 59초이다. 그리고 출력해야 하는 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수도 메모했다. 2. 알고리즘을 떠올리고 적용하려고 노력한다. 구현 예시이므로 구현을 먼저 적었고 경우의 수 보자마자 완.. [이코테] 상하좌우 풀이 과정 1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다. N x N 크기의 정사각형 공간이 주어진다. 시작 좌표는 항상 (1,1)이며, 최대 좌표는 (N, N)이다. 주의할 점은 정사각형 공간을 벗어나는 움직임은 무시된다는 점이다. 입력 첫째 줄에 공간의 크기를 나타내는 N이 주어지고, 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. 입력 조건을 메모했고, 최종적으로 도착하는 지점의 좌표를 출력하면 된다. 2. 알고리즘을 떠올리고 적용하려고 노력한다. 구현 문제이므로 알고리즘을 떠올리기는 쉬웠으나 막상 소스코드로 구현하는 데는 어려움이 있었다. 주의할 점이 없었다면 바로 코딩할 수 있는 문제였으나 주의할 점으로 인해 문제가 조금 까다로워졌다. 3. 필요한 변수에 대해서는 변.. 이전 1 2 3 4 다음
