본문 바로가기

전체 글

 (102)
[LeetCode] 3번: Longest Substring Without Repeating Characters 문제링크 : https://leetcode.com/problems/longest-substring-without-repeating-characters/ 문제풀이 중복되는 문자를 포함하지 않는, 가장 긴 구간을 찾는 문제이다. 방법1) 입력된 문자의 처음부터 끝까지 중복되지 않는 모든 경우를 찾는다. 가장 단순한 방법이지만, 이렇게 풀면 n까지 for문을 두 번 돌게 되므로 O(n2)의 시간복잡도가 나온다. 방법2) 투 포인터 알고리즘을 사용한 방법이다. 투 포인터 알고리즘은 인덱스를 가리키는 두 개의 포인터를 이동시키는 방법이다. 포인터 i, j가 있다고 하면, 조건에 일치하는 경우 j 포인터 이동, 일치하지 않는 경우 i 포인터를 이동시킨다. Set은 중복을 허락하지 않는 자료구조이다. Set에 값을 ..
[LeetCode] 2번: Add Two Numbers 문제링크 : https://leetcode.com/problems/add-two-numbers/ 문제풀이 두 링크드 리스트의 각 숫자끼리 짝지어 차례로 더하는 문제이다. 링크드 리스트의 길이가 서로 다를 때 오류가 발생하여 한쪽 값이 null이면 숫자 0을 더하도록 수정했다. 소스코드 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode nextNode = null; List..
[LeetCode] 1번: Two Sum 문제링크 : https://leetcode.com/problems/two-sum/ 문제풀이 배열의 데이터들을 두 개씩 더하면서 target과 일치하는지 체크한다. 소스코드 class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length - 1; i++) { for (int j = i + 1; j < nums.length; j++) { int sum = nums[i] + nums[j]; if (sum == target) { return new int[] {i, j}; } } } return null; } }
[백준] 4963번: 섬의 개수 문제링크 : https://www.acmicpc.net/problem/4963 문제풀이 DFS/BFS로 풀 수 있는 문제이다. DFS로 풀었으며 상하좌우, 대각선 네 방향으로 이동하면서 땅이 있는지 체크하였다. 소스코드 import java.io.*; import java.util.*; public class p_4963 { static final int MAX = 50; static int[][] map = new int[MAX][MAX]; static int[] dx = new int[] {0, -1, -1, -1, 0, 1, 1, 1}; static int[] dy = new int[] {1, 1, 0, -1, -1, -1, 0, 1}; public static void main(String[] a..
[자료구조] Set - HashSet, TreeSet, LinkedSet Set이란? 중복 데이터를 허용하지 않는 자료구조이다. 데이터들은 순서를 가지지 않는다. 따라서 Set에 추가한 데이터들을 그대로 출력해보면, 추가한 순서 그대로 출력이 되지 않는다. 자바에서 제공하는 Set 컬렉션은 HashSet, TreeSet, LinkedSet이 있다. 1. HashSet 데이터를 무작위로 해쉬 테이블에 저장한다. HashSet은 Set 중 가장 많이 사용되는 클래스이다. Set 중 성능이 가장 좋으며, 중복을 허용하지 않는다. 2. TreeSet 데이터를 이진 검색 트리의 형태로 저장한다. 따라서 데이터는 항상 정렬된 상태로 저장된다. (따라서 HashSet보다 성능이 낮다.) 기본적으로 오름차순으로 정렬이 되며 정렬 기준을 따로 정의할 수 있다. 3. LinkedSet 데이터를..
[백준] 10828번: 스택 문제링크 : https://www.acmicpc.net/problem/10828 문제풀이 Stack 자료구조를 이용해서 명령에 따라 그에 해당하는 작업을 처리하면 된다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; import java.util.StringTokenizer; public class p_10828 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..
[백준] 1012번: 유기농 배추 문제링크 : https://www.acmicpc.net/problem/1012 문제풀이 dfs, bfs로 풀 수 있는 문제이다. 문제 2667번과 동일한 방식으로 쉽게 풀 수 있다. dfs, bfs 두 방식으로 모두 풀어보았다. 소스코드 import java.io.*; import java.util.*; public class p_1012 { static int[][] arr = new int[50][50]; static int[] dx = {0, 0, -1, 1}; static int[] dy = {1, -1, 0, 0}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..
[백준] 2667번: 단지번호붙이기 문제링크 : https://www.acmicpc.net/problem/2667 문제풀이 dfs, bfs로 풀 수 있는 문제이다. 1) 1인 지점을 찾아 그 지점부터 상, 하, 좌, 우로 깊이 우선 탐색을 한다. 2) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 3) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다. 4) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 5) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다. 6) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다. 7) 더 이상 셀 집이 없다면 (1인 값이 없다면) co..

티스토리툴바