하루 2시간
본문 바로가기
728x90
[프로그래머스] 당구 연습 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/169198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 크게 케이스가 3가지로 나뉘고 큰 케이스 안에 작은 케이스로 나눠서 풀었습니다. startY 와 목표 y가 같은 경우 아래 3가지 중 최소 값 가벼운 x 벽과 원 쿠션 시작점 x가 목표점 x값보다 작은 경우 시작점 x가 목표점 x값보다 큰 경우 두 공이 같은 선상에 있을 경우 시작지점에서 벽 사이에 목표지점이 있으면 쿠션이 안되므로 예외처리 startX 와 목표 X가 같은 경우 아래 3가지.. 2023. 3. 17.
[프로그래머스] 특이한 정렬 자바(Java) 프로그래머스 - 특이한 정렬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 정렬 기준을 바꿔기 n을 기준으로 가까운 수 -> 각각 숫자에서 n을 뺀 절댓값 절댓갑 기준(값의 차이) 내림차순 정렬 후 오름차순 정렬 - 문제에서 거리가 같은 경우 큰수가 앞으로 와야하는 조건 때문 상세 설명은 코드 주석 참고 코드 import java.util.*; class Solution { public int[] solution(int[] numlist, int n) { // 정수 리스트를 저장할 어레이리스트 생성 List numList = new ArrayList.. 2023. 3. 7.
[백준] 20165 인내의 도미노 장인 호석 자바(Java) https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 알고리즘은 다음과 같이 작동합니다. 각 도미노의 양쪽에 일정한 수의 점이 있는 도미노 게임을 시뮬레이트하는 Java 프로그램입니다. 직사각형의 도미노 보드를 가져옵니다. 여기서 각 셀은 각 면에 특정 수의 점이 있는 도미노를 나타냅니다. 프로그램은 또한 일련의 동작을 취하며 각 동작은 공격과 방어로 구성됩니다. attack은 시작 셀, 방향 및 크기로 표시됩니다. 지정된 셀에서 시작.. 2023. 3. 4.
[백준] 16924 십자가 찾기 자바(Java) https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net 문제 이 알고리즘의 목적은 주어진 문자 격자에서 모든 별 모양의 패턴을 찾고 각 패턴의 크기와 위치를 출력하는 것이다. 입력은 표준 입력 스트림에서 읽히고 첫 번째 줄에 두 개의 정수 N과 M으로 구성되며, 각각 문자 그리드를 나타내는 길이 M의 N 줄로 구성된다. 문자 '*'는 별 모양의 패턴의 일부를 나타냅니다. 출력은 표준 출력 스트림으로 인쇄되며, 발견된 별 모양 패턴의 수를 나타.. 2023. 2. 28.
[알고리즘] 다양한 이분 탐색 문제 풀이 2차 배열 이분 탐색 row 값과 cols값을 구하기만 한다면 문제는 import java.io.IOException; ​ public class Main { ​ private static boolean solution(int[][] arr, int target) { if (arr == null || arr.length == 0) { return false; } ​ int left = 0; int rows = arr.length; int cols = arr[0].length; int right = rows * cols - 1; ​ while (left days) { minWeight = carryingWeight + 1; } //현재 적재량이 넉넉하기 때문에 적재량 감소 else { maxWeight =.. 2023. 2. 24.
[백준] 10816 숫자 카드 2 자바(Java) https://www.acmicpc.net/problem/10816 중복된 값을 가지고 있는 배열에서 입력된 값이 몇 개 있는지 출력하는 문제 HashMap을 사용해서 풀 수 있지만 카테고리가 이분 탐색이라 이분탐색으로 문제 접근 처음 입력받은 배열을 정렬 입력 값 이분 탐색 동일 값 처음 인덱스 마지막 인덱스 구하기 마지막 인덱스 - 처음 인덱스 동일 값 처음 인덱스 private static int lower(int[] arr, int key) { int si = 0; int li = arr.length; while (si < li) { int mid = (si + li) / 2; // 입력 값과 같거나 큰 값 if (key 2023. 2. 22.
이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 규칙 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 중복된 키를 허용하지 않음 각가의 서브 트리도 이진 탐색 트리를 유지 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 이진 트리에 비해 탐색이 빠르다. (균형 유지 필요) 균형 상태 : O(logN) 불균형 상태 : O(N) 탐색 찾고자 하는 데이터를 루트 노드부터 비교 시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다. 찾는 데이터가 없으면 null반환 삽입 루트 노드부터 비교 시작 삽입할 키가 현재 노드의 키보다 작으면 왼쪽, 크면 오른쪽 노드로 이동. L.. 2023. 2. 15.
해시 테이블(Hash Table) 해시 테이블(Hash Table) 키, 값을 대응시켜 저장하는 데이터 구조로 키를 통해 해당 데이터에 빠르게 접근 가능 해싱 키를 특정 계산식에 넣어 나온 결고를 사용하여 값에 접근하는 과정 해시 테이블 구조 키 : 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값 : 해시 테이블의 인덱스 해시 충돌 해시 함수를 통한 해시 값이 동일한 경우 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다. 해시 충돌 해결 방법 개방 주소법(Open Address) 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장 hash와 value가 1:1 관계 유지 (해시 키는 하나의 데이터만 가지.. 2023. 2. 10.
[백준] 11004 K번째 수 자바(Java) https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 11004번 문제에서 2가지 정렬 방식으로 문제를 접근했습니다. Arrays.sort(), Collections.sort() Java8에서는 Arrays.sort()는 시간 초과가 나오고 Collections.sort()는 문제를 맞혔습니다. Java11에서는 Arrays.sort()도 맞았다고 나옵니다. 시간 복잡도에서 최악의 경우 Arrays.sort()는 O(n^2) 값이 나와 시간 초과가 나옵니다. Java11에서는 왜 맞았다고 나오는지 이유.. 2023. 1. 29.
팩토리 패턴(factory pattern) 팩토리 패턴(factory pattern) 팩토리 패턴을 사용하는 이유 다형성은 높이고 의존성 낮추기 위해서이다. 구상 클래스, 추상 클래스, 인터페이스 사용 이유 new 연산자를 사용해 인스턴스를 구현하면 나중에 코드를 수정해야 할 가능성이 커지고, 유연성이 떨어집니다. 그래서 상위 형식에 맞춰서 프로그래밍합니다. (인터페이스에 맞춰서 프로그래밍한다.) 실제 실행 시에 쓰이는 객체가 코드에 공정되지 않도록 상위 형식(supertype)에 맞춰 프로그래밍해서 다형성을 활용해야 한다는 점 변수를 선언할 때 보통 추상 클래스나 인터페이스 같은 상위 형식으로 선언해야 한다. 객체를 변수에 대입할 때 상위 형식을 구체적으로 구현한 형식이라면 어떤 객체든 넣을 수 있기 때문이다. 그러면 "변수를 선언하는 클래스에.. 2023. 1. 13.
싱글톤 패턴 (Singleton) 싱글톤 패턴 (Singleton) 클래스의 인스턴스가 하나임을 보장하고 접근할 수 있는 전역적인 접근점을 제공하는 패턴 장점 하나의 인스턴스를 만들어 놓고 해당 인스턴스를 다른 모듈들이 공유하며 사용하기 때문에 인스턴스를 생성하는데 드는 비용이 줄어든다. 자원을 많이 잡아먹는 인스턴스가 있다면 유용하다. 단점 의존성이 높다. -> 의존성 주입(DI, Dependency Injection)을 통해 모듈 간의 결합을 조금 더 느슨하게 만들어 해결할 수 있다. TDD -> 단위 테스트는 서로 독립적이어야 하며 어떤 순서로든 실행할 수 있어야 한다. 싱글톤 패턴은 테스트마다 독립적인 인스턴스를 만들기 어렵다. 싱글톤이 깨지는 경우 멀티스레딩 -> 동기화 필요 클래스 로더가 2개 이상일 때 -> 클래스 로더를 직.. 2023. 1. 12.
디자인 패턴 소프트웨어 디자인에서 공통적으로 발생하는 문제에 대해 재사용 가능한 해결책이다. 특정한 상황에 맞게 사용될 수 있는 구조적 문제들을 해결하는데 쓰이는 서술이나 템플릿. 디자인 패턴은 외우기보다는 어떠한 패턴이 있는지 알고 수많은 디자인 패턴에서 다양한 코딩 노하우를 습득하는것이 중요하다고 생각합니다. "이 코드에는 무조건 이 패턴을 적용시킬거야!" 이것이 아니라 여러가지 패턴이 자연스럽게 내 코드에 녹아드는것이 좋다고 생각합니다. 출처 : https://coding-factory.tistory.com/708 즉, 모든 곳에 패턴을 적용하려고 하면 안 된다. 디자인 패턴의 종류 생성(Creational) 패턴 객체 생성에 관련된 패턴 객체의 생성과 조합을 캡슐화해 특정 객체가 생성되거나 변경되어도 프로그램.. 2023. 1. 11.
[백준] 2579 계단 오르기 자바(Java) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2156 포도주 시식 문제와 비슷한 문제다. 다른 점은 "마지막 도착 계단은 반드시 밟아야 한다."이다. 계단 오르기의 경우의 수는 2가지이다. 마지막 도착 계단 밟은 상태에서 n -1 위치의 계단을 밟지 않는 상태 vs n -1 위치의 계단을 밟은 상태 위 그림과 같이 2가지 형태로 나올 수 있다. 앞에 n - 2, n - 3 위치의 체크표시가 빨간 이유는 다음과 같다. n -1 위치의 계단을 밟지 않.. 2023. 1. 6.
[백준] 2156 포도주 시식 자바(Java) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 가장 많이 마실 수 있는 상황의 값을 저장한 dp 테이블 int[] dp = new int[n + 1]; 와인의 용량이 저장된 테이블 int[] values = new int[n + 1]; 와인을 마실 수 있는 경우의 수 아래 그림 3가지 중 가장 큰 값이 dp[i] 에 저장이 된다. 현재 i위치에 있는 와인을 마시는 경우 그림에서 위에 2줄 연속으로 3잔을 모두 고를 수 없다는 것을 고려한다. 1.. 2023. 1. 6.
[백준] 9465 스티커 자바(Java) https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제에서 이동하는 방법은 현재 위치에서 대각선으로만 갈 수 있다. 하지만 아래 그림과 같이 그 다음칸의 대각선으로도 이동이 가능하다. 1번 값과, 2번 값중 큰 값을 선택하면 된다. 그럼 점화식나온다. dp[0][n] = Max(dp[1][n - 1], dp[1][n - 2]) + dp[0][n] dp[1][n] = Max(dp[0][n - 1], dp[0][n - 2]) + dp[1].. 2023. 1. 6.
[백준] 2193 이친수 자바(Java) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 점화식 풀이 1. 현재 위치에서 값이 0이면 이전 값은 1과 0이 올 수 있다. dp[digit][0] = dp[digit - 1][1] + dp[digit - 1][0]; 현재 위치에서 값이 1이면 이전 값은 0만 올 수 있다. dp[digit][1] = dp[digit - 1][0]; 풀이 2. d[i] = d[i-2]+d[i-1] 이런 식으로 푸는 방식이 있는데, 직접 나열하면서 .. 2023. 1. 5.
[백준] 11057 오르막 수 자바(Java) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net dp테이블 자릿수, 자릿값을 가지고 있어야 한다. -> dp[자릿수][자릿값] 접근 static int L(int n, int i) { if (dp[n][i] != 0) { return dp[n][i]; } if (i == 0) { dp[n][i] = L(n - 1, i); } else { for (int j = i; j >= 0; j--) { dp[n][i] .. 2023. 1. 4.
[백준] 10844 쉬운 계단 수 자바(Java) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1의 자릿수일 때 1 ~ 9까지 가능 -> 9가지 2의 자릿수일 때 1의 자릿수 1 ~ 9, 2의 자릿수 1의 자릿수의 값이 1, 9가 아니면 1의 자릿값 + 1과 1의 자릿값 - 1 2가지가 가능하게 된다. dp테이블 자릿수, 자릿값을 가지고 있어야 한다. -> dp[자릿수][자릿값] 초기화 dp[1][1~9] = 1; -> 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없다 점화식 탑다운 자바 코드 package main.iyk2h; import java.io.BufferedReader.. 2023. 1. 2.
[백준] 9095 1, 2, 3 더하기 자바(Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 : n을 1, 2, 3의 합으로 나타내는 방법의 수 접근. countSum( 1 ) = 1 countSum( 2 ) = 2 countSum( 3 ) = 4 countSum( 4 ) = 7 countSum( 5 ) = 13 ... n = 5까지 단순하게 숫자를 세본 결과 규칙을 찾을 수 있었다. countSum( n ) = countSum( n - 1) + countSum( n - 2) + countSum( n - 3) 증명. n = 4일 때 맨 마지막 더하기 값에는 3가지 값이 들어갈 수 .. 2023. 1. 1.
[백준] 11727 2xn 타일링 2 자바(Java) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726 문제를 이해하고 풀었다면 쉽게 풀리는 문제이다. 아래 블로그 참고 https://iyk2h.tistory.com/306 기존 문제에서 2 * 2 정사각형 타일이 추가되었다. 위 그림과 같이 직사각형을 채워나갈 수 있게 된다. n의 값이 3, 4일 때부터 규칙이 보이기 시작한다. n = 3 일 때 색으로 구별해 두었는데, 빨간색은 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 .. 2023. 1. 1.
[백준] 11726 2xn 타일링 자바(Java) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제를 풀어보고 오면 좋겠습니다. 문제는 2*n 크기의 직사각형을 2 * 1 타일로 채우는 방법의 수를 구하는 문제이다. 위 그림과 같이 직사각형을 채워나갈 수 있게 된다. n의 값이 3, 4일 때부터 규칙이 보이기 시작한다. n = 3 일 때 두 개의 박스로 크게 묶어두었다. 묶은 이유는 왼쪽 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 박스는 n = 1 일 때 직사각형을 .. 2023. 1. 1.
[백준] 1463 1로 만들기 자바(Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근 방법 단순하게 접근하면 3으로 나누고, 2로 나누고, 나눌 수 없으면 -1을 하면서 값을 작게 만들면 되지 않나 생각할 수 있다. 단순 접근 : 10 -> 5 -> 4-> 2-> 1 : 4번 정답 : 10 -> 9 -> 3-> 1 : 3번 쉽게 단순 접근은 틀린 걸 알 수 있다. 이유는 10을 1로 만드는 경우에 2가지 경우의 수가 생기게 된다. 1. 9를 1로 만드는 최솟값 + 1 2. 5를 1로 만드는 최솟값 + 1 두 값 중 더 작은 값이 최솟값이 된다. 그럼 문제에서 나온 3가지 경우를 보면 최솟값.. 2022. 12. 30.
[Java] 익명 클래스(anonymous class) 이 글은 https://youtu.be/CXuA31XcBZ0 를 통해 개념 정리 후 복습용으로 정리한 글입니다. 문제시 바로 삭제하겠습니다. 익명 클래스(anonymous class) 이름이 없는 일회용 클래스. 정의와 생성을 동시에 new 조상클래스이름() { // 멤버 선언 } ​ new 구현인터페이스이름() { // 멤버 선언 } class anonymous { Object iv = new Object(){ void methd(){} }; static Object cv = new Object(){ void methd(){} }; void myMethod() { Object lv = new Object(){ void methd(){} }; } } 사용하는 이유 프로그램 내에서 단발성으로 한 번만 사용.. 2022. 12. 27.
[Java] 내부 클래스(inner class) 이 글은 https://youtu.be/CXuA31XcBZ0 를 통해 개념 정리 후 복습용으로 정리한 글입니다. 문제시 바로 삭제하겠습니다. 내부 클래스(inner class) 클래스 안의 클래스 class A { // 외부 클래스 ... classB { // 내부 클래스 ... // 객체 생성 없이도 A의 멤버 접근 가능 } } 내부 클래스의 장점 내부 클래스에서 외부 클래스의 멤버들을 쉽게 접근할 수 있다. 코드의 복잡성을 줄일 수 있다.(캡슐화) 내부 클래스의 종류와 특징 내부 클래스의 종류와 유효범위(scope)는 변수와 동일 내부클래스 종류 특징 인스턴스 클래스 iv (instance class) 외부클래스의 멤버변수 선언위치에 선언하며, 외부클래스의 인스턴스처럼 다뤄진다. 주로 외부클래스의 인.. 2022. 12. 26.
[Java] 추상 클래스(abstract class), 추상 메서드(abstract method) 이 글은 https://youtu.be/CXuA31XcBZ0 를 통해 개념 정리 후 복습용으로 정리한 글입니다. 문제시 바로 삭제하겠습니다. 추상 클래스(abstract class) 미완성 설계도. 미완성 메서드를 갖고 있는 클래스 abstract class Player { // 추상 클래스(미완성 클래스) abstract void play(int pos); // 추상메서드(몸통{}이 없는 미완성 메서드) abstract void stop(); // 추상메서드 } abstract - 추상 클래스라고 표현, 상속해서 구현하라는 의미 다른 클래스 작성에 도움을 주기 위한 것. 인스턴스 생성 불가 Player p = new Player(); // 에러. 추상 클래스는 인스턴스 생성 불가 상속을 통해 추상 메서.. 2022. 12. 24.
[Java] super, package, import, modifier, polymorphism 이 글은 https://youtu.be/CXuA31XcBZ0 를 통해 개념 정리 후 복습용으로 정리한 글입니다. 문제시 바로 삭제하겠습니다. super 객체 자신을 가리키는 참조변수. 인스턴스 메서드(생성자) 내에만 존재 -> static 메서드 내에 사용 불가 조상의 멤버와 자신의 멤버를 구별할 때 사용 Class ex{ public static void main(String args[]) { Child c = new Child(); c.method(30); } } class Parent { int x = 10; } // super.x class Child extend Parent { int x = 20; // this.x void method(int x) { System.out.println("x =.. 2022. 12. 23.
[OOP] 객체 지향 개념 이 글은 https://youtu.be/CXuA31XcBZ0 를 통해 개념 정리 후 복습용으로 정리한 글입니다. 문제시 바로 삭제하겠습니다. 객체 지향 개념 클래스와 객체 클래스 정의 클래스란 객체를 정의해 놓은 것 용도 클래스는 객체를 생성하는 데 사용 객체 정의 실제로 존재하는 것, 사물 또는 개념 용도 객체가 가지고 있는 기능과 속성에 따라 다름 클래스 객체 제품 설계도 제품 TV 설계도 TV 객체의 구성요소 - 속성과 기능 객체 = 속성(변수) + 기능(메서드) TV 속성(변수) 크기, 길이, 높이, 색상, 볼륨, 채널 등 기능(메서드) 켜기, 끄기, 볼륨 높이기, 볼륨 낮추기, 채널 변경하기 등 //TV 설계도 Class tv { String color: //색깔 boolean power; //.. 2022. 12. 22.
728x90

티스토리툴바