Computer Science (20) 썸네일형 리스트형 [LeetCode/Easy] 20. Valid Parentheses 20. Valid Parentheses easy 문제는 아직까지 모르는 개념은 거의 없고, 이 문제를 어떤 자료 구조로 풀어야 효과적일지가 포인트인 것 같다. 따라서 내가 아는 알고리즘 중에 풀 수 없을까 고민해보자!!! 내 풀이 vs. 답안 풀이 내 풀이 답안 풀이 주어진 test case 외의 case {()}[] 에 대한 이해 (= 문제 이해) {()}[] 와 같은 예시는 invalid하다 생각함. 왜냐하면 바로 닫혀야 한다고 문제를 잘못 이해했기 때문. 주어진 예시 외에도 valid한지 invalid한지 판단할 수 있어야 하는데.. -> 근거에 대해서도 설명할 수 있어야 함. 생각만 하지 말고 말로 설명해보기! 설명할 수 없으면 아닌 것. {()}[]와 같은 예시는 valid함. 왜냐하면 꼭 연속.. [LeetCode/Easy] 1. Two Sum 1. Two Sum Testcase 통과한다고 해서 Submit 하면 안 된다 ㅠㅠ 제한시간 내에 Edge case를 생각해보고 그마저도 통과하면 Submit 하자! 내 풀이 vs. 답안 풀이 내 풀이 답안 풀이 O(n2)보다 적은 Time complexity를 고려한 구현 for문 2개 하면 O(n2)이 나오니 조합(combination)으로 먼저 구해야겠다 생각했지만 결국은 for문에 while문으로 구현함으로써 O(n2)이 됨.. -> 내 풀이의 time complexity 구하는 연습을 많이 해야겠다. Hash Table 내가 필요한 건 index고 알고 있는 건 숫자이므로 key는 nums 원소, value는 index여야 함. -> 내가 필요한게 뭐고 알고 있는게 뭔지 잘 정의.. [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 2 3 4 다음 목록 더보기
