Java - 알고리즘52

• DFS 문제풀이 : 중복순열 다루기, 거스름돈 계산하기 이번에는 중복순열을 Java 코드로 만들어보고, 관련 문제를 풀어볼 것입니다. 사실 저는 고딩때 순열, 조합 이런 것들을 정말 정말 싫어했었는데... 고등학교 졸업 후 약 10년 만에 이런 문제들을 다시 봤지만, 사람은 변하지 않나 봅니다. 여전히 싫네요ㅠ 1. 중복순열 다루기 ※ 설명 1부터 N 까지 적힌 구슬에서 중복을 허락하여 M번 뽑아서 나열하라 ※ 입력 첫 번째 줄에 자연수 N(3 for 문 시작 pm[0] = 1; && dfs(index+1) == dfs(1) // 2. dfs(1) 이 시작됨 => for 문 시작, i=1 일 때 pm[1] = 1 && dfs(index+1) == dfs(2) // 3. dfs(2) 는 곧 index == 2 임을 의미하고, m = 2 때문에 index == .. Java - 알고리즘 2022. 6. 19.

• DFS 문제풀이 : 바둑이 승차, 잔돈 계산하기 오늘은 DFS 관련 문제를 풀고 공부해봤습니다. 코드에 대한 설명은 주석에 달아두었습니다. 1. 바둑이 승차 ※ 설명 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. ※ 입력 첫 번째 줄에 자연수 C(1 Java - 알고리즘 2022. 6. 19.

• 

  그래프에서 최단거리 구하기 BFS 문제 제시 보통 이런 문제에서 간선의 수는 도로의 갯수, 도로 1개당 이동시간 몇 분 이런식으로 나온다 1번 도시에서 각 도시까지 가는 최소 이동 시간을 구하시오 1번 도시에서 3번, 4번 도시까지 최소 이동 시간은 1분 첫째 줄에는 도시의 수 N(1≤N 해당 queue 는 LinkedList 를 담음 // Linklist 인 이유는 도시와 도시가 연결 linked 되어 있기 때문!! Queue queue = new LinkedList(); // v 번째를 지났다면 ch 배열의 v 번째 인덱스에 1 이 들어감 ch[v] = 1; // v 번째에서 v 번째 까지 거리는 당연 0 -> 자기 자신으로의 거리 dis[v] = 0; // queue 에 v 를 넣기 queue.add(v); // queue 가 비어.. Java - 알고리즘 2022. 6. 12.

• 알고리즘 - 버블 정렬, 삽입 정렬 1. 버블 정렬 두 인접한 원소를 검사하며 정렬하는 방법!! 시간 복잡도가 O(n^2) 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 버블 정렬은 1회 차에 배열의 갯수 - 1 회만큼 정렬한다. 따라서 바깥쪽 for 문은 총 몇 회 비교를 하는지 안쪽 for문은 인접한 숫자를 비교하기 위해 사용된다 /* 버블 정렬 시작!! 버블 정렬은 num 이란 배열안에 num[0] ~ num[n] 까지의 값이 있을 때 num[0] 과 num[1] 을 비교 후 정렬, num[1] 과 num[2]를 비교 후 정렬 ~~~ 최종적으로 num[n-1] 과 num[n] 을 비교 후 정렬하며 작은 수부터 정렬하는 방법이다. 기억해야할 점은 큰 수부터, 배열에서는 num[n] 부터 값이 확정된다는 점이다. */ fo.. Java - 알고리즘 2022. 2. 25.

• 

  그래프와 인접 행렬 & 인접 리스트 오늘은 그래프와 인접 행렬 & 인접 리스트에 대해서 공부해보았다. 알고리즘 문제를 풀 때 항상 생각하는건데...어려운 문제은 항상 경로 찾기 문제가 포함된다ㅠ.ㅠ 이번에는 경로찾기 문제중에서도 트리 형태가 아닌 그래프에서 경로 찾기 문제에 대해서 공부하도록 하겠다. 1. 그래프 : 그래프는 방향 그래프와 무방향 그래프, 가중치 방향 그래프 총 3가지! 무방향 그래프 : 방향이 따로 없는 그래프 2차원 배열로 표현하자면, 행에서 열로 가는 방향 && 열에서 행으로 가는 방향 모두 확인해야 함. graph[a][b] = 1; 로 표현된다. 즉, 아래처럼 표현 할 수 있다. graph[1][2] = 1; // 1번과 연결된 2번 노드 graph[2][1] = 1; graph[1][4] = 1; // 1번과 연.. Java - 알고리즘 2021. 12. 1.

• 

  자바 알고리즘 - 큐(Queue), BFS(너비 우선 탐색), 최단 횟수 찾기 이번에는 BFS 깊이우선탐색에 대한 글입니다. 역시나 DFS 와 마찬가지로 어마무시하게 중요합니다ㅠㅠ - What is Queue? 큐(Queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First in First Out) 구조로 저장하는 형식이다. 스택(Stack)이 먼저 집어 넣은 데이터가 가장 나중에 나오는 자료 구조라면, 큐(Queue)는 먼저 들어간 데이터가 가장 먼저 나오는 구조이다. 아주 간단히 이야기하면 평소 우리가 놀이동산에서 놀이기구를 탈 때를 떠올리면 될 것 같다. 놀이동산에서는 먼저 줄을 선 사람이 먼저 놀이기구를 타게 된다. Queue 는 딱 이런 구조로 먼저 들어온 데이터가 가장 먼저 출력, 처리되는 형식이다. 1. BFS 는 넓.. Java - 알고리즘 2021. 11. 11.

• 

  자바 알고리즘 - 이진트리 순회, DFS 오늘은 DFS 깊이 우선 탐색에 대해서 공부하였다. 새로운 것 두 가지를 알았는데 - DFS 는 생각보다도 훨~~씬 어렵고 심오하다는 것과 - 바로 이 DFS 로 조합과 관련된 문제를 풀 수 있다는 것 이다. 사실 지금까지는 조합과 관련된 문제를 풀어보려고 몇 번 뒤적뒤적 했던 적이 있다. 그럴때마다 문제도 이해가 안되었지만, 대체 이걸 코드로 어떻게 짜는거지? 라고 생각될 때가 많았다. 그렇다, 문제가 어려웠던 것은 그렇다치고, 조합에 관한 부분을 대체 어떻게 짜는거지? 하면서 뭔가 풀이 방법조차 떠오르지 않았던 것은 바로 이 DFS , BFS 에 대해서 공부하지 않았기 때문이었다. 앞으로 적을 DFS 와 BFS 의 개념은 엄청 엄청!!! 아주아주 매우매우 중요하다. 이걸 쓰는 코딩 테스트 문제들은 물.. Java - 알고리즘 2021. 11. 11.

• 

  자바 알고리즘 - 스택(stack), 팩토리얼 ! , 피보나치 함수 오늘부터는 단순히 알고리즘 문제만 푸는게 아니라 알고리즘 강의 듣고 정리한 부분들에 대해서도 글을 쓸까 한다. 그래도 글을 쓰고 정리해두어야 뭔가 기억에 남는 것 같기도 하고...뭣보다 점점 가면서 이거 공부안하면 문제를 못 풀겠어서 결국 알고리즘 강의를 듣게 되었다ㅠ.ㅠ 1. What is stack? 스택(stack)에 대해서는 젠가를 예로 들면 딱 적절할 것 같다. 스택은 젠가가 아직 젠가 통에 담아져있는 것을 생각하면 된다. 이러한 상황에서 우리는 나무조각을 하나하나 빼내야 한다. 당연하게도 젠가는 통에 담아져있기 때문에 맨 아래 나무조각을 빼려면 맨 위 나무조각부터 하나하나 꺼내서 쌓아야한다. 스택은 이렇게 맨 아래 도착하기 위해 맨 위에 있는 것부터 튀어나오는 구조이다. 이를 전문 용어로 Fi.. Java - 알고리즘 2021. 11. 7.

• 

  백준 Java - 문자열 단계(1) : 11720번, 10809번 , 2675번, 1157번 이번에는 글쓰는 주기가 살짝 늦었네요ㅠㅠ반성하겠습니다... 여튼 오늘도 자바 백준문제 시작합니다! 오늘부터는 문자열 단계 문제입니다. 1. 11720번 : 숫자의 합 구하기 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하라. static void Q_11720() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int num = Integer.parseInt(br.readLine()); // 첫번재 숫자 입력 ch.. Java - 알고리즘 2021. 11. 2.

• 

  백준 Java - 4단계 1차원 배열 활용하기(3) : 8958번, 4344번 오늘도 백준 자바 알고리즘 2문제를 완료하였습니다. 8958번, 4344번 바로 시작하겠습니다!! 1. 8958번 : OX 퀴즈 문제! OXXXOXXX 와 같이 주어지는 퀴즈가 있다. O 는 문제를 맞은거고 X 는 문제를 틀린것이라고 한다. 이때 문제를 맞은 경우 그 문제의 점수는 그 문제까지의 연속된 O 의 갯수이다. 예를 들어 "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이라고 합니다. 이때 OX 퀴즈 결과가 주어졌을때 점수를 구하는 코드를 작성해야한다. static void Q_8958() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buffe.. Java - 알고리즘 2021. 10. 25.

• 

  백준 Java - 4단계 1차원 배열 활용하기(2) : 3052번, 1546번 오늘도 자바 알고리즘 문제 중 3052번 1546번 총 2문제 풀이를 완료했다. 사실 예전처럼 한번에 모아서 싹! 올리고 싶었는데 점점 문제도 뭔가 어려워지고, 코드도 길어져서 이제 풀고 바로바로 올리려고 한다. 1. 3052번 : 서로 다른 나머지는 몇 개? 10개의 수를 입력받고 42 로 나누었을 때 서로 다른 나머지값은 몇 개 일까? import java.io.*; import java.util.Arrays; public class Q11_2 { public static void main(String[] args) throws IOException { Q_3052(); } static void Q_3052() throws IOException { BufferedReader br = new Buffe.. Java - 알고리즘 2021. 10. 20.

• 백준 JAVA - 4단계 1차원 배열 활용하기(1) 이번에는 1차원 배열 문제를 풀어보았다. 뭔가 이전에 for 에 비해서 난이도가 확! 올라간 것 같은 느낌이였다. while 문을 그냥 넘긴 이유는 for 문을 한 번 했으니까 다른 문제를 먼저 접해보고 싶었다. 1차원 배열 문제중 10818번, 2562번, 2577번을 풀이 및 코드이다. 1. 10818번 - 최솟값, 최댓값 찾기 static void Q_10818() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 변수 초기화 int num1.. Java - 알고리즘 2021. 10. 15.