본문 바로가기

ALGORITHM37

알고리즘 백준 문제 로드맵 (추천) https://code.plus/course/41 알고리즘 기초 1/2 알고리즘 기초 code.plus 백준 알고리즘 온라인 강의 사이트인데, 알고리즘 초급/중급/고급 강의에 나와있는 문제들을 차례대로 풀어보면 좋을 것 같음. 백준에서 뭐부터 풀어야 하나 고민이 많았는데, 이대로 풀면 정리되는 느낌이 들듯. 아래는 알고리즘 기초 1/2 강의의 문제들 2021. 5. 31.
[JAVA] 백준 1789번 https://www.acmicpc.net/problem/1789 1789번 수들의 합 문제 재정의: "서로 다른" n개의 숫자가 있다. n개의 수를 다 더하면 총합 s가 됨. s가 주어질 때 n의 최댓값은 무엇인가 생각한 것: 1부터 19까지 더하면 190인 거임. 1부터 1씩 더해가면서 s가 도달할 때까지의 count을 출력하면 되는 거 아닌가? 그래야 '최대'를 구할 수 있지 않나 싶다 런타임 에러 났지만, s의 범위가 S(1 ≤ S ≤ 4,294,967,295) 여서 int가 아닌 long을 써주니 바로 해결. -> Long.parseLong 코드: package till; import java.io.BufferedReader; import java.io.IOException; import jav.. 2019. 9. 1.
[JAVA] 백준 10871번 https://www.acmicpc.net/problem/10871 문제 재정의: 수열 중 주어진 숫자보다 작은 수를 출력 생각한 것: 배열보다 큐로 하는 게 더 깔끔하다고 생각 코드: package till; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I.. 2019. 9. 1.
[JAVA] 백준 2455번 문제: https://www.acmicpc.net/problem/2455 2455번 지능형 기차 문제 재정의: 빈칸을 두고 입력됨 모두 내려야 승차 가능 기차에 제일 많은 사람이 있을 때를 출력 총 4개의 역. 역 번호 순서대로 운행 생각한 것: 사람 수 어떤 자료구조에 저장 배열? 4개의 역이라 2차원 배열 말고 그냥 8개 변수 생성 현재 남아 있는 승객 수 저장. 더 크면 update 코드: package till; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static .. 2019. 8. 25.
해결 x, 기억 o 문제 list 백준 1063번 킹 - 런타임 에러. 해결 x. 노가다로 풀어서 정답은 나오나 런타임 에러 남 (https://www.acmicpc.net/problem/1063) 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다. 킹은 다음과 같이 움직일 수 있다. R : 한 칸 오른쪽으로 L : 한 칸 www.acmicpc.net 프로그래머스 가장 큰 수 - 틀렸습니다. 해결.. 2019. 8. 21.
[JAVA] 백준 1173번 문제: https://www.acmicpc.net/problem/1173 1173번: 운동 첫째 줄에 N m M T R이 주어진다. N T R은 200보다 작거나 같은 자연수이다. m은 50보다 크거나 같고, 200보다 작거나 같은 자연수이고, M은 m보다 크거나 같고, 200보다 작거나 같은 자연수이다. www.acmicpc.net 운동 1173번 - 시뮬레이션 문제 재정의: 1분마다 운동/휴식 하나 선택해야 함 운동 N분 함 운동- T증가, 휴식 - R감소 맥박 M 넘기면 안 됨, m은 넘어야 함. 처음 맥박은 m 운동 과정 끝내는데 걸리는 시간의 최솟값 출력 생각한 것: 설탕 배분 문제(2839번)가 떠오름. 문제 개념이 비슷하다고 생각 듦 -이문제는 dp문제였음. dp로 접근하는 것이 맞는지. 근.. 2019. 8. 17.
[JAVA] 백준 1592번 https://www.acmicpc.net/problem/1592 1592번: 영식이와 친구들 일단 1번이 공을 잡는다. 1번은 공을 한 번 잡았기 때문에, 공을 3번에게 던진다. 3번은 공을 한 번 잡았기 때문에, 공을 5번에게 던진다. 5번은 2번에게 던지고, 2번은 4번에게 던진다. 4번은 1번에게 던진다. 1번은 이제 공을 두 번 잡았기 때문에, 공을 4번에게 던진다. 4번은 2번에게 던지고, 2번은 5번에게 던지고, 5번은 3번에게 던지고, 마지막으로 3번은 1번에게 던진다. 1번은 이제 공을 세 번 잡았기 때문에, 게임은 끝난다. www.acmicpc.net 영식이와 친구들 1592번 문제 재정의: 사람 n명, 한 사람이 공을 m번 받으면 종료된다, m보다 적게 공을 받은 사람이 L번째 사람에.. 2019. 8. 17.
[JAVA] 프로그래머스 가장 큰 수 [가장 큰 수] https://programmers.co.kr/learn/courses/30/lessons/42746 문제 재정의: numbers배열이 주어짐 (input) numbers 배열에 있는 숫자를 조합하여 가장 큰 수를 만들어 '문자열로' return numbers의 길이는 1 이상 100,000 이하, numbers의 원소는 0 이상 1,000 이하 예외 테스트 케이스 0, 0, 0, 0 -> 0 0, 1000, 0, 0 -> 100000 12, 121 -> 12121 21, 212 -> 21221 [0,0,0,1000] [0,0,1000,0] [1000,0,0,0] 틀리기 쉬운 입출력 예제 (출처:https://stroot.tistory.com/114[Strong Root]) 입력 출력 {.. 2019. 7. 15.
[JAVA] 백준 1260번 [백준 1260번 DFS와 BFS] https://www.acmicpc.net/problem/1260 문제 재정의: https://mygumi.tistory.com/102 생각한 것: 일단 인접 행렬에 input값들을 저장해 트리 구조를 저장 (양방향임을 주의) DFS는 따라 따라 가면됨. 끊기면 오른쪽으로 이동 BFS는 한 번 내려가고 바로 오른쪽, 맨 오른쪽까지 간다음 다시 왼쪽으로 돌아와 탐색 코드 //이클립스 코드 package till; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.uti.. 2019. 7. 8.
[JAVA] 프로그래머스 기능개발 문제: https://programmers.co.kr/learn/courses/30/lessons/42586 [기능 개발] 문제 재정의: 작업의 진도가 적힌 정수 배열 progresses. input 각 작업이 하루에 % 할 수 있는지 개발 속도가 적힌 speeds 배열. input 뒷 기능이 먼저 끝난다해도 앞 기능이 끝날 때 같이 배포됨. 생각한 것: 1.몇일 후에 배포 가능한지 계산해서 순서대로 새로운 저장공간 a에 저장. 2.a에 저장되어 있는 값들 & 큐를 이용해 계산 - a[0]을 일단 pivot으로 - 그 다음 값이 a[0]보다 작거나 같을때까지 count++ (count는 초기값이 1) - 다음 값이 a[0]보다 크다면 큐(temp)에 count를 집어넣어줌. - 그리고 a[0]이었던 pi.. 2019. 6. 24.
[JAVA] 프로그래머스 쇠막대기 문제 https://programmers.co.kr/learn/courses/30/lessons/42585 [쇠막대기] 문제 재정의: 인접한 ()는 레이저, 여는 괄호( 와 닫는 괄호)로 쇠막대기 input 받음 긴 쇠막대기 위에만 올릴 수 있음 각 쇠막대기 자르는 레이저 적어도 하나 존재 레이저는 쇠막대기의 양 끝점 절대로 겹치지 x 쇠막대기는 다른 막대기들의 끝점과 겹치지 않게 올려야 함 생각한 것: input받은 괄호를 분석해 구분하여 데이터 저장해놓는 것이 우선 스택으로 구현. (스택으로 후위 계산식 계산하는 코드 생각이 남. 이걸 참고 해야겠다고 생각. ) 스택에 일단 차례대로 집어 넣는다. 근데 이때 )괄호를 만나면 pop 해주고, 인접한 괄호라면 레이저 정보 업데이트, 그리고 count +2.. 2019. 6. 24.
[JAVA] 프로그래머스 H-Index 문제: H-Index https://programmers.co.kr/learn/courses/30/lessons/42747 [H-Index] 문제 재정의: citations 배열(input)의 length->n citations 배열 중 h 이상 인용된 논문이 h개 이상이고, 나머지 논문이 h번 이하 인용되었다면, h return 생각한 것: 일단 citations 배열 정렬 배열.length의 /2를 일단 int h로 잡고 검사. h 이상 인용된 논문이 h편 이하이면 h--, 또 검사. h 이상 인용된 논문이 h편 이상이면 h++, 또 검사. 반복. ->h이상 인용된 논문의 갯수를 count로 잡음 2번 단게를 반복하다가 h이상 인용된 논문이 h이면, 나머지 논문이 h번 이하 인용되었다면. 맞다면 re.. 2019. 6. 24.
[JAVA] 프로그래머스 K번째수 문제: K번째수 https://programmers.co.kr/learn/courses/30/lessons/42748 [k번째수] 문제 재정의: 원본 배열 array (input) commands. [i=나눌 배열 첫번째 인덱스 번호, j=마지막 인덱스 번호, k=return할 인덱스 번호 ] (input) commands의 인덱스2의 값을 배열에 담아 return 이클립스에서 할 때 commands 몇개 넣을지 숫자도 input 받기 (편의상) commands의 길이는 1 이상 50 이하입니다. commands의 각 원소는 길이가 3입니다. 생각한 것: 정렬함수 만들어서 정렬함수 매개변수에 commands 에서 정렬, 그리고 답 return sort(배열, fromIndex, toIndex) 사용 So.. 2019. 6. 24.
[JAVA] 알고리즘을 최적화 해보자 1. Scanner 입력 대신 BufferedReader를 사용하자 왜? 효율면에서 훨씬 굳 (입력값이 많을수록) BufferedReader는 데이터를 사용자가 요청할 때마다 '매번' 읽어오기 (X) 일정량 사이즈로 '한 번에' 읽어온 후 버퍼에 보관. 사용자가 요구할 때 버퍼에서 읽어오게 한다. (O) -> 속도 향상, 시간 부하 줄일 수 있다 (Scanner의 버퍼 사이즈는 1024 chars VS BufferedReader의 버퍼 사이즈는 8192 chars) 얼마나 빠른지 밑에 사진 참고. (출처: 알고스팟) 깨알 지식: BufferedReader 나오고 난 뒤에 Scanner 나옴 각각 특징: Scanner: space를 모두 경계로 인식. 가공하기 쉽다. 효율 낮음 BufferedReader:.. 2019. 6. 24.
[JAVA] 백준 2869번 [백준 2869] 달팽이 문제: https://www.acmicpc.net/problem/2869 문제 이해: (1 ≤ B < A ≤ V ≤ 1,000,000,000) 낮에 a 올라갈 수 있고, 밤에는 b 미끄러진다. 그러나 v미터인 정상에 도착하면 밤이어도 미끄러지지 않는다. 하고자 하는 것: 그렇다면 하루에 올라가는 미터는 a-b, 그러나 낮에 정상에 올라가면 밤에 떨어지지 않는 부분을 넣어야 됨. 코드: (시간 초과 남 ) package till; import java.util.Scanner; public class Main { public static void main (String[] args) { Scanner scan = new Scanner(System.in); int day= scan.n.. 2019. 6. 4.
[JAVA] 백준 11399번 [백준 11399] ATM 문제: https://www.acmicpc.net/problem/11399 전형적인 그리디 문제 문제 이해: 각자 번호가 있고, 각 번호마다 할애하는 시간이 주어진다. 고객을 어떻게 세우냐에 따라 시간의 합을 조절할 수 있는데, 최소의 시간의 합을 구하기. 하고자 하는 것: 그 순간순간에 제일 시간이 적게 걸리는 사람들을 채택. : input된 시간들 배열에 저장. 배열 Array.sort(). 걸리는 시간들을 다 더한 result 도출 : += 이용 package till; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main (String[] args) { S.. 2019. 6. 4.
[JAVA] 백준 2293번 https://www.acmicpc.net/problem/2293 동전 1 -다이나믹 프로그래밍 [백준 2293번] 동전 1 예제를 풀어 봄 문제 파악 해서 정리 해 봄: n개의 숫자 조합을 이용해 합 k를 맞추는 경우의 수를 찾는 문제. (순서 상관없고, n개 다 이용 안 해도 됨, 동전 중복 사용 가능) 풀이 생각해 봄: dp 1원부터 생각->1,2원 두가지 동전 종류가 있을 때 생각 -> 1,2,3원 세 가지 동전 종류가 있을 때 생각 ~ 이 과정에서 규칙을 발견하고 점화식 세워보기 코드 짜기. 출처 https://songsunbi.tistory.com/67 하나 더 고려해야 할 점이 있습니다. 3원으로 경우의 수를 계산하는데 1원과 2원의 경우를 계산할 필요가 있을까요? 어차피 제가 가지고 있는 .. 2019. 6. 2.
[JAVA] 백준 8979번 https://www.acmicpc.net/problem/8979 올림픽 -정렬 [백준 8979번] 올림픽 문제 이해: 올림픽 메달 개수로 순위 매기기 답 봄 . 2차원 배열로 한 사람 https://yeolco.tistory.com/8 내가 하려고 한 것: 2차원 배열에 메달 정보 저장. 정렬 클래스 따로 작성. 메인에서 금메달을 내림차순 정렬&은메달 내림차순 정렬&동메달 내림차순 정렬을 함. 금메달 내림차순 정렬한 것대로 순위 매김. but 금메달 동점 국가가 있다면 은메달 내림차순 정렬된 것으로 순위 매김 but 은메달 동점 국가가 있다면 동메달 내림차순 정렬된 것으로 순위 매김 해서 답을 내려고 했음. 근데, 'but' 부분이 생각대로 안되서 포기하고 답을 봄 안 된 부분 ex) 금메달 따로 정렬.. 2019. 6. 2.

티스토리툴바