본문 바로가기
◀ PREV [1] [2] [3] [4] [···] [6] NEXT ▶
11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아까 개념을 2차원 배열에 적용시켜서 푸는 문제다 그림을 그리면 이해가 잘 되고 구간합 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]; 범위로 구간합을 구할때 (x1,y1) (x2,y2) 두 좌표의 범위의 구간값은 sum[x2][y2] - sum[x1-1][y2] - sum[x2][y.. 2023. 10. 12.
11659 구간 합 구하기 11659 구간 합 구하기 몸비틀기 느낌으로 풀었는데 인덱스를 1번부터 햇으면 편햇을 것 같다 각 자리까지 배열합 = 구간합[i-1] + 배열[i] 구간합 = s[j] - s[i-1] StringTokenizer를 처음 알게 되었고 잘 사용해 보자.. BuffredReader = 0) res[i] = sum[b] - sum[a]; else res[i] = sum[b]; } for (int x : res) System.out.println(x); } } 책코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Main { public static.. 2023. 10. 12.
프로세스 https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우선순위 큐를 이용하면 프로세스를 다시 넣는 2번 과정을 거치지 않아도 된다 처음에 풀때는 큐를 사용해서 해보려다가 막히고 우선순위 큐를 사용해서 꺼낸값을 초기 인덱스와 꺼낸 값의 인덱스를 비교해서 문제를 푸는식으로 이해했다 import java.util.*; class Solution { public int solution(int[] priorities, int location) { int an.. 2023. 10. 9.
시저 암호 https://school.programmers.co.kr/learn/courses/30/lessons/12926 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.Scanner; class Solution { public String solution(String s, int n) { char[] arr = s.toCharArray(); String answer = ""; for (char x : arr) { if (Character.isLowerCase(x))x = (char) ((x+n -'a') % 26 + 'a'); el.. 2023. 10. 5.
소수 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/12921 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그냥 n제곱으로 돌리면 시간초과 sqrt(n)으로 제곱근(제곱근까지 해도 그냥 소수와 결과가 같다)을 돌리거나 에라토스테네스의 체 n까지 입력받으면 인덱스를 각 자릿수로 초기화 만난 수가 0이 아니면 그 수의 배수들을 전부 0으로 바꾸는 연산을 n이 될때가지 수행 남아있는 수는 소수 에라토스테네스의 체로 구했다 import java.util.*; public class Solution { publ.. 2023. 9. 21.
문자열 int tmp = Arrays.asList(seoul).indexOf("Kim"); String[] 배열에서 특정 문자열 위치 찾기 2023. 9. 21.
문자열 내림차순 정렬하기 https://school.programmers.co.kr/learn/courses/30/lessons/12917 Arrays.sort(arr, Collectons.reverseOrder);로 정렬이 될줄 알았는데 char[] 배열이라 그런지 정렬이 안됬고 Stringbuilder를 이용해서 .reverse.toString으로 정렬했다 import java.util.*; class Solution { public String solution(String s) { String answer = ""; char[] arr = s.toCharArray(); Arrays.sort(arr); answer = new StringBuilder(new String(arr)).reverse().toString(); ret.. 2023. 9. 20.
문자열 내 마음대로 정렬하기 https://school.programmers.co.kr/learn/courses/30/lessons/12915 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Comparator를 sort 내부에 정의할 수 있는걸 알게 되었다, n번째 char가 다르면 기존에 comparator 사용하는 것처럼 하지만 같으면 string1.compareTo(string2) 형태로 비교하면 사전상 앞에 있는 걸로 비교할 수 있다 import java.util.*; public class Solution { public String[] solution(String[] st.. 2023. 9. 19.
나누어 떨어지는 숫자 배열 https://school.programmers.co.kr/learn/courses/30/lessons/12910 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 ArrayList로 푸는 문제인줄 알았는데 stream.filter를 사용하면 바로 쉽게 풀 수 있다! stream 사용법을 좀더 익혀두자. arr 배열을 스트림으로 변환하고 정렬해서 필터링 다음 다시 배열로 바꿧고 만약 정렬결과 해당되는게 없으면 return new in[] {-1};로 -1이 들어간 배열을 반환했다 import java.util.*; public class Solut.. 2023. 9. 19.
가운데 글자 가져오기 https://school.programmers.co.kr/learn/courses/30/lessons/12903/solution_groups?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr substring으로 문자열 자르는거 잘 익혀두자 import java.util.*; public class Solution { public String solution(String s) { String answer = ""; if (s.length() % 2 == 0) { answer += s.substring(s.length()/2-1,s... 2023. 9. 18.
2016년 https://school.programmers.co.kr/learn/courses/30/lessons/12901 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 노가다로 구했는데 2016년 한정인 경우 말고 다른 경우엔 Calender 클래스를 이용하자! import java.util.*; public class Solution { public String solution(int a, int b) { String answer = ""; int[] mon = new int[13]; int tmp = 0; for (int i = 1; i < mon.lengt.. 2023. 9. 18.
폰켓몬 https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.*; public class Solution { public int solution(int[] num_list) { int answer = 0; HashMap arr = new HashMap(); for (int i = 0; i < num_list.length; i++) arr.put(num_list[i], arr.getOrDefault(num_list[i],0)+1).. 2023. 9. 18.
프로그래머스 코딩 기초 트레이닝 풀면서 알게된거 str.repeat(n) 문자열을 n번 반복 아스키 코드 A - 65, a - 97 32만큼 차이남 \ 출력하고 싶으면 \\을 해주기! a.concat(b); 문자열 a와 b 합치기 String a = sc.nextLine(); System.out.println(a.replaceAll(" ", "")); 문자열 안에서 특정 문자 교체 삼항연산자 조건문 ? 참 : 거짓 str.chatat(i) - i번째 char 반환 str.indexOf ("O") O가 어딧는지 인덱스를 반환 my_string.repeat(k); string k번 반복해서 출력 String.valueOf(a); String.valueOf(""+a+b); String.valueOf(a)+String.valueOf(b); v.. 2023. 9. 13.
최대점수 구하기(냅색) N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 첫 번째 줄에 문제의 개수와 제한 시간이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다. 첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력 입력 5 20 10 5 25 12 15 8 6 3 7 4 출력 41 dp로 문제를 풀때 넣을수 있는 물건의 갯수가 정해져 있으면 뒤에서 부터 시작한다, 9/11 클래스가 없이 2차원 배열을 사용하는 방법으로 다시 풀어보자 import j.. 2023. 9. 11.
동전교환(냅색) dp 문제는 경우를 쪼개서 보는게 중요한 것 같다.. 냅색 알고리즘을 이용해서 푼다 M원을 거슬러 줘야할때 1~M까지 인덱스의 dy배열을 만들어서 최대값으로 초기화한 후 dy[0] = 0(0원 거슬러주는 방법은 0)으로 하고 tmp = dy[j - coin[i]] +1 2023. 9. 10.
가장 높은 탑 쌓기(LIS) 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. 입력 5 25 3 4 4 4 6 9 2 3 16 2 5 1 5 2 출력 10 최대 부분 증가수열을 응용한 문제, 무게와 넓이 중 하나를 잡아서 내림차순으.. 2023. 9. 9.
최대 부분 증가수열(LIS) !다시 풀어보기 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다. 입력 8 5 3 7 8 6 2 9 4 출력 4 부분증가수열, 원소들의 숫자는 유지해야함 dy[i] = 마지막 숫자를 arr[i]로 하는 부분증가수열의 최대 길이 arr[0]의 dy[i]는 맨 앞이므로 1, 그 뒤에 원소들은 arr[i] 앞 인덱스의 원소들을 반복문으로 돌면서 앞에 원소가 arr[i] 보다 작고, dy[앞에원소]가 0보다 크면 .. 2023. 9. 9.
계단 오르기, 돌다리 건너기 DP : 1차원 배열인 다이나믹 테이블을 이용해서 점화식 형태로 나오는 문제의 값을 구한다 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 올라갈 수 있는 방법의 수는 몇 가지인가? 계단을 오르는 방법을 저장하면서 푸는 문제 1번 계단 1가지, 2번 계단 2가지, 3번 계단 3가지... d[n] = d[n-1] + d[n-2] 형태 import java.util.*; class Main{ static int[] dy; public int Solution(int n){ dy[1] = 1; dy[2] = 2; for (int i = 3; i 2023. 9. 9.
원더랜드(최소스패닝트리-프림) 도시를 연결하는 도로의 최소비용 찾기 도시의 개수 V와 도로의 개수 E가 주어진다 입력 9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15 출력 196 프림 알고리즘 - 우선순위 큐를 이용해서 푸는 방법 이번에는 유니온 파인드를 하지 않고 우선순위 큐를 이용한다 Edge 클래스에 현재 정점이어진 정점과 비용만 넣고(입력을 받을때 이중 ArrayList에 get(현재정점).add(new Edge(이어진정점, 비용)) 형태로 받기에 Edge 클래스를 만들때 이어진 정점을 넣는다 현재 정점과 이어진 정점들을 탐색한다 check 배열을 만들어서 이미 정점을 방문했는지를 판단한다 class Edge imple.. 2023. 9. 7.
원더랜드(최소스패닝트리-크루스칼) 도시를 연결하는 도로의 최소비용 찾기 도시의 개수 V와 도로의 개수 E가 주어진다 입력 9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15 출력 196 최소스패닝트리, 크루스칼 알고리즘 등등으로 부르고 내가 이해한건 시작노드, 끝나는 노드, 비용을 가지는 Edge 클래스를 만들어서 비용을 기준으로 오름차순으로 정렬한 arraylist에 edge를 넣고, 시작노드와 끝 노드가 연결됐는지를 유니온파인드로 판단해 노드를 연결한 집합을 만들면서 연결할때마다 비용을 저장해두는 걸로 이해했다 !유니온 파인드는 그냥 방법을 외우자 unf[] 2023. 9. 6.

티스토리툴바