티스토리

개발일지

검색하기

블로그 홈

개발일지

qazwsxedc9codingpractice.tistory.com/m

qazwsxedc9 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

Union-Find > 1043번 Union-Find: 대표적인 그래프 알고리즘 '합집합 찾기' 라는 의미를 가진 알고리즘으로 서로소 집합 알고리즘이라고도 부른다 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 1043번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class baekjoon1043 { static int n; static int m; static int[] parent; static boolean[] tru.. 공감수 0 댓글수 0 2022. 9. 15.
다이나믹 프로그래밍 > 12865번, 9084번, 2293번 12865번 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 담은 이차원 배열 // knapsack 알고리즘 > 무게와 가치가 함께 주어짐 // 이차원 배열 사용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class baekjoon12865 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer s.. 공감수 0 댓글수 0 2022. 9. 6.
플로이드 워셜 > 13168번 13168번 map을 사용하여 한국에 있는 도시들에 번호를 매겨준다 m개의 도시를 차례대로 여행하므로 해당 도시들을 배열에 담은 뒤 도시들의 간 최소 비용 경로의 합을 구한다 ex) 서울 > 전주 > 순천 > 여수 > 서울을 여행할 경우 [서울 > 전주의 최소 비용 경로] + [전주 > 순천의 최소 비용 경로] + [순천 > 여수의 최소 비용 경로] + [여수 > 서울의 최소 비용 경로]이 여행에서 최소 비용 경로의 합이 된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.. 공감수 0 댓글수 0 2022. 9. 5.
최소 신장 트리 > 13418번 13418번 // 오르막길 = 0, 내리막길 = 1 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon13418 { static int n; static int m; static boolean[] visited; static ArrayList[] lists; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeniz.. 공감수 0 댓글수 0 2022. 9. 1.
플로이드 워셜 > 13424번 13424번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class baekjoon13424 { static int n; static int m; static int [][] map; static int INF = 4950001; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int test = Integer.parseIn.. 공감수 0 댓글수 0 2022. 8. 31.
최소 신장 트리 > 14621번, 14950번, 21924번 14621번 // 모든 대학교 간 이동이 가능해야 함 // 최단 경로 // 크루스칼 알고리즘 사용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon14621 { static int n; // 학교 수 (1번 대학교, 2번 대학교...) static int m; // 연결하는 도로 수 static Map map = new HashMap(); static ArrayList [] lists; // 인접리스트 static boolean [] visited; // 방문 여부 체크 static int result; static.. 공감수 0 댓글수 0 2022. 8. 29.
분할 정복 > 1629번, 10830번 1629번 long 타입을 사용해도 정수의 오버플로우가 발생하므로 모듈러 합동 공식을 사용해야 한다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class baekjoon1629 { static int A; static int B; static int C; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringToken.. 공감수 0 댓글수 0 2022. 8. 19.
투 포인터 > 22862번 22862번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class baekjoon22862_ { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = Integer.parseInt(st.nextToken(.. 공감수 0 댓글수 0 2022. 8. 17.
보석 쇼핑 코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 투 포인터를 사용하는 문제이다 import java.util.*; public class programmers_jewel { public static void main(String[] args) { String [] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"}; System.out.println(solution(gems)); gems .. 공감수 0 댓글수 0 2022. 8. 16.
투 포인터 > 17609번 17609번 2개의 포인터가 각각 배열의 시작점과 끝점에 위치하여 반대로 이동하는 방법을 사용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class baekjoon17609 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for(int .. 공감수 0 댓글수 0 2022. 8. 15.
DFS와 BFS > 1926번, 2468번 1926번 // bfs & 인접 행렬 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class baekjoon1926 { static int n; // 도화지 세로 크기 static int m; // 도화지 가로 크기 static int [][] picture; // 그림 색칠 여부 이차원 배열로 표현 static boolean [][] visited; // 방문 여부 체크 static int [] dx = {-1,1,0.. 공감수 0 댓글수 0 2022. 8. 14.
다익스트라 > 4485번 / 그리디 > 1339번 4485번 이전 다익스트라 문제들은 인접 리스트를 사용하여 풀었지만 해당 문제는 인접 행렬을 사용하였다 // 인접 행렬과 최단 경로 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; public class baekjoon4485 { static int n; // 동굴의 크기 static int[][] graph; // 동굴 내 도둑 루피 정보를 담은 이차원 배열 static boolean[][] visited; // 방문 여부 확인 static int[] dx = {-1, 1, 0, 0};.. 공감수 0 댓글수 0 2022. 8. 12.
이진 탐색 > 1939번, 3079번 1939번 bfs와 이진 탐색을 함께 사용하는 문제이다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon1939 { static int n; // 섬의 개수 (정점) static int m; // 다리의 개수 (간선) static boolean[] visited; // 방문 여부 체크 static ArrayList[] lists; // 인접리스트 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead.. 공감수 0 댓글수 0 2022. 8. 10.
다익스트라 > 10282번 10282번 2번(a) 컴퓨터가 1번(b) 컴퓨터에 의존 = 1번(b) 컴퓨터가 감염되면 5초 후 2번(a) 컴퓨터도 감염 3번(a) 컴퓨터가 2번(b) 컴퓨터에 의존 = 2번(b) 컴퓨터가 감염되면 5초 후 3번(a) 컴퓨터도 감염 > 2번 컴퓨터가 해킹 당해 감염된다면 3번 컴퓨터도 감염된다 (1번 컴퓨터는 해당 없음) // 컴퓨터의 개수 = 정점의 개수 // 의존성의 개수 = 간선의 개수 // 의존성으로 감염되는데 걸리는 시간 = 가중치 // 단방향 : 컴퓨터 a가 b를 의존한다 > b가 감염되면 a도 감염된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u.. 공감수 0 댓글수 0 2022. 8. 9.
DFS와 BFS > 1327번, 11724번 1327번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon1327 { static int n; // 순열의 개수 static int k; // 뒤집어야할 문자 개수 static char [] arr; // 순열에 들어가는 수 배열 static char [] copy; // 순열에 들어가는 수 배열을 복사한 배열 static String arr_str; // 순열에 들어가는 수 배열을 오름차순 정렬 후 문자열로 만든 것 static String copy_str; // 순열에 들어가는 수 배열을 문자열로 만든 것 pu.. 공감수 0 댓글수 0 2022. 8. 9.
최소 신장 트리 > 1922번, 1647번, 6497번 최소 신장 트리 신장 트리는 그래프의 모든 정점을 연결하는 사이클이 없는 트리이다 최소 신장 트리는 신장 트리 중 정점들을 연결하는 간선들의 합이 최소가 되는 트리이다 최소 신장 트리를 구하는 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 있다 프림 알고리즘 시작 정점을 기준으로 가장 작은 가중치를 가진 간선을 선택하여 트리를 확장 크루스칼 알고리즘 간선의 가중치를 기준으로 오름차순 정렬 후 가중치가 가장 작은 간선부터 선택하여 선택한 간선의 두 정점이 연결되어 있지 않으면 연결 1922번 프림 알고리즘은 다익스트라 알고리즘과 유사하다 // 모든 컴퓨터를 연결하는데 필요한 최소 비용 // n = 컴퓨터의 수 = 정점의 개수 // m = 연결할 수 있는 선의 수 = 간선의 개수 // 프림 알고리즘 사용 .. 공감수 0 댓글수 0 2022. 8. 6.
다익스트라 > 1504번 / DFS와 BFS > 14502번 1504번 INF의 값을 INTEGER.MAX_VALUE로 설정할 경우 더하는 과정에서 오버플로우가 발생하므로 주의해야 한다 // 정점의 개수 = n // 간선의 개수 = e // 1번 정점에서 n번 정점으로 최단 거리로 이동 (시작점 1) // 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 // 주어진 두 정점(v1, v2)을 반드시 거치면서 최단 경로로 이동 // (1번 > v1) + (v1 > v2) + (v2 > n번) // (1번 > v2) + (v2 > v1) + (v1 > n번) // 두 가지 경우를 모두 고려한 후 그 중 작은 값이 정답 // 경로가 없을 때에는 -1을 출력 import java.io.BufferedReader; import java.io.IOExcept.. 공감수 0 댓글수 0 2022. 8. 5.
DFS와 BFS > 7576번, 1389번 7576번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않음 // 보관 후 하루 지나면 익은 토마토의 상하좌우에 있는 익지 않은 토마토가 익는다 (bfs 사용) // 익은 토마토의 개수가 여러개인 경우도 있으므로 동시 출발 > 큐 사용 public class baekjoon7576 { // 이동할 4가지 방향 정의 (상하 / 좌우가 겹치지 않게) sta.. 공감수 0 댓글수 0 2022. 8. 3.
DFS와 BFS > 10026번, 1012번 10026번 // 적록색약인 경우 초록색과 빨간색을 구분하지 못함 = 하나의 구역으로 본다 // 적록색약인 경우 dfs, 적록색약이 아닌 경우 dfs 나눠서 생각? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class baekjoon10026 { static String [][] grid; // 색칠한 그림을 이차원 배열로 나타낸 것 static boolean [][] visited; // 방문 여부 static int n; // 이동할 4가지 방향 정의 (상하 / 좌우가 겹치지 않게) static int[] dx = {-1, 1, 0, 0}; static int[] d.. 공감수 0 댓글수 0 2022. 8. 2.
다익스트라 > 1916번, 1238번 다익스트라 알고리즘 : 최단 경로 탐색 알고리즘 최단 거리는 여러 개의 최단 거리로 이루어져 있다 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 ex) 1번 노드부터 다른 모든 노드로 가는 최단 시간 경로 1916번 // 도시의 개수 = 노드 개수 (n) // 버스의 개수 = 간선 개수 (m) // 비용 = 가중치 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.String.. 공감수 1 댓글수 0 2022. 8. 1.
10250번, 2910번(해시 맵), 4949번(스택) 10250번 나머지와 몫을 활용하는 문제로 나머지가 0이 될 때만 주의해주면 된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int test = Integer.parseInt(br.readLine()); StringBuilder sb = new .. 공감수 0 댓글수 0 2022. 7. 25.
2470번(투 포인터), 5568번(조합) 2470번 투 포인터 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 형태이다 1. 2개의 포인터의 시작점이 배열의 시작점인 경우 > 포인터 2개가 같은 방향으로 진행된다 2. 2개의 포인터가 각각 배열의 시작점과 끝점에 위치한 경우 > 포인터 2개가 양 끝에서 시작하여 반대로 진행된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { public static void main(String[] args) throws I.. 공감수 0 댓글수 0 2022. 7. 25.
18115번(덱), 2798번, 1929번(소수) 18115번 수열 A를 뒤집어서 풀이하면 된다 1번 > 2번 > 3번 > 3번 > 2번 순서로 기술을 실행 1. deque의 맨 앞에 1을 집어 넣음 2. deque의 맨 앞에 있는 1을 잠시 버리고 앞에 2를 집어 넣은 후 다시 맨 앞에 1을 넣는다 3. deque의 맨 뒤에 숫자 3을 넣는다 4. deque의 맨 뒤에 숫자 4를 넣는다 5. deque의 맨 앞에 있는 1을 잠시 버리고 앞에 5를 집어 넣은 후 다시 맨 앞에 1을 넣는다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Solution { public static.. 공감수 0 댓글수 0 2022. 7. 22.
10799번(스택), 10816번(이진 탐색), 2805번(이진 탐색) 10799번 스택을 응용한 문제이다 괄호들의 묶음을 문자열 한 줄로 입력 받은 후 이를 하나씩 쪼개 문자열 배열로 만든다 for문을 돌며 배열에서 "("이 나오면 스택에 push ")"이 나올 경우 스택에서 pop 만약 ")"의 앞이 "("였다면 여는 괄호와 닫는 괄호의 인접한 쌍이므로 레이저이다 만약 ")"의 앞이 ")"였다면 쇠막대기가 끝났다는 의미이다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { .. 공감수 0 댓글수 0 2022. 7. 20.
10866번(덱), 9012번(스택), 1764번 10866번 덱의 기본 개념을 묻는 문제이다 여기서 주의해야할 점은 어제와 풀었던 문제와 마찬가지로 명령어를 push_back X와 push_front X인 문자열로 받았을 때 이를 공백을 기준으로 문자열과 숫자로 분리시켜야 한다는 것이다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; public class Practice { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe.. 공감수 0 댓글수 0 2022. 7. 19.
10818번(스택), 18866번(큐), 1654번(이진 탐색) 10818번 스택의 개념에 대해 확인하는 문제이다 주어지는 명령어를 문자열로 받은 후 이것이 제시된 명령어와 동일한지 비교하여 동일한 경우 명령을 수행하도록 한다 가장 중요한 점은 push 명령어는 push + 숫자로 구성되어 있으므로 공백을 기준으로 나눠서 생각해줘야 한다. 현재 숫자는 문자열이기 때문에 정수형으로 변환이 필요하다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Practice { public static void main(String[] args) throws IOException { BufferedRe.. 공감수 0 댓글수 0 2022. 7. 18.
1966번(큐), 1010번(조합), 1789번 1966번 큐는 먼저 들어간 자료가 가장 먼저 나오는 구조 Enque: 큐 맨 뒤에 데이터가 추가되는 것 Deque: 큐 맨 앞쪽의 데이터를 삭제하는 것 큐는 연결 리스트를 활용하여 생성 poll() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거, 큐 비어있으면 false 반환 remove() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거, 큐가 비어 있으면 예외 발생 peek() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환, 없으면 null 반환 offer() - 해당 큐의 맨 뒤에 전달된 요소를 삽입, 만약 삽입에 실패하면 false 반환 add() - 해당 큐의 맨 뒤에 전달된 요소를 삽입, 만약 삽입에 성공하면 true를 .. 공감수 0 댓글수 0 2022. 7. 15.
10815번 (이진 탐색), 1874번 (스택), 11650번 (정렬) 10815번 인텔리제이에서는 잘 돌아갔는데 시간 초과 떠서 틀렸다ㅎ... 찾아보니까 이진 탐색 사용해야 한다고 함 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Practice { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int n = Integer.parseIn.. 공감수 0 댓글수 0 2022. 7. 13.
2751번, 2231번, 1110번, 1181번, 1436번, 10814번 2751번 반복문을 통해 num개의 입력값들을 list로 넣어준다 Collections.sort() 메서드를 사용하여 해당 list를 오름차순으로 정렬 처음엔 배열을 사용해서 Arrays.sort() 사용 했는데 시간 초과 떴다 import java.util.*; public class Practice { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int num = sc.nextInt(); List list = new ArrayList(); for(int i = 0; i 공감수 0 댓글수 0 2022. 7. 12.
14954번, 15649번, 15650번, 15651번, 15625번 14954번 기초 수학 연습 문제 4번과 유사한 문제이다 (자세한 풀이는 그쪽에 적어둠) import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Practice { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int number = sc.nextInt(); System.out.println(isHappy(number) ? "HAPPY" : "UNHAPPY"); } public static boolean isHappy (int number) { Set set = new HashSet(); while(set.add(.. 공감수 0 댓글수 0 2022. 7. 11.

문의안내

티스토리
로그인
고객센터

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