차곡차곡 성 쌓기
article thumbnail
[백준] 로봇 조종하기(2169): DP - Java
카테고리 없음 2025. 3. 21. 15:50

1. 문제  요약양옆, 밑으로 가면서 얻을 수 있는 최대 가치의 합 구하기  2. 접근몇일 전 코테 봤을 때 문제랑 비슷해서 다시 풀어봤다. 과거에 풀었던건데 코테 때는 생각도 안났다. 고민했던 부분- BFS하면 무조건 시간초과 날 것 같음. 그러면 DP인데 어떻게 구하지?- DP로 중복 방문을 어떻게 체크하지?- 다음 칸으로 가는 경우가 3가지인데, 어떤 기준으로 갱신을 해주지? 이런 문제 처럼 그래프 문제 같은데, 그렇게 하다간 분명 시간초과가 날것 같을 때. 문제에 힌트가 있다. 바로 위로는 못 간다는 것이다. 무조건 아래로만 갈 수 있다.   3. 알고리즘위로는 안가니깐 밑으로 내려가기 전에, 해당 층에서 얻을 수 있는 최대 이익을 구한다. 방문했던 칸은 다시 안간다고 했다. 그러면 갈 수 있는 ..

article thumbnail
[백준] 4와 7 : 2877: 구현, 이진 수 - Java
알고리즘/백준 2025. 3. 21. 15:03

1. 문제  요약4와 7을 이용해서 K 번째 작은 수 만들기  2. 접근작은 수를 차례로 써보면  4,7,44,47,77,444,447,474...이다. 숫자만 다를 뿐 두 개의 수로 표현한다는 점에서 이진수를 표현하는 방법과 유사하다.k번째로 작은 수0과 1로 표기4 071440047017711444000447001474010 이 방법까지 떠올리면 반은 온거다. 하지만 이진 수랑 다른 점이 있다. 바로 맨 앞 bit에 0이 온다는 것이다. 최대한 이진수랑 연관시켜서 방법을 찾아야 한다. 이진수를 쭉 써보자 k번째로 작은 수0과 1로 표기이진수401711044001147011007711101444000110447001111 규칙이 있다. 잘 보면 k번째 작은 수는 k+1를 이진 수로 표현한 것에서 맨 앞..

[프로그래머스] level2 - [1차] 캐시
카테고리 없음 2025. 3. 18. 21:19

1. 문제캐시지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오  입력 형식캐시 크기(c..

[프로그래머스] level2 - 짝지어 제거하기

1. 문제짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면b aa baa → bb aa → aa →의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.   2. 코드import java.util.*;class Solution{ public int sol..

article thumbnail
[백준] 카드섞기 : 21315 - 완탐 (Java)
알고리즘/백준 2025. 3. 8. 15:38

1. 문제https://www.acmicpc.net/problem/21315 요약카드를 2번 섞은 후에 결과를 줄테니, 각 2번의 k 값을 구해라  2. 접근독해력이 안좋아서 문제 이해하기가 어려웠다. 아무튼 k의 값을 구하는 건데, 문제의 조건을 보면3 ≤ N ≤ 1,0001≤ K, 2K 로 k는 1~9의 값을 가질 것이다. 그리고 두 번만 수행하면 되니 최대 많아야 9*9 = 81번이니 완탐으로 접근한다. 최종 결과를 보고 처음 결과로 돌아가기(x)처음엔 입력으로 주어진 결과를 이용하여 연산을 거꾸로 해서 초기값을 찾고자 했다. 하지만 좋은 방법이 아니였다. 연산이 더 복잡해지고 생각할 것이 많아진다. 처음상태를 가지고 최종 결과와 비교하기(o)그래서 초기 값이 {1, 2, 3..., N} 순서로 주..