본문 바로가기

Algorithm64

[백준] 18870번-좌표 압축-Java [백준] 18870번-좌표 압축 🖊️풀이법 이번 문제는 너무 복잡하고 비효율적이게 생각해서, 시간초과로 애를 좀 먹었다.. 결론부터 얘기하자면, 너무 어렵게 생각했고 조금 시간을 가진뒤 코드를 다시 보니 쉽게 풀 수 있는 문제 였다 :) 이번 문제는 배열의 중복을 제거하고, HashMap을 이용해서 중복값을 제거한 후에 해당 요소가 몇번째 요소인지 키값으로 저장 후 기존의 배열과 매칭시켜 출력하는 방식으로 풀었다. 우선, 처음에 삽질한 시간초과 코드를 살펴보자.. 시간초과 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedRe.. 2023. 7. 9.
[백준] 7785번-회사에 있는 사람-Java [백준] 7785번-회사에 있는 사람-Java ❓문제 N명의 직원의 출입기록을 이름+ (enterorleave) 형태로 받아 leave기록이 없는 직원을 사전 역순으로 출력해주면 된다. 🖊️풀이법 문제만 봐도 key와 value매칭을 이용한 Map을 사용해야 하는 느낌이 온다..! 반복문을 통해 주어진 요소들을 Map에 key와 value로 요소들을 담는다. 담긴 요소에서 value값을 조회하여, 만약 value값이 leave인 경우 map에서 제거해준다. 맵 객체에서 정렬을 할 수 있도록 list객체로 변환해준다. list객체를 사전 역순으로 정렬한다. 정렬된 list를 하나의 요소씩 출력한다. 정답 코드 import java.util.*; import java.io.*; public class Mai.. 2023. 7. 9.
[백준] N과 M (2)-Java [백준] 15650-N과 M (2)-Java ❓문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 예제 입력 4 2 예제 출력 1 2 1 3 1 4 2 3 2 4 3 4 🖊️풀이법 이번 문제는 백트리킹 카테고리의 두번째 문제이다. 앞전에 풀었던 15649에서 설명했던 DFS의 개념을 가지고 문제를 만약 해당 알고리즘의 개념이 궁금하다면, [백준] 15649-N과 M (1)-Java를 참고하자. 정답 코드 import java.util.*; import java.io.*; public class Main { static .. 2023. 7. 9.
[백준] 11729-하노이 탑 이동순서-Java [백준] 11729-하노이 탑 이동순서-Java 🖊️풀이법 하노이탑의 핵심 개념을 한번 먼저 살펴보자. 1번에 쌓여있는 원판들을 3번까지 옮겨야한다. 1회에 한 개의 원판만 옮길 수 있다. 반드시 큰 원판 위에 작은 원판이 있어야한다. 이 세가지 조건을 부합하여 문제를 살펴보자. 1번에 있는 가장 큰 원판을 3번으로 옮기기 위해서는 n-1개의 원판이 1번 -> 2번으로 가야한다. 1번에서 2번으로 가는 것을 hanoi함수로 정의한다면 hanoi(n-1)이 된다. 그 후 1번의 가장큰 원판이 3번으로 이동한다. 그렇다면, 이동횟수는 +1이 된다. 2번에 있는 (n-1)개의 원판이 3번으로 이동하기 위해서는 다시 hanoi(n-1)이 된다. 그렇다면 hanoi(n) = 2 * hanoi(n-1) + 1로 표.. 2023. 7. 9.
[백준] N과 M (1)-Java [백준] 15649-N과 M (1)-Java ❓문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 🖊️풀이법 이번 문제는 백트리킹 카테고리의 첫번째 문제이다. 백트래킹이란 해석하면, ‘되추적’이라는 말로, 알고리즘적으로 설명 하나의 결과를 찾는 도중 결과가 아닌 값을 마주했을 때 돌아가서 다시 결과를 찾는 것을 말한다. DFS(깊이우선탐색) 이번 문제의 경우 백트래킹의 대표적인 방법 중 하나인 DFS(깊이우선탐색)를 이용하여, 풀 수 있다. DFS란 깊이 우선 탐색법으로, 위의 사진과 같이 상위노드에서 가장 깊은 노드까.. 2023. 7. 9.
[백준] 4779-칸토어 집합-Java [백준] 4779-칸토어 집합-Java ❓문제 ’-‘가 3N개 있는 문자열에서 시작한다. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 계속해서 반복하여, 모든 선의 길이가 1일때 까지 반복한다. N의 범위 0 ≤ N ≤ 12 예제 입력 0 1 3 2 예제 출력 - - - - - - - - - - - - - - - 🖊️풀이법 재귀함수를 이용하면 좋은 문제이다. 범위를 3등분 한다. 3등분한 범위의 가운데를 공백으로 바꿔준다. 해당 작업을 반복하며, 범위가 1이되면, 재귀함수 호출을 종료한다. 정답 코드 import java.io.*; public class Main { static char[] charArr; static StringBuilder answer; public static voi.. 2023. 7. 9.

티스토리툴바