본문 바로가기

분류 전체보기

 (119)
[Leetcode] 328번 - 홀짝 연결 리스트 1. 문제 파악문제 링크: https://leetcode.com/problems/odd-even-linked-list/description/문제 정의: 홀수 인덱스인 노드끼리 연결하고 짝수 인덱스이 노드끼리 연결해라. (첫번째 노드부터 인덱스가 홀수로 시작한다.)문제의 제약 파악 (입력값 크기, 상수 조건)입력 크기: 0 ~ 10000시간 복잡도: O(N)추가 공간 복잡도: O(1)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 추가 공간 복잡도가 O(1)으로 제한되어있기 때문에 새로운 연결리스트를 생성하는 것이 아니고, 기존의 연결리스트에서 참조값 변경을 통해 재구조화 시키는 것이다. 문제를 풀기 위해서는 크게 다음 3개의 단계를 거쳐야한..
[Leetcode] 24번 - 페어의 노드 스왑 1. 문제 파악문제 링크: https://leetcode.com/problems/swap-nodes-in-pairs/description/문제 정의: 연결리스트에서 노드 쌍의 순서를 변경해라.문제의 제약 파악 (입력값 크기, 상수 조건): 시간복잡도 O(N)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 연결리스트를 순회하면서 노드간에 참조를 변경해야한다. 참조 값의 수정을 통해 연결리스트를 재구구조화하는 문제이다.연결리스트에서 노드 두개의 쌍끼리의 위치를 변경해야한다.first step: 첫번재 노드와 두번째 노드의 위치를 변경한다.second step: 세번째 노드와 네번째 노드의 위치를 변경한다.input: 1 2 3 4output: 2 1 4 31 2 3 4 // origi..
[Leetcode] 2번 - 두 수의 합 1. 문제 파악문제 링크: https://leetcode.com/problems/two-sum/description/문제 정의: 주어진 두 연결리스트의 각 노드에 저장된 숫자를 더해서 새로운 연결리스트를 생성해라.문제 주의점:주어진 두 연결리스트의 노드 개수가 다를 수 있다.두 개의 노드의 수를 저장한 값이 올림수가 있을경우, 주어진 연결리스트보다 노드 개수가 많은 연결리스트가 생성될수있다.시간복잡도: O(N)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)일단, 두개의 연결리스트를 순차적으로 노드를 순회하면서 덧셈을 진행하면 된다. 이렇게 덧셈을 진행해서 반환을 위한 새로운 연결리스트가 완성될때까지 반복문을 수행한다. 하지만, 위의 문제 주의점에서 두개의 조건에 따라 반복문 탈출조건을 설정해야..
[Leetcode] 42번 - 빗물 트래핑 1. 문제 파악해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.문제 링크: https://leetcode.com/problems/trapping-rain-water/ (백준: https://www.acmicpc.net/problem/14719)문제 정의:각 인덱스의 요소값은 벽의 높이를 나타낸다.양쪽에 벽으로 막혀야 물이 고일수 있으므로, 현재 지정한 벽에서 양쪽 벽의 높이를 알아야한다.현재 지정한 벽을 기준으로, 왼쪽에서 가장 높은벽과 오른쪽에서 가장 높은 중에서 작은 쪽과의 차이가 물이 고일수있는 양이다.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출[0,1,0,2,..
[Leetcode] 121번 - 주식을 사고팔기 가장 좋은 시점 1. 문제 파악문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/문제 요구사항: 배열 요소중에서 가장 작은값과 최대 값의 차이를 구해라. 단, 최소값이 최대값보다 작은 인덱스에 위치해야한다. 만일, 0보다 작다면 0을 반환해라.시간복잡도: 입력 크기가 100000개이므로 O(N)내의 풀이를 작성해야한다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출주어진 배열 요소를 하나 지정하고, 나머지 배열 요소중에서 지정한 요소보다 인덱스가 큰 요소들을 순회하는 방식으로 O(N^2) 내에 풀수있다. 2. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까? 브루트포스로 풀면 O(N^3)이 나온다. 따라서 O(..
[Leetcode] 561번 - 배열 파티션 1. 문제 파악문제 링크: https://leetcode.com/problems/array-partition/문제 정의: 주어진 배열에서 두개의 요소를 쌍을 지은 모든 경우의 수에서, 각 쌍의 최소값을 모두 더한 최대값을 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출브루트 포스로 풀수 있는 방법을 모르겠었다. 짧은 시간내에 배열의 요소의 모든 조합 쌍을 묶는 코드가 떠오르지 않았다. 따라서 부르트 포스로 문제 풀이가 떠오르지 않아므로 창의적인 아이디어가 필요할거라고 생각되었다. 2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?문제를 돌파할 창의적인 아이디어를 떠올리기 위해서 생각이 나지 않았다. 그치만 ..
[Leetcode] 1번 - 두 수의 합 1. 문제 파악문제 링크: https://leetcode.com/problems/two-sum/description/문제 정의: 배열의 요소중 두개의 합이 target인 인덱스 두개를 반환해라. 답은 하나이고 반환하는 인덱스의 순서는 상관없다. 단, 배열의 동일한 요소의 합은 포함되지않는다.문제의 제약 파악 (입력값 크기, 상수 조건) 2 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출배열을 순회하면서 순차적으로 요소 하나를 지정1번에서 지정한 요소를 제외하고, 배열을 순회하면서 순차적으로 나머지 요소를 지정지정한 두 요소의 합이 target과 동일한지 확인target과 동일하다면 두 요소의 인덱스를 반환, 동일하지 않다면 순회for (int i = 0; i 두개의 요소를 찾기 위해서 이중 순회를 해..
[Leetcode] 15번 - 세 수의 합 1. 문제 파악문제 링크: https://leetcode.com/problems/3sum/문제 요구사항: 주어진 배열에서 3개의 요소의 합이 0인 리스트중에서 중복되지 않는 리스트들을 반환해라.시간복잡도: 입력 크기가 3000개이므로 O(N^2)내의 풀이를 작성해야한다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출주어진 배열의 요소를 3개 골라야되므로 시간복잡도는 O(N^3)이다.for (int i = 0; i 2. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까?브루트포스로 풀면 O(N^3)이 나온다. 따라서 O(N^2) 이내로 풀어야한다. 세 개를 고르는데 O(N³)이니까 줄일 수 있는 방법은 없을까? 배열에서 요소를 하나 지정해놓고 배열을 한번 순회해서 처리할수있다면 O(N^2)이..

티스토리툴바