티스토리

carsumin devlog 🍀

검색하기

블로그 홈

carsumin devlog 🍀

marginata.tistory.com/m

기록하기

구독자: 4

방명록 방문하기

주요 글 목록

[Silver III/JAVA] 16956 늑대와 양 https://www.acmicpc.net/problem/16956 조건크기 RxC인 목장양은 이동하지 않음, 늑대는 인접한 방향으로 이동 가능울타리를 설치해서 늑대가 양이 있는 칸으로 못가도록 해야 함울타리 개수 제한 없음 풀이 과정양 주변으로1. 늑대-양 인접한가?2. 빈곳 체크해서 울타리 설치 여부 결정 전체 코드import java.io.*;import java.util.*;public class Main{ static int R, C; static char[][] map; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; public static void main(String[] args) throws .. 공감수 1 댓글수 0 2024. 12. 25.
[Silver I/JAVA] 3187 양치기 꿍 https://www.acmicpc.net/problem/3187 조건양 > 늑대 -> 양만 남음 , 늑대 >= 양 -> 늑대만 남음울타리 바깥에는 양 늑대 없음빈공간 있음 필요한 것방문 여부 체크방향 이동 배열 dx, dy울타리, 빈공간, 양늑대 입력 받을 map 배열입력을 공백없이 받음 (charAt 사용) 풀이 과정방문한 적 없고, 울타리가 아니면 BFS 탐색상하좌우 방향 이동하면서 BFS 탐색을 하고 늑대와 양의 개수를 각각 카운트마지막에 최종 늑대와 양의 개수를 비교좌표 형태로 큐에 한번에 담을 수 있음 전체 코드import java.io.*;import java.util.*;public class Main{ static int R,C; //가로C,세로R static char[][].. 공감수 0 댓글수 0 2024. 12. 19.
[Silver I/JAVA] 2667 단지번호붙이기 https://www.acmicpc.net/problem/2667 풀이이전에 풀었던 영역구하기와 유사한 문제다. (https://marginata.tistory.com/173)영역구하기가 색칠되지 않은 영역의 넓이를 구한것이라면 반대로 단지번호붙이기는 집이 있는곳의 넓이를 구하면 된다.주의할 점은 0001010 이런식으로 공백없이 입력을 받기 때문에 charAt()을 이용해서 한자리씩 char형으로 추출한 뒤에 정수형으로 변환해줘야 한다. 전체 코드import java.io.*;import java.util.*;public class Main{ static int[][] map; //지도 static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,.. 공감수 1 댓글수 1 2024. 12. 13.
[Silver I/JAVA] 2583 영역 구하기 https://www.acmicpc.net/problem/2583 조건M*N 모눈종이에 K개의 직사각형을 그림K개의 직사각형 내부를 제외한 나머지 부분을 구하는 것분리된 영역 개수, 각 영역의 넓이를 출력(오름차순)필요한 것네 방향으로 움직이면서 탐색하기 위한 dx, dy 배열영역 넓이 결과를 저장할 ArrayList (넓이가 얼마나 나올지 모르기 때문에 가변적인 ArrayList 사용)영역 넓이를 저장할 cnt풀이여기서 M이 높이, N이 너비이다.x,y좌표값은 문제에서 설명하는 것과 다르더라도 그대로 2차원 배열로 나타내도 넓이는 같다.x, y 범위만큼 영역을 1로 채워줌빈 영역을 DFS 탐색 전체 코드import java.io.*;import java.util.*;public class Main{.. 공감수 0 댓글수 0 2024. 12. 12.
[Silver II/JAVA] 2210 숫자판 점프 https://www.acmicpc.net/problem/2210 조건숫자판의 크기는 5*5인접한 네 방향으로 다섯번 이동 (위, 아래, 오른쪽, 왼쪽)한 번 거쳤던 칸을 다시 거쳐도 됨 = 방문 체크 필요없음서로 다른 여섯 자리 수들의 개수 구하기필요한 것숫자판(grid) 2차원 배열방향 이동을 위한 배열 dx, dy중복을 제거할 수 있는 Set풀이grid 2차원 배열에 값 입력받기각각의 정점(숫자판의 숫자)에서 DFS 탐색하기인접한 네 방향으로 이동int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};/*아래 : dx=1 dy=0 -> 행 번호 1증가 x+1위 : dx=-1 dy=0 -> 행 번호 1감소 x-1오른쪽 : dx=0 dy=1 -> 열 번호 1증가 y+.. 공감수 0 댓글수 0 2024. 12. 12.
[Silver IV/JAVA] 1388 바닥장식 https://www.acmicpc.net/problem/1388 '-' 이런 문자가 나오면 -> 이 방향으로 탐색, '|' 이런 문자가 나오면 ↓ 이 방향으로 탐색한다고 생각하면 된다.여기서 어떤 경우에 인접리스트를 사용하고 어떤 경우에 2차원 배열을 사용하는지가 궁금해졌다.* 인접 리스트 사용하는 경우- 정점이 많고, 각 정점에 연결된 간선의 수가 적을 때- 정점 중심의 탐색- 입력이 정점-간선 목록으로 주어질 때* 2차원 배열(그리드, 인접 행렬)을 사용하는 경우- 정점 개수에 비해 간선 개수가 많을 때 ( 예 : N x N 행렬에서 모든 정점이 연결된 완전 그래프 )- 그래프가 2D 격자 형태일 때 ( 예 : 미로찾기, 섬의 개수, 경로 탐색 등 )- 정점 간 연결 여부 체크할 때 ( 예 : 경.. 공감수 0 댓글수 2 2024. 12. 10.
[Silver II/JAVA] 1260 DFS와 BFS https://www.acmicpc.net/problem/1260 인접리스트를 이용해서 정점의 방문여부를 체크한다. (입력예시)1 2 입력 -> graph = [ [ ], [2], [1], [ ] , [ ] ]1 3 입력 -> graph = [ [ ], [2, 3], [1], [1] , [ ] ]1 4 입력 - > graph = [ [ ], [2, 3, 4], [1], [1] , [1] ]2 4 입력 - > graph = [ [ ], [2, 3, 4], [1, 4], [1] , [1, 2] ]3 4 입력 -> graph = [ [ ], [2, 3, 4], [1, 4], [1, 4] , [1, 2, 3] ]앞에서 풀었던 알고리즘 수업 1,2와 유사함. 풀이import java.io.*;import j.. 공감수 2 댓글수 1 2024. 12. 10.
[Silver II/JAVA] 24479, 24480 알고리즘 수업 - 깊이 우선 탐색 1, 2 https://www.acmicpc.net/problem/24479 문제의 조건정점의 수 : N간선의 수 : M시작 정점 : R인접 정점은 오름차순 방문 (24479번 문제)인접 정점은 내림차순 방문 (24480번 문제) 필요한 것ArrayList (이차원 Array는 N*N이라 시간초과 발생함) -> 실제 연결된 간선만 저장하는 ArrayList를 사용하는 것이 메모리 낭비를 줄일 수 있음 - 이차원 배열의 시간 복잡도 : O(N)- 인접 리스트의 시간 복잡도 : O(E), 여기서 E는 간선의 개수. 인접리스트는 간선의 개수와 시간복잡도가 비례한다. 입력받기BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[].. 공감수 0 댓글수 0 2024. 12. 1.
[Silver III/JAVA] 10451 순열 사이클 https://www.acmicpc.net/problem/10451 DFS, BFS 두 가지로 풀 수 있는 문제시간복잡도는 O(N)으로 DFS, BFS 동일하다. DFS (깊이우선탐색) 풀이 문제를 보면 순열을 1부터 세기 때문에 배열의 크기 설정에 주의한다.입력받은 순열을 배열에 넣을 때도 ArrayIndexOutOfBoundsException가 발생하지 않도록 주의한다.순열 배열에 인덱스 1부터 값을 넣기 때문에 그 값에 해당하는 str 배열에서는 index-1을 해줘야한다.노드 방문을 기록할 boolean 타입의 visited 배열을 만들어서 사이클이 중복으로 체크되지 않도록 탐색한다.[ 탐색 과정 ] * n = 1dfs(1)visited[1] = truenextNode = 3 dfs(3) vis.. 공감수 0 댓글수 0 2024. 11. 23.
[Silver V/JAVA] 13241 최소공배수 https://www.acmicpc.net/problem/13241 유클리드 호제법을 이용하여 최소공배수를 구한다.최소공배수 = 두 수의 곱 / 최대공약수 풀이 import java.io.*;import java.util.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); long a = Long.parseLong(str[0]); long.. 공감수 0 댓글수 0 2024. 11. 22.
[Algorithm] 유클리드 호제법 (Euclidean Algorithm) 유클리드 호제법 (Euclidean Algorithm) 최대공약수, 최소공배수 (GCD, LCM)최대공약수 구한 뒤 두 수의 곱을 최대공약수로 나누면 최소공배수 구할 수 있음두 자연수의 곱 = 최대공약수 * 최소공배수∴ 최소공배수 = 두 자연수의 곱 / 최대공약수 만약 A, B라는 두 수가 있다면 최소공배수(LCM)는 아래와 같다LCM = A*B / GCD 공감수 0 댓글수 0 2024. 11. 22.
[Silver V/JAVA] 10815 숫자카드 https://www.acmicpc.net/problem/10815 이진탐색을 사용하지 않고 배열을 일일이 비교하면 시간초과가 뜬다.이진탐색(Binary Search)를 사용해서 풀어야 하는 문제 (https://marginata.tistory.com/150)풀이 1은 System.out.print() 를 이용하여 일일이 출력을 했고, 풀이 2는 StringBuilder를 사용하여 출력을 했다. 성능면에서 StringBuilder를 사용하는 것이 훨씬 더 빠르다. 풀이 1 import java.io.*;import java.util.*;public class Main{ static int[] arr; public static void main(String[] args) throws IOExc.. 공감수 0 댓글수 0 2024. 11. 18.
[Algorithm] 이진탐색 (Binary Search) 이진탐색 (Binary Search) 중앙값 (mid) 지정해서 비교하는 탐색이진탐색을 하려면 정렬이 된 상태에서 수행해야 함 이진탐색의 시간복잡도 O(logn)의 시간복잡도를 가지고 있다.선형탐색과 비교했을 때 데이터 수가 증가함에따라 기하급수적으로 증가하지 않음 (그래프 참고) 공감수 0 댓글수 0 2024. 11. 18.
[Algorithm] 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS) BFS (Breadth-First Search) 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드 광범위하게 탐색첫번째 floor부터 시작해서 해당 floor의 모든 노드 방문할 때까지 수평 이동한 번 거친 노드 순서 저장한 후 다시 꺼내는 FIFO 주로 Queue로 구현 DFS (Depth-First Search) 시작 노드와 직접 연관된 하위 노드의 끝까지 모두 탐색한 후 다음 하위 노드 탐색경로 하나의 모든 floor 탐색한 뒤 그 다음 경로의 모든 floor 탐색하는 순서주로 재귀호출이나 Stack 명시하는 방법으로 구현 공감수 0 댓글수 0 2024. 11. 13.
[Bronze II/JAVA] 84753226 상수 https://www.acmicpc.net/problem/2908 문자열을 뒤집는 reverse() 를 알면 좀 더 쉽게 풀 수 있는 문제다른 사람 풀이를 보니 한번에 문자열을 입력받아 공백기준으로 분리해서 처리했는데 이게 훨씬 좋은 코드같다.나는 변수를 여러번 입력받고 각각 뒤집는 과정을 거쳐서 코드가 지저분해졌다.split으로 분리해서 배열로 처리하면 최댓값도 Max함수로 간단히 구할 수 있다. 내 풀이import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.. 공감수 0 댓글수 0 2024. 11. 2.
[Bronze II/JAVA] 10809 알파벳 찾기 https://www.acmicpc.net/problem/10809 문자열이 처음 나타난 위치를 계산하는 게 헷갈림알파벳 (A-Z) 이 총 26개인 것을 알아야 풀 수 있는 문제알파벳 개수만큼 배열을 만들고, 입력값의 원소와 비교'처음 등장하는 위치' 라는 출력 조건이 있기 때문에, 모든 알파벳 배열을 -1로 초기화한다.예를 들어 c가 'a'라면 c-'a'는 0이므로 arr[0]은 'a'의 위치를 가리킨다.마찬가지로 c가 'b'라면 c-'a'는 1이므로 arr[1]은 'b'의 위치를 가리킨다.즉 , arr[c-'a']는 문자 c가 처음 등장한 위치를 가리킨다. 풀이import java.io.*;class Main{ public static void main(String[] args) throws.. 공감수 0 댓글수 0 2024. 10. 29.
[Bronze II/JAVA] 10811 바구니 뒤집기 https://www.acmicpc.net/problem/10811 배열 인덱스 주의할 것 (첫번째 바구니는 1, 두번째 바구니는 2... 배열은 0부터 시작)왼쪽으로부터 i번째부터 j번째 바구니까지 순서를 역순으로 만든다 -> i 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] arr = new int[N]; for(int i=0; i 공감수 0 댓글수 0 2024. 10. 25.
[Bronze II/JAVA] 3052 나머지 https://www.acmicpc.net/problem/3052 배열과 HashSet으로 풀이할 수 있음배열로 입력받아서 이중for문을 돌려서 값이 같은 경우 cnt를 증가시키고, cnt가 0이면 값이 다르다고 볼 수 있기 때문에 diff를 카운트해서 서로 다른 나머지를 체크했다문제는 입력값이 10개뿐이였지만 입력개수가 많아지는 경우 효율성이 떨어지기 때문에 다른 풀이 방법을 찾아봐야겠다 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[] arr = new int[10]; int diff = 0;.. 공감수 1 댓글수 0 2024. 10. 23.
[Bronze II/JAVA] 10813 공 바꾸기 https://www.acmicpc.net/problem/10813 앞서 풀었던 공넣기 문제를 응용한 문제라 어렵지 않게 풀 수 있다swap 알고리즘을 이용한 문제배열의 인덱스 주의해서 풀이 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //가지고 있는 바구니 개수 int N = sc.nextInt(); int[] arr = new int[N]; //바꿀 횟수 int M = sc.nextInt(); for(int i=0; i 공감수 1 댓글수 0 2024. 10. 21.
[Bronze III/JAVA] 10810 공 넣기 https://www.acmicpc.net/problem/10810 여러번 읽고 문제를 이해했다해결방법 자체는 쉬운데 문제를 이해하는 데 시간이 걸림이중 for문을 사용할 때 index 범위를 주의해야함예를 들어서 문제에서 말하는 2번 바구니부터 5번 바구니는 배열로 따지면 1번부터 4번일 것따라서 반복문을 실행할 때 -1을 해야함 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //바구니를 N개 가지고 있음 int n = sc.nextInt(); int[] arr = new int[n]; .. 공감수 1 댓글수 2 2024. 10. 20.
[Bronze V/JAVA] 10951 A+B-4 (EOF) https://www.acmicpc.net/problem/10951 * EOF는 End of File의 약자로, 더 이상 읽을 수 있는 데이터가 존재하지 않는 것을 의미한다.* 다양한 풀이 방법은 이 분의 블로그를 참고했다. (https://st-lab.tistory.com/40) Scanner 이용한 풀이 hasNextInt(), hasNext() 둘 중 아무거나 사용해도 됨hasNextInt() : 입력값이 정수일경우 true 반환, 정수 아닐경우 예외 발생하고 false 리턴 및 반복문 종료import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in.. 공감수 0 댓글수 0 2024. 10. 16.
[Bronze IV/JAVA] 11720 숫자의 합 https://www.acmicpc.net/problem/11720 1. 공백없이 입력받는다 -> 문자열로 받는다는 얘기2. 문자열로 받아서 charAt으로 각 자리 값을 반환3. 정수형으로 변환해서 합을 구함 1. Scanner 이용한 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String str = sc.next(); int sum = 0; for(int i=0; i charAt() 은 문자의 아스키코드값을 리턴하기 때문에 -.. 공감수 0 댓글수 0 2024. 10. 15.
[Bronze IV/JAVA] 2480 주사위 세개 https://www.acmicpc.net/problem/2480 1. 습관적으로 Scanner만 사용했는데 이번에는 BufferedReader를 이용해서 풀어봄2. 코드가 더 길어진다... 고려해야할 게 많다 (import, 예외처리, 타입변환...)3. Math 함수안에 Math 함수를 또 사용해서 세가지 수의 max 값을 찾았다4. BufferedWriter는 문자열을 리턴하기 때문에 출력시에 형변환이 필요5. close, flush도 잊지 말고 해주자 내 풀이import java.io.*;import java.util.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader .. 공감수 0 댓글수 0 2024. 10. 10.
[Bronze IV/JAVA] 15552 빠른 A+B https://www.acmicpc.net/problem/15552 1. Scanner와 BufferedReader의 성능 차이를 느낄 수 있는 문제2. BufferedReader은 문자열로 입력받기 때문에 정수형으로 변환하는 과정이 필요3. BufferedReader, BufferedWriter는 예외처리를 해줘야 한다4. 마지막에 버퍼를 비우고 스트림을 닫는 코드를 써준다 내 풀이import java.io.*;class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Bu.. 공감수 1 댓글수 0 2024. 10. 9.
[LV2/JAVA] 피보나치 수 https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 재귀함수(recursive)로 풀면 입력값이 클 경우 메모리차지를 많이 하고 시간복잡도가 증가한다.2. 중복연산을 없애는 dynamic programming을 해야한다.3. 첫번째와 두번째 경우는 미리 값을 초기화하고 시작한다.4. 오버플로우를 방지하기 위해서 각 연산에 1234567의 나머지 연산을 해야한다. 내 풀이class Solution { public int solution(i.. 공감수 1 댓글수 2 2024. 10. 6.
[LV2/JAVA] 최솟값 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 최솟값을 만드는 것이 목적이기 때문에 두 배열 요소의 곱의 합이 가장 작게 나올만한 경우를 생각해봐야한다.2. 배열 A를 오름차순 정렬, 배열 B를 내림차순 정렬해서 각각 곱하면 가장 작은 값을 만들 수 있다.3. 처음에는 배열 B를 reverseOrder() 하려고 했지만 no suitable method found for sort 에러가 발생함.4. Integer 배열이면 Arrays.s.. 공감수 0 댓글수 0 2024. 10. 6.
[LV2/JAVA] 올바른 괄호 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Stack 컬렉션 Java의 Stack 컬렉션을 사용하기 위해서 java.util.Stack 클래스를 import 한다.Stack 사용법// Stack에 요소 삽입Stack stack = new Stack();stack.push(1);stack.push(2);stack.push(3); 풀이Stack을 이용해서 푸는 문제괄호가 (), (()), ()() 이런식으로 짝이 맞으면 true, 아니면 fal.. 공감수 1 댓글수 2 2024. 10. 3.
[LV2/JAVA] 최댓값과 최솟값 https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문자열을 문자형 배열에 담는다.String[] sArr = s.split(" "); 2. 최대, 최소를 비교하기 위한 초기값을 설정한다. 여기서 max, min의 값은 배열을 순회하면서 비교할 것이기 때문에 아무거나 상관없다.3. 향상된 For문으로 문자형 배열을 순회한다.4. 문자형 answer을 리턴한다.class Solution { public String solution(String.. 공감수 1 댓글수 1 2024. 10. 2.
[LV1/JAVA] 3진법 뒤집기 https://school.programmers.co.kr/learn/courses/30/lessons/68935 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 진법에 관한 문제이다. 방법을 알면 어렵지 않게 풀 수 있다. 1. 3진법은 3으로 나눈 나머지로 이루어진 수2. n을 3진법 상에서 뒤집어야함3. 3으로 나눈 나머지를 문자열로 붙여서 저장하면 뒤집은 결과값을 얻을 수 있음4. 리턴할 .. 공감수 1 댓글수 0 2024. 9. 30.
[LV1/JAVA] 행렬의 덧셈 https://school.programmers.co.kr/learn/courses/30/lessons/12950 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 예전에 학교에서 C언어 배울 때 이후로 오랜만에 보는 2차원 배열... 실무에서는 거의 쓸 일이 없었다.2. 헷갈려서 배열 요소에 대한 그림을 그리며 풀었다. 나의 풀이class Solution { public int[][] solution(int[][] arr1, int[][] arr2) { int[][] answer = new int[arr1.length][arr1[0]... 공감수 0 댓글수 0 2024. 9. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.