본문 바로가기

전체 글

 (124)
[Java] LeetCode 5번 Longest Palindromic Substring dp[start][end]에 start부터 end까지의 부분 문자열이 팔린드롬인지 여부를 저장하였다. 1이면 팔린드롬이고 0이면 아직 체크되지 않은 값이며, -1이면 팔린드롬이 아니다. 이중 포문을 돌면서 i와 j를 시작과 끝으로 하는 문자열이 팔린드롬인지 아닌지를 체크하였다. 이미 체크한 문자열들을 다시 검사하지 않기 위해서 dp를 사용하였으며 O(n^2) 보다는 조금 더 느린 풀이이지만 통과되었다. class Solution { public int checkPalindrome(int[][] dp, int start, int end, String s) { if (dp[start][end] != 0) { return dp[start][end]; } int len = end - start + 1; if (..
[Java] LeetCode 4번 Median of Two Sorted Arrays 문제의 조건에서는 O(log(m+n))으로 풀라고 주어졌다. 차근차근 접근하기위해서 느린방법으로 먼저 풀어보았다. 1. O(m+n) 시간복잡도 풀이 중간값을 찾기 위해서 두개의 배열을 합쳐준다. 병합정렬(merge sort)에서 두개의 배열을 합쳐주는 작업과 흡사하다. 두개의 배열의 값들을 비교해서 작은 값을 추가하고 인덱스를 증가시킨다. 인덱스가 전부 증가된 이후에는 남은 배열들을 추가해주는 작업을 해주면 된다. 합친 후에는 홀수개인지 짝수개인지에 따라서 값을 계산해주었다. class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; i..
[Java] LeetCode 3번 Longest Substring Without Repeating Characters 반복되는 문자가 없는 가장긴 부분문자열(substring)의 길이를 구하는 문제이다. for문으로 순차적으로 문자를 탐색하면서 map 언제 마지막으로 해당 문자를 마주쳤는지 저장한다. 만약 마주친 문자가 나온다면 마주친 문자의 개수가 부분문자열의 길이가 된다. 그리고 마주친 문자가 이전에 등장한 위치 + 1 부터 현재위치까지 map을 이용해 마주친 문자들을 넣어준다. class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0; Map visitedPos = new HashMap(); for (int i = 0; i < s.length(); i++) { Integer lastPos = visitedPos.get(Character..
[Java] LeetCode 2번 Add Two Numbers 총 3단계로 풀이가 진행되었다. l1과 l2의 길이가 다르고, 최대 100개까지 이어질 수 있다. 1. l1과 l2의 공통 조상을 먼저 더하여 노드로 만들어준다. 2. 공통조상을 제외하고 남은 l1또는 l2를 더해준다. 3. 마지막에 올림이 남았으면 노드를 추가해준다. 컴퓨터 구조에서 가산기를 구현하는 것과 비슷한다. carry라는 변수에 올림이 발생했는지를 저장하고 이것을 더할 때마다 계속 사용했다. 그리고 마지막에도 올림이 발생하였으면 최고 자리수가 1이 되도록 만드는 것이 포인트이다. class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode ..
Network Layer 1. 목적 한 호스트에서 다른 호스트로 패킷을 전달 하는 것이 목적이다. 2. 주요기능 네트워크 레이어의 중요한 기능은 포워딩(forarding)과 라우팅(routing)이다. 1) 포워딩 라우터의 인풋 링크로 패킷이 들어왔을 때, 라우터는 해당 패킷을 적절한 아웃풋 링크로 보내야한다. 2) 라우팅 패킷이 송신자로부터 수신자로 잘 전달이 될 수 있도록 경로를 결정해야한다. 이런 경로를 결정하는 것이 라우팅 알고리즘이다. 라우팅 알고리즘은 중앙에서 결정되거나 라우터들이 서로 통신하여 결정하는 방법이 있다. 운전하는 상황을 비유로 들어보면, 라우팅은 고속도로 인터체인지에서 어떤 길로 빠져나갈지 결정하는 것을 의미하며, 포워딩은 이런 인터체인지를 빠져나가는 것을 의미한다. 모든 라우터들은 라우팅 테이블을 가지..
[Java] 코딩 테스트 팁 보통 프로그래머스라는 플랫폼을 이용하여, 기업 코딩테스트를 치르게 된다. 많은 기업들의 코딩 테스트를 치르면서 내가 보통 이용하는 팁을 공유해보고자 한다. IDE의 사용이 허용된 경우에 내가 이용하는 방식이다. 1. 문제별로 Package를 나누어서 미리 준비해 둔다. 프로그래머스에서는 아래와 같이 Solution 이라는 클래스 명으로 문제를 해결하도록 되어있다. class Solution { public long solution(int price, int money, int count) { long answer = -1; return answer; } } 같은 프로젝트에서 Solution이라는 클래스 명이 중복되면 컴파일 시에 오류가 나게 되므로, 나의 경우는 문제 별로 p1,p2,p3... 로 패키지..
[Java] 2021 위클리 챌린지 7주차 - 입실 퇴실 모기업 코딩테스트의 기출문제로 당시 너무 어려워서 이것을 빼고 제출했던 기억이 있다. 프로그래머스의 정답자 수가 다른 주차수에 비해서 적은 것을 보면 풀기 어려운 문제임을 직감할 수 있다. 나는 그림을 그려서 문제의 규칙을 찾아보고자 했다. 먼저 입실을 1, 4, 2, 3 순으로 하고, 퇴실을 2, 1, 4, 3으로 하는 경우를 살펴보자. 입실과 퇴실을 일렬로 쓰고, 같은 번호를 선으로 이었다. 선으로 둘러쌓아진 부분이 각 번호가 존재한 시간을 나타내게 된다. 1번과 다른 번호들의 관계를 보면서 어떤 경우일 때 확정적으로 만나게 되는지 알아보자. - 1번과 2번의 관계 1번의 파란선이 2번의 노란선을 감싸고 있는 구조가 보이게 되는데, 이 경우에는 1번과 2번이 무조건 만났다는 것을 알 수 있다. 그래서..
[Java] 백준 1114번 - 통나무 자르기 통나무 최대 c번 자를 수 있고, 자르는 위치는 정해져 있다. 통나무를 잘라서 만들 수 있는 길이의 최대값의 최소값을 구하는 문제이다. 최대값의 최소값이라는 문구가 주어지면 이분 탐색의 방법을 사용하는 것이 가능하다. 이분 탐색은 주어진 조건을 만족하는 최소값이나 최대값을 log(n)의 시간 복잡도에 찾을 수 있기 때문이다. 잘리는 위치는 정해져있으므로 누적합을 이용해서 통나무의 길이를 더하고, 만약 누적합이 허용되는 길이보다 길다면, 이전의 위치에서 통나무를 잘라준다. 자르지 못하는 상황에서 길이를 초과한 경우에는 break를 이용해 통나무 탐색을 빠져나와서 left와 right의 값을 변경해준다. 첫번째 통나무의 길이를 최소로 하라는 조건이 주어져 있기 때문에, 뒤에서부터 통나무를 자른다. 만약 통나..

티스토리툴바