https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 핵심 이 문제는 DFS로 풀면 시간초과가 나게 된다. 따라서 DP를 함께 사용한다. 이미 탐색한 부분은 다시 탐색하지 않는 방법을 이용한다. 정답 코드 import java.util.Scanner; public class Main { static int M; static int N; static int[][] map; static int[] dy = {1, 0, -1, 0}; static int[] d..
https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 DFS를 활용하여 풀 수 있었다. 처음에는 HashMap을 사용하여 풀려고 하였다. HashMap 의 맵을 만들고, 키 값에 시작점을 넣고 value값은 도착점을 넣으려고 하였다. (키값이 중복이 있을 수 있기 때문에 value의 값을 List 으로 하려 함) 하지만 이러한 풀이는 value의 순서에 따라 전부 방문하지 못하는 경우가 생기기도 하였다. 따라서 전부다 탐색을 시도해야 한..
https://school.programmers.co.kr/learn/courses/30/lessons/138477 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 그림은 문제의 일부분이다. 핵심 문제를 간단하게 해석하면, socre는 하루하루 추가되는 점수이다. k의 개수 개까지 명예의 전당에 오르게 된다. -> 상위 k개에서 가장 낮은 점수가 커트라인이 된다. 발표 점수는 커트라인으로 이루어져 있다. 정답 코드, 스트림을 활용 import java.util.ArrayList; import java.util.Comparator; import java..
재귀 함수 문제입니다. 핵심 최댓값과 최솟값을 출력해야 하는데, 여러 가지 방법이 있겠지만 List를 사용하면 쉽게 출력할 수 있다. 정답 코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static int n; static char[] arr; static boolean[] check; static int[] result; static List list; public static void main(String[] args) { Scanner sc= new Scanner(System.in); n =sc.nextInt(); arr = new char[n]; for (int i=..
오늘은 이진 탐색에 대해 정리해보려 한다. 영어로는 Binary Search라고 한다. 이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다. -값들 중에 절반을 기준으로 원하는 값을 찾는다. -절반을 나눈 값을 기준으로 원하는 값이 있는 쪽에서 다시 절반을 나눈다. 즉 이진 탐색은 숫자를 절반씩 지워나가면서 찾는다. 따라서 시간 복잡도는 O(log n)이 된다. 여기서 의문점이 들 수 있다. 정렬해야 하면 O(log n)이 아니라 결국 O(n log n) 아닌가요? -> yes 따라서 이미 배열이 정렬되어 있다면 Binary Search가 효율적이다. 또는 숫자 찾기를 엄청 많이 해야 하는 경우에는 오히려 정렬을 한 뒤에 Binary Search를 하는 것이 좋다. 이제 이진 탐색을 구현해보자...
우선 함수에 대해 알아보자 함수란 값을 입력받아 특정 연산을 수행하여 결과를 반환하는 것이다. 다음은 재귀 함수에 대해 알아보자 자기 자신을 부르는 함수 대표적인 예시는 팩토리얼이다. import java.util.Scanner; public class Main2 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n =sc.nextInt(); System.out.println(getFactorial(n)); } public static int getFactorial(int n){ if (n==0)return 1; else return n*factory(n-1); } } 위 코드를 보면 계속해서 자기 자신을 ..
https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 핵심 2개의 배열의 값을 2진수로 바꾸어, 각 배열의 값이 둘 중 1개라도 1이면 새로운 배열에 # 아니면 공백을 추가해준다. 정답 코드, 처음 풀이 public class Solution { public String[] solution(int n, int[] arr1, int[] arr2) { String[] answer = new String[n]; for (int i =0;i
https://school.programmers.co.kr/learn/courses/30/lessons/12915 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 문자열 내 마음대로 정렬하기 문제 링크입니다. 핵심 이 문제에서 핵심은 정렬을 하는데, 문자열에서 원하는 index의 문자를 비교하여 정렬해야 한다. 정답 코드 import java.util.*; class Solution { public String[] solution(String[] strings, int n) { String[] answer = {}; List list = new..
https://www.acmicpc.net/problem/2204 2204번: 도비의 난독증 테스트 꿍은 도비에게 영어단어들을 제시한 후 어떤 단어가 대소문자를 구분하지 않고 사전순으로 가장 앞서는지 맞추면 양말을 주어 자유를 얻게해준다고 하였다. 하지만 인성이 좋지 않은 꿍은 사실 www.acmicpc.net 2204번 도비의 난독증 테스트 문제 링크입니다. 핵심 HashMap을 사용하여 기존의 문자열을 저장해주고, 전부 소문자로 바꾼다. 정답 코드 import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..
재귀 함수 문제입니다. 핵심 숫자가 작아지는 형태로 나타나야 한다. 재귀 함수를 만들 때, 매개변수로 값의 합과 인덱스 위치를 나타내는 값을 사용한다. 정답 코드 import java.util.Scanner; public class Main { static int[] result; static int n; static int count; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); result = new int[n]; division(0,0); System.out.println(count); } //현재까지 구한 합이 mysum //index번째 숫자를 결정할 차례 result[..
