Algorithm

[LeetCode] 1448. Count Good Nodes in Binary Tree (C#)

https://leetcode.com/problems/count-good-nodes-in-binary-tree/ Root 노드부터 현재 노드(X)까지 이동하는 동안 자신(X)보다 큰 값을 가진 노드가 없는 경우 X는 GoodNode가 된다.이때 주어진 이진 트리의 GoodNode 개수를 구하는 문제.  1. 풀이현재 노드의 값이 지금까지 지나온 값들과 비교해 같거나 크면 GoodNode 카운팅namespace PS.LeetCode;public class Solution_1448_1{ public int GoodNodes(TreeNode root) { var result = 0; Dfs(root, root.val, ref result); return resu..

[LeetCode] 328. Odd Even Linked List (C#)

https://leetcode.com/problems/odd-even-linked-list/description/   홀수번째 Node를 앞으로 당겨오고, 짝수번째 Node를 뒤로 밀어주는 문제. 제한 사항공간 복잡도 : O(1)시간 복잡도 : O(N) 1. 풀이더 이상 Odd 노드가 없을 때까지 Odd는 Odd끼리, Even은 Even끼리 연결마지막에 Odd의 tail과 Even의 head를 연결namespace PS.LeetCode;public class Solution_328_1{ public class ListNode { public int val; public ListNode next; public ListNode(int val = 0, ListN..

[LeetCode] 2095. Delete the Middle Node of a Linked List (C#)

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list linkedlist의 head가 주어진다.해당 linkedlist의 middle 노드를 삭제하고, 변경된 리스트의 head를 반환하는 문제.middle 노드의 기준은 리스트의 사이즈를 n이라고 가정하고 [ n / 2 ] 번째 노드를 뜻한다.  1. 원 포인터를 사용한 풀이middle 노드가 몇 번째인지 확인하는 과정이 들어간다.middle 노드 직전에서 순회를 멈추고 다다음 노드를 Next 로 바라본다.원소가 1개인 경우는 예외 케이스로 처리public class ListNode { public int val; public ListNode next; public L..

[LeetCode] 238. Product of Array Except Self (C#)

https://leetcode.com/problems/product-of-array-except-self/nums[i] 자신을 제외한 다른 모든 원소의 곱을 answer[i] 에 입력하여 반환하는 문제.nums 배열 원소의 prefix product 값과 suffix product 값은 32bit 정수값이 되도록 주어진다. 제한사항시간복잡도 O(n)나눗셈 연산 사용 불가  1. 나눗셈 연산을 사용했을 때의 답안결과가 0 이 되는 경우를 분리하여 코드를 구성한 번에 이해하기 어려운 조건식list 배열을 사용하여 불필요한 Array 변환 과정이 있음public class Solution { public int[] ProductExceptSelf(int[] nums) { var pro..

[백준 2250] 트리의 높이와 너비 (C++)

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이진 트리의 특성을 활용하는 문제 *주의 사항* 1. 트리의 루트 노드의 번호는 1이 아닐 수 있다. 2. 노드의 열의 위치는 이진 트리의 특성을 통해 결정된다. dfs를 통해 트리를 탐색하며 각 노드별 왼쪽 자식 노드 수의 합, 오른쪽 자식 노드 수의 합을 구한다. (1)과정을 통해서 각 노드별 자식 노드의 수를 알 수 있다. 자식 노드의 개수 + 1(현재 노드) 값이 N과 같으면 루트 노드임을 알 수 있다. 각 노드별 좌, 우 노드 수를 구..

[백준 17135] 캐슬 디펜스 (C++)

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 오랜만에 풀어본 백준! 백트래킹을 사용한 완전탐색 문제였다. 주의해야할 궁수의 공격 특징은 다음과 같다. 모든 궁수는 동시에 공격하며 같은 대상을 공격할 수 있다. (같은 적이 여러 궁수에게 공격당할 수 있다.) 적과의 거리가 D이하이면 공격한다. 가장 가까운 적을 공격한다. (가장 가까운 적이 어렷일 시 가장 왼쪽의 적을 공격한다.) 1번과 3번 특징 때문에 궁수의 위치에 따라서 잡을 수 있는 적의 수가 달라질 수 있다는 것을 눈치채야 한다. 궁수가 적절히 배치되어 적을 ..

[백준 16637] 괄호 추가하기 (C++)

16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 꿀 조건 1. 괄호 안에는 연산자 하나만 들어갈 수 있다. 꿀 조건 2. 중첩된 괄호는 사용할 수 없고, 항상 올바른 수식만 주어진다. 모든 괄호 안에는 정직하게 정수1, 연산자, 정수2 의 형태로 구성되어있다. 이 점을 활용해서 백트래킹을 사용한 브루트 포스로 현재 연산자를 둘러싸는 괄호를 추가하는 경우, 그냥 넘어가는 경우 모두에 대해서 수식의 값을 확인하면 답을 구할 수 있다. 현재 연산자가 괄호로 둘러싸일 경우, 바로 다음 연산자(현재인덱스+2..

[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다. 위 그래프는 2개로 나눌 수 있다. 위 그래프는 하나로 연결된 하나의 그래프이다. 모든 노드는 BFS 탐색의 시작점이 될 수 있다. BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다. 시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다. 개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다. 최종 코드 #include #include #include using namespace std; vector adj[201]; bool visited[201]; void bfs(int start){ queue que; que.push(start); visited[start..

[프로그래머스 level 3] 가장 먼 노드 (C++)

다익스트라 문제 시작노드는 1번으로 고정되어 있고, 간선 사이의 거리는 항상 1로 고정되어 있다. 일반적인 다익스트라 풀이와 거의 동일하다. 하지만 1번 노드에서 가장 멀리 떨어진 노드의 거리가 최댓값으로 갱신될 때마다 답을 1로 초기화 시켜야 한다. ex 우선순위 큐에 1번 노드가 있다. 가장 먼저 2번 노드에 방문하면 1번 노드와의 최대 거리가 1로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 1이 된다. 그리고 3번 노드에 방문하면 1번 노드와의 거리가 1이므로 현재 최댓값인 1과 동일하다. 따라서 가장 멀리 떨어진 노드의 수는 2로 갱신이 된다. 동일한 방법으로 4, 5, 6번 노드에 방문하면 최대 거리가 2로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 3이 될 것이다. 최종 코드 #includ..

[프로그래머스 level 3] 표편집 (C++)

카카오 2021 인턴 삽입, 삭제의 시간이 O(1)이거나 O(logn)이면 풀 수 있을 것 같았다. (알고보니 이동시간이 더 중요했다) log시간을 쓰려면 세그먼트 트리를 써야 할 것 같아서 너무 복잡해질게 예상되어서 그쪽으로는 시도하지 않았다. 예전에 백준에서 풀었던 'AC'문제랑 비슷하다고 생각했다. 그리고 학교 자료구조 시간에 리스트 과제 문제와 비슷했다. 처음에 리스트를 사용해 푸는 거라고 생각해서 List STL을 사용해서 시도해 보았다. STL에 있는 List는 삽입, 삭제는 O(1)이지만, 문제의 'U', 'D', 'Z' 명령어를 처리할 수가 없었다. 키 포인트 Z를 수행하기 위해서는 삭제된 행의 순서를 스택에 입력해 놓아야 한다. C는 리스트에서 값을 지우는 척만 하고 실제로 지워서는 안 ..