Java

    Java

    상속보다 컴포지션을 사용해야하는 이유

    [Java] 컴포지션(Composition) 컴포지션 : 기존 클래스가 새로운 클래스의 구성요소가 되는 것 상속(Inheritance)의 단점을 커버할 수 있는 컴포지션에 대해 알아보자 우선 상속(Inheritance)이란, 하위 클래스가 상위 클래스의 특성을 재정의 한 것을 말한다. 부모 클래스의 메서드를 오버라이딩하여 자식에 맞게 재사용하는 등, 상당히 많이 쓰이는 개념이면서 활용도도 높다. 하지만 장점만 존재하는 것은 아니다. 상속을 제대로 사용하지 않으면 유연성을 해칠 수 있다. 구현 상속(클래스→클래스)의 단점 1) 캡슐화를 위반 2) 유연하지 못한 설계 3) 다중상속 불가능 오류의 예시 다음은, HashSet에 요소를 몇 번 삽입했는지 count 변수로 체크하여 출력하는 예제다. public ..

    [CodeForce Beta Round #4] C. Registration system
    Algorithm/CodeForce

    [CodeForce Beta Round #4] C. Registration system

    문제 출처 : 링크 Problem - C - Codeforces codeforces.com 문제 자체는 어렵지 않다. 처음으로 등록되는 문자열은 "OK"로 출력하고, 만약 똑같은 문자열이 또 입력되면 숫자를 붙여서 출력해야한다. ex) Input 4 abacaba acaba abacaba acab output OK OK abacaba1 OK abacaba가 3번째에 또 들어오면서 abacaba1로 출력하는 모습을 볼 수 있다. 만약 한번더 들어오면 abacaba2를 출력하면 된다. 이 문제는 시간초과에 빠지기 쉬운 문제다. 왜냐하면 N의 값이 1~100000이다. 만약 브루트포스로 진행하면 N^2으로 100억번의 연산을 해야하는데 문제에 주어진 제한 시간 5초로는 불가능하다. 이 문제는 따라서 해시 테이..

    [자료구조/Java] 이진탐색트리 (Binary Search Tree)
    Algorithm/개념 정리

    [자료구조/Java] 이진탐색트리 (Binary Search Tree)

    [자료구조/Java] 이진탐색트리 (Binary Search Tree) - 각 노드의 자식이 2개 이하인 트리 - 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 노드 삽입 시간 균등 트리 : 노드 개수 N개일 때 O(logN) 편향 트리 : 노드 개수 N개일 때 O(N) 삽입,검색,삭제의 시간복잡도는 트리 높이에 비례함 삭제가 조금 까다로움 (3가지 case) 1. 자식이 없는 leaf 노드면? → 그냥 지우면 끝 2. 자식이 1개인 노드면? → 지워진 노드에 자식을 올리면 끝 3. 자식이 2개인 노드면? - 자식 노드 중에서 삭제할 노드보다 크면서 가장 작은 값 - 자식 노드 중에서 삭제할 노드보다 작으면서 가장 큰 값 편향된 트리(ex. 정렬된 상태인 값을 트리로 만들면 한쪽으로 뻗는다)에서..

    [Java] 컴파일 과정
    Java

    [Java] 컴파일 과정

    [Java] 컴파일 과정 자바를 많이 사용하기는 하지만, 막상 컴파일 과정을 설명하라하면 말문이 막힌다;; 면접에서도 가끔 나오는 주제이므로 정리해보자 HelloWorld.java 파일을 실행하기 위해 Run 버튼을 눌렀을 때 진행되는 과정은 아래와 같다. 1. HelloWorld.java가 javac.exe을 통해 컴파일 진행 2. HelloWorld.class가 생성됨 ( byte code ) → byte code는 반 기계어 상태로, 컴퓨터가 읽을 수 없다. 따라서 변환 과정이 필요함 3. HelloWorld.class를 java.exe로 실행 4. 클래스 로더를 통해 HelloWorld.class를 JVM으로 가져온다. (JVM은 현재 진행을 시도하는 OS에 맞게 변환시켜줌) 5. Byte Cod..

    [백준 14889] 스타트와 링크 (Java)
    Algorithm/백준(BOJ)

    [백준 14889] 스타트와 링크 (Java)

    [백준 14889] 스타트와 링크 (Java) 문제 출처 : 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 SW역량테스트 기출 문제다. 정답률도 매우 높고, 실제로 다른 기출문제에 비해 상당히 쉬운편이다. 짝수로 주어진 사람 수를 2팀으로 나누고, 문제에 주어진 능력치 값을 구해 두 팀의 최소차를 출력해주면 된다. 조합을 짤 수만 있다면 간단히 해결이 가능하다. 조합에서 팀이 나누어지는 상황마다 각 팀의 능력치 값을 구하고 절대값을 구한다. 이 절대값 중 가장 작은 값을 출력하면 끝! 1 2 3 4 5 6 7 8 9 1..

    [백준 17140] 이차원 배열과 연산 (Java)
    Algorithm/백준(BOJ)

    [백준 17140] 이차원 배열과 연산 (Java)

    [백준 17140] 이차원 배열과 연산 (Java) 문제 출처 : 링크 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 올해 삼성 상반기 오후 기출 문제다. 처음에 글만 보고 문제를 이해하기 힘들었는데 테스트케이스 밑에 자세한 설명이 나와있었다. 실제로 역량테스트를 볼 때는 너무너무 자세한 예시가 나와있으니 문제 이해를 못할 걱정은 크게 걱정하지 않아두 된다ㅎㅎ 이처럼 행과 열의 사이즈를 비교해 숫자의 수만큼 배열을 확장해나가는 방식이다. 행의 길이가 열보다 더 크거나 같으면 → 방향으로 열의 길이..

    [백준 17142] 연구소3 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 17142] 연구소3 (Java, BFS)

    [백준 17142] 연구소3 (Java, BFS) 문제 출처 : 링크 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 올해 상반기 삼성전자 역량테스트 문제다. 예전에 나온 삼성 기출 '연구소'에서 조건만 좀 더 추가된 문제 3가지 조건만 잘 기억하고..

    [백준 17143] 낚시왕 (Java)
    Algorithm/백준(BOJ)

    [백준 17143] 낚시왕 (Java)

    [백준 17143] 낚시왕 (Java) 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 www.acmicpc.net 올해 상반기 삼성전자 SW역량테스트 기출문제다. 시뮬레이션으로, 주어진 문제를 잘 읽으면서 코드로 옮겨야 한다. 큰 진행 방향은 아래와 같다. 낚시왕이 오른쪽으로 한..

    Algorithm/개념 정리

    [Java] HashSet을 ArrayList로 변환하기

    [Java] HashSet을 ArrayList로 변환하기 HashSet set = new HashSet(); for (int i = 0; i < T; i++) { set.add(br.readLine()); } ArrayList list = new ArrayList(set); 중복되는 값을 제외하고 저장하고 싶은 경우가 존재한다. 이때 HashSet을 통해 저장한 뒤 ArrayList로 변환해주면 값을 뽑을 때 매우 유용하다

    [백준 11559] Puyo Puyo (Java, DFS)
    Algorithm/백준(BOJ)

    [백준 11559] Puyo Puyo (Java, DFS)

    [백준 11559] Puyo Puyo (Java, DFS) 문제 출처 : 링크 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 약간의 DFS와 시뮬레이션이 합쳐진 문제다. 이런 문제 또한 약간의 제한조건만 달라지면서 많이 출제된다. 가장 중요한 건, 문제를 잘 이해하고 제한 조건을 하나라도 놓치지 않고 구현해야 한다는 점. 코드를 짜기 전에 먼저 종이에 확실히 조건을 모두 이해하며 로직을 간단하게 짜고 진행하자. 1. 맨 아래부터 블럭이 쌓여있기 때문에, 배열에서 아래부터 체크하며 빈칸이 아닌 것(알파벳인 곳)을 list에 담는다. 2. list에 담은 걸 하나씩 뽑아 해당 위치에서 DFS를 돌리..

    [백준 2206] 벽 부수고 이동하기 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 2206] 벽 부수고 이동하기 (Java, BFS)

    [백준 2206] 벽 부수고 이동하기 (Java, BFS) 문제 출처 : 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 지난번에 포스팅한 미로만들기와 유사한 방법으로 접근해야하는 문제다. 이 문제의 정답률은 훨씬 낮은데, N과 M의 ..

    [백준 17135] 캐슬 디펜스 (Java)
    Algorithm/백준(BOJ)

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

    [백준 17135] 캐슬 디펜스 (Java) 문제 출처 : 링크 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 최근에 나온 따끈따끈한 문제 이 문제 또한 주어진 제한 조건을 잘 확인하고, 구현으로 옮기면 된다. 진행 방식을 요약하면 다음과 같다. 1. 궁수 3명을 배치하고 사정거리 안에 있는 가장 가까운 적병을 사격 2. 사격 진행 후 남은 적병들 아래로 한칸 전진 3. 적병이 모두 죽거나, 궁수 칸으로 이동해서 사라질 때까지 1~2번 반복 - 주의할 점 1. 만약 궁수에게 가장 가까운 적병이 2개 이상이면, 가장 왼쪽..

    [백준 16236] 아기 상어 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 16236] 아기 상어 (Java, BFS)

    [백준 16236] 아기 상어 (Java, BFS) 문제 출처 : 링크 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 삼성 코딩테스트 기출 문제인 아기 상어 문제를 읽고 이해할 때 여러 제한 조건을 잘 고려해서 구현해야 한다. 하나라도 놓치면 디..

    [백준 2665] 미로만들기 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 2665] 미로만들기 (Java, BFS)

    [백준 2665] 미로만들기 (Java, BFS) 문제 출처 : 링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 시작부터 끝이 정해져 있고, 시작 방부터 끝 방까지 방의 색을 최소로 바꿔서 이동시켜야 하는 문제다. BFS라는거는 바로 알 수 있지만, 단순하게 생각하면 까다로울 수 있는 문제다. 평소처럼 boolean으로 visit 배열을 만들어 체크하는 것이 아닌, int형으로 각 위치마다 방을 바꾼 횟수를 저장시키며 나아가는 방법을 익힌 문제..! 시작할 때 visit 배열을 모두 무한대 값으로 초기화 해두고..

    카테고리 없음

    [SWEA 1767] 프로세서 연결하기(Java)

    [SWEA 1767] 프로세서 연결하기(Java) 문제 출처 : 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 2차원 배열 안에 설치되어 있는 코어에 전선을 연결시키는 문제다 벽에 붙어있는 코어는 전선을 연결할 수 없고, 나머지 코어를 최대한 많이 활용하면서 최소한의 전선 길이를 출력해야하는 문제다 최소한의 전선 길이라는 말로 BFS로 접근하면 힘들어지고, 코어를 많이 가져가기 위해 DFS 탐색 접근이 편하다 우선 코어에 해당하는 1의 값이 들어오면, 벽에 붙어있지 않은 코어들을 list에 저장했다 그리고 dfs를 통해 해당 코어의 index와 코어의 수 coreCnt, 마지막으로 전선의 길이를 ..

    Algorithm/SWEA

    [SWEA 2117] 홈 방범 서비스 (Java)

    [SWEA 2117] 홈 방범 서비스 (Java) 문제 출처 : 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소프트웨어 모의 테스트 문제다. 시뮬레이션 문제로, 마름모를 구현할 수만 있으면 잘 풀 수 있다. (잘 생각이 안나서 더럽게 구현했음ㅜㅜ) 이익이 0 이상일 때를 체크해서 가장 많은 집의 수를 출력하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858..

    Algorithm/SWEA

    [SWEA 4050] 재관이의 대량할인 (Java)

    [SWEA 4050] 재관이의 대량할인 (Java) 문제 : 링크 입력 받은 수를 sort하면 작은 수부터 큰 수로 정렬된다. 뒤에서부터 3개씩 묶어서 할인을 받으면 가장 큰 할인 금액을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Solution_4050_재관이의대량할인 { static int N; static int[] arr; publ..

    Algorithm/SWEA

    [SWEA 4301] 콩 많이 심기(Java)

    [SWEA 4301] 콩 많이 심기(Java) 문제 출처 : 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 규칙을 찾고 미리 배열에 채운다. 그리고 입력 받은 N과 M을 통해서 2차원배열의 [0][0] ~ [N-1][M-1] 혹은 [0][0] ~ [M-1][N-1] 중에 큰 수를 저장하여 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899..

    [백준 15686] 치킨 배달 (Java)
    Algorithm/백준(BOJ)

    [백준 15686] 치킨 배달 (Java)

    [백준 15686] 치킨 배달 (Java) 출처 : 링크 삼성 코테 기출문제다. 0은 빈 공간, 1은 집, 2는 치킨집이다. 집과 치킨집의 행렬 값을 저장해두고, 치킨집의 수도 같이 저장한다. 치킨집의 총 개수가 n개면, 1~n개까지 조합을 통해 채택시키고 가장 작은 도서의 치킨 거리를 구하면 된다. 이 문제는 따로 dfs, bfs를 적용하지 않고도 풀 수 있다. 최소 거리만 잘 구해보자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394..

    [백준 14502] 연구소 (Java)
    Algorithm/백준(BOJ)

    [백준 14502] 연구소 (Java)

    [백준 14502] 연구소 (Java) 출처 : 링크 삼성 코테 기출 문제다. 0은 이동가능한 값, 1은 벽, 2는 바이러스다. 벽으로 막혀있지 않고, 바이러스와 인접해있는 0인 곳들은 모두 감염이 된다. 처음 시작 전에, 값이 0인 map에서 3곳에 벽을 세울 수 있다. 따라서 map에 저장된 0의 수를 저장하고, 조합을 통해 벽을 모두 세운 뒤 dfs를 진행했다. 모두 진행한 뒤 가장 많은 안전 영역 수를 출력해주면 되는 문제다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081..

    [백준 16234] 인구 이동 (Java)
    Algorithm/백준(BOJ)

    [백준 16234] 인구 이동 (Java)

    [백준 16234] 인구 이동 (Java) 출처 : 링크 2018년 하반기 삼성 코테 기출이다. DFS와 BFS 모두 사용이 가능하고, 인구 이동이 가능할 때까지 계속 진행해서 횟수를 출력해주면 된다. 이동이 가능한 배열마다 같은 숫자를 저장하도록 2차원 배열을 하나 더 만들었다. (copymap) DFS를 통해 조건에 맞는 이동가능 배열끼리 묶어주고, 해당 map의 값을 모두 더해 평균을 내서 저장시켰다. 평균을 구하는 반복문을 따로 만들어서 사용하면 시간초과로 풀 수 없으므로 먼저 리스트를 생성해 DFS를 호출하는 반복문 안에서 평균 값 계산을 같이 해야 시간을 줄일 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383..

    [백준 2839] 설탕 배달 (Java)
    Algorithm/백준(BOJ)

    [백준 2839] 설탕 배달 (Java)

    [백준 2839] 설탕 배달 (Java) 출처 : 링크 구현 문제다. 5kg 봉지와 3kg 봉지로 최소 봉지 수를 구해야 한다. 가장 최소가 될 수 있는 수는 5kg로 모두 가능할 때이므로 먼저 체크했다. 그 다음 미리 3kg로 나눠지는 봉지 수도 체크하고 값을 저장시켜 놓았다. 이제 N 값에서 5씩 감소시키면서 3으로 나누어지는지 while문을 통해 진행하면 끝 N이 5보다 작아질 때까지 돌면서 처음값과 갱신된 최소값이 답이고, 변화가 없었으면 -1 출력한다 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.InputStr..

    [백준 2470] 두 용액 (Java)
    Algorithm/백준(BOJ)

    [백준 2470] 두 용액 (Java)

    [백준 2470] 두 용액 (Java) 출처 : 링크 쉽게 생각하고 접근하다 큰 코 다쳤다;; 조합 → 시간초과이중for문 → 시간초과 N의 수를 잘 체크하고 문제를 푸는 습관을 갖자.. ArrayList에 값을 담고, Sort한다 처음 값과 끝 값의 합을 미리 저장해두고, while문을 통해 시작과 끝의 인덱스 값을 증감해가며 최소값을 찾아간다 문제 풀 때는 용액의 값이 크길래 long으로 선언해서 풀었는데 10억이라 int형으로 풀어도 상관 없을 것 같다 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.io.BufferedReader;import jav..

    [백준 2004] 조합 0의 개수 (Java)
    Algorithm/백준(BOJ)

    [백준 2004] 조합 0의 개수 (Java)

    [백준 2004] 조합 0의 개수 (Java) 출처 : 링크 그냥 조합으로 풀면 시간 안에 해결이 불가능하다. 끝자리 0의 개수만 구하면 되므로 다 계산할 필요가 없다. 일단 조합의 식은 아래와 같다. nCm = n! / (n-m)! * m! 결국 이 값에서 2의 배수와 5의 배수의 갯수를 찾으면 된다. 2의 배수 1개와 5의 배수 1개가 만나면 10이 되어 끝자리 0 하나가 생기기 때문 주의) 25부터는 5가 두개, 4부터는 2가 2개이므로 반복문을 잘 돌려야 함 5와 2 모두 n!에서 개수를 구해주고, 나눠지는 (n-m)!이랑 m!에서 나오는 개수를 빼주면 된다. 그리고 5와 2 중에 개수 최소값을 출력하면 끝이다 123456789101112131415161718192021222324252627282..

    [백준 2503] 숫자 야구 (Java)
    Algorithm/백준(BOJ)

    [백준 2503] 숫자 야구 (Java)

    [백준 2503] 숫자 야구 (Java) 출처 : 링크 완탐 문제다. 처음에 규칙을 어떻게 가져와야할까 고민했지만, 그냥 다 돌면서 해당하는 규칙과 비교하고 성립하는 수만 고르면 된다. 123~987까지 for문으로 돌아도 되지만, 중복되는 수를 없애기위해 순열을 만들어 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105import java.io.BufferedReader;impo..

    [백준 1261] 알고스팟 (Java, 다익스트라)
    Algorithm/백준(BOJ)

    [백준 1261] 알고스팟 (Java, 다익스트라)

    [백준 1261] 알고스팟 문제 출처 : 링크 경로를 이동하는 걸 생각하면 DFS나 BFS를 활용해야 될 것 같다. 하지만 기존의 문제와는 다르게, '가중치'가 존재한다. 1인 값을 가지고 있는 곳을 지날 때는 벽이 있는 것이므로 부수고 지나갈 수 밖에 없다. 따라서 그냥 움직이는 것이 아닌, 1인 곳을 지나갈 때마다 값을 변경시켜나가야 하는 문제다. 우선 미로탐색처럼 BFS와 유사한 방식으로 나아가지만, 이 가중치 값을 최소화 시키기 위해 그냥 큐가 아닌 우선순위 큐를 사용해서 저장한다. (우선순위를 위해 comperable 활용) 123456789101112131415161718class Spot implements Comparable{ int y; int x; int cost; public Spot..

    [알고리즘] 서로소 집합(Disjoint-sets) - Java
    Algorithm/개념 정리

    [알고리즘] 서로소 집합(Disjoint-sets) - Java

    서로소 집합(Disjoint-sets) [알고리즘] 서로소 집합(Disjoint-sets) 서로소 or 상호배타 집합서로 중복 포함된 원소가 없는 집합(= 즉, 교집합이 없는 것) 대표자(representative)집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분 상호배타 집합 표현 방법연결 리스트트리 상호배타 집합 연산Make-Set(x), Find-Set(x), Union(x,y) 트리를 이용해 상호배타 집합 표현된 모습부모는 해당 노드의 Find-Set 값 연산Make_Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산Find_Set(x) : x를 포함하는 집합을 찾는 연산(해당 노드의 부모 정보 갱신)Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산 M..

    [알고리즘] 트라이(Trie) - Java
    Algorithm/개념 정리

    [알고리즘] 트라이(Trie) - Java

    [알고리즘] 트라이(Trie) 트라이(TRIE) 트라이(TRIE)retrieval 문자열의 집합을 표현하는 트리를 말한다모든 문자열은 다른 문자열의 접두어가 아니라고 가정 부분 문자열 검사ba가 abac의 부분 문자열인가?두개 접두사의 최장 공통 접두어 찾기abac와 ac의 최장 공통 접두어는?사전적 순서로 정렬된 k번째 접미사 찾기abac의 3번째 접미사는? : abac, ac, bac, c (정답 : bac) 각 간선은 하나의 문자에 대응한다같은 노드에 나오는 간선들은 같은 레벨을 갖지 않음각 문자열은 단말 노드에 대응한다 Compressed Trie노드들과 간선들을 부분 문자열로 압축(= 접미어 트리(Suffix Tree)) 문자열 S = {xabxac}에 대한 접미어 트리 발생하는 문제점 해결책하..

    [알고리즘] 다익스트라(Dijkstra) - Java
    Algorithm/개념 정리

    [알고리즘] 다익스트라(Dijkstra) - Java

    [알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 경로를 찾을 때 가중치가 있으면 사용하자 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.Arrays; /** * Dijkstra : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 * * Greedy 방식, 음이 아닌 가중치일 경우만 사용가능 * 음의 가중치가 있는 경우 => 벨만포드 알고리즘을 통해서 구해야 한다 * 시간복잡도 O[n^2] */ public cl..

    [디자인 패턴] 어댑터(Adapter) 패턴
    Java/디자인 패턴(Design Pattern)

    [디자인 패턴] 어댑터(Adapter) 패턴

    어댑터 패턴용도 : 클래스를 바로 사용할 수 없는 경우가 있음 (다른 곳에서 개발했다거나, 수정할 수 없을 때) 중간에서 변환 역할을 해주는 클래스가 필요 → 어댑터 패턴사용 방법 : 상속호환되지 않은 인터페이스를 사용하는 클라이언트 그대로 활용 가능향후 인터페이스가 바뀌더라도, 변경 내역은 어댑터에 캡슐화 되므로 클라이언트 바뀔 필요X 클래스 다이어그램 아이폰의 이어폰을 생각해보자가장 흔한 이어폰 잭을 아이폰에 사용하려면, 잭 자체가 맞지 않는다.따라서 우리는 어댑터를 따로 구매해서 연결해야 이런 이어폰들을 사용할 수 있다 이처럼 어댑터는 필요로 하는 인터페이스로 바꿔주는 역할을 한다 이처럼 업체에서 제공한 클래스가 기존 시스템에 맞지 않으면?기존 시스템을 수정할 것이 아니라, 어댑터를 활용해 유연하게..

티스토리툴바