전체 글145 [백준 2293] 동전1 / 자바 / dp 문제 레벨: G4알고리즘: dp ( dp 업데이트 기준 1개 + 일차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/22931 번째 시도 [잘못된 알고리즘]이문제는 dp문제이다. 왜 dp일까?1원일 때 경우의 수 dp =[1] 2원일 때 경우의 수 = {1,1}(1을 만들 수 있는 경우의 수 x 1을 만들 수 있는 경우의 수) {2,0}(2를 한 번에 만 들 수 있는 경우 수) .. 2024. 6. 5. [프로그래머스 LV3] 연속 펄스 부분 수열의 합 / 자바 / DP 문제 레벨: LV3알고리즘: DP(쉬운버전 / cause: 1차원배열 사용)풀이시간: 1시간힌트 참조 유무: 유https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1 번째 시도 [문제 설명](1) 2 3 -6 1 3 -1 2 4 전체 연속배열 x -1 1 -1 1 -1 1 -1 1 펄스배열----------------------------- -2 3 6 1 -3 -1 -.. 2024. 6. 4. [백준 1339번] 단어 수학 / 자바 / 그리디 ** 문제 레벨: G4알고리즘: 그리디풀이시간: 50분힌트 참조 유무: 유(아이디어 참조)https://www.acmicpc.net/problem/1339 1 번째 시도 [알고리즘 선택 과정]입력 제한을 보니 DFS도 가능하다.그러나 Greedy문제이기 때문에 Greedy로 풀어보겠다. [Greedy란?]탐욕적 알고리즘이라고도 불린다.현재의 단계에서 최적을 선택해 마지막의 최적의 정답을 도출한다는 아이디어이다.근시안적으로 현재만 보고 선택하는 것이 탐욕적 알고리즘이라고 불리는 게 어울린다. [Greedy 과정]알파벳이 주어진 순대로 탐색할 것이다. 납득이 가는 과정일 것이다. 그렇다면 어떨 때 알파벳의 숫자를 바꿔줘야 할까?새로운 알파벳이 해당 숫자의 알파벳보다 자릿수가 높을 때 숫자를 바.. 2024. 6. 3. [백준] 수 찾기 / 자바 문제 레벨: S4알고리즘: 이분 탐색풀이시간: 10:29힌트 참조 유무:https://www.acmicpc.net/problem/19201 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp.. 2024. 6. 2. [백준] 숫자 찾기 / 자바 문제 레벨: 알고리즘: 이분탐색풀이시간: 40분힌트 참조 유무: 유https://www.acmicpc.net/problem/10816 1 번째 시도 [upper-bound, lower-bound 차이]lower bound, 즉 하한은 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미한다. upper bound, 즉 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다. 중복 원소에 대한 길이 = (상한 - 하한) mport java.util.Arrays;import java.util.StringTokenizer;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException.. 2024. 6. 1. [백준] 공유기 설치 / 자바 문제 레벨: G4알고리즘: 이분탐색 풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/21101 번째 시도 만약, 이 문제를 풀이하기 전에 이분탐색에 대해 조금이나마 헷갈리는 부분이 있다면 필자가 풀이한 숫자카드 2 문제를 한 번 보고 오시는 것을 추천드린다.자카드 2 문제에서 다루었던 Upper Bound, Lower Bound 형식을 그대로 적용시키면서 최대한 코드 재사용성을 높이고자 같은 구조를 띄도록 노력하고 있다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer; i.. 2024. 5. 31. [백준] 감시 / 자바 문제 레벨: G3알고리즘: 완전탐색 풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/156831 번째 시도: 실패 [알고리즘 선택 과정]각 cctv마다 방향 설정이 중요합니다그렇다면 각 cctv의 방향을 무슨 기준으로 놓아야 할까요주장: 각 CCTV마다 칸을 많이 차지하는 방향으로 반론: A가 칸이 많이 차지하는 방향, B가 칸이 많이 차지하는 방향으로 설정했는데 A,B가 겹치는 것이 많은 상황을 가장해보자.(주장 답안)0 0 #0 0 2(A)0 0 #0 0 2(B)0 0 #(정답 답안)0 0 0# # 2(A)0 0 0# # 2(B)0 0 0 그래서 이 주장은 옳지 않습니다. 패스그렇다면 완전탐색으로 각 CCTV의 모든 방향마다 확인해.. 2024. 5. 30. [백준] 가장 긴 증가하는 부분 수열 2 / 자바 ** 문제 레벨: G2알고리즘: 이분탐색풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/120151 번째 시도 [ LIS (Longest Increasing Subsequence) 란]어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이다.LIS를 구할 때는 DP를 사용한다.LIS의 길이를 구할 때는 이분 탐색(O(nlogn))을 사용한다. DP(O(n^2))로 길이를 구할 시 시간초과가 난다[알고리즘 설명]*이 알고리즘은 고정된 사고를 달리해서 이해해야 합니다*핵심 아이디어: 길이가 동일한 증가 부분 수열 중에서 마지막 값이 작은 것을 유지합니다.지금부터 배열을 순회하면 LIS를 찾아보도록 하겠습니다.수열 A가.. 2024. 5. 29. [백준] 최단경로 / 자바 문제 레벨: G4알고리즘: 다익스트라 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17531 번째 시도 [다익스트라 알고리즘에서 우선순위 큐를 쓰는 이유]최소거리 값 갱신 횟수의 감소때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다.import java.io.*;import java.util.*;class Node implements Comparable{ int end, weight; public Node(int end, int weight){ this.end = end; this.weight = weight;.. 2024. 5. 28. 이전 1 2 3 4 5 6 ··· 17 다음
