알고리즘 테크닉 - LR 테크닉

1. 문제 [3, 6, 2, 6, 7, 5, 2] 와 같이 숫자들이 주어졌을 때, 다음 질의에 대해 답하는 프로그램을 작성해보세요. 단, 질의마다 하나의 숫자가 주어지며 해당 번째 숫자를 제외한 다른 숫자들에 대해 인접한 숫자간의 차이의 합을 구해야 합니다. 예를 들어 질의로 5가 주어졌다면 5번째 숫자인 7을 제외한 다른 숫자들을 나열하면 [3, 6, 2, 6, 5, 2]가 되므로 인접한 숫자간의 차이의 합은 |3 - 6| + |6 - 2| + |2 - 6| + |6 - 5| + |5 - 2| = 15가 됩니다. 이때 주어지는 숫자는 1초과 N 미만임을 가정해도 좋습니다. -------------------------------------------------------------------------..

• format_list_bulleted 알고리즘 일반
• · 2023. 4. 16.
• textsms

알고리즘 테크닉 - 좌표압축(grid compression)

1. 좌표압축이란 정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때, 1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요. 일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서, 큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다. 하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다. 그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며.. 이 정점들의 번호를 1번부터 순서..

• format_list_bulleted 압축 알고리즘
• · 2023. 4. 14.
• textsms

[Java]자바 매개변수 탐색 - 배열에서 특정 수를 지우고 k번째 수를 찾는 방법

1. 문제 1부터 차례대로 숫자를 적는데, 3이나 5의 배수는 숫자 대신 "Moo"라고 적습니다. 예를 들어 1부터 16까지의 숫자를 적는다면 아래와 같습니다. 1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16 이 때, N번째로 적히는 숫자는 무엇인지 구하는 프로그램을 작성해보세요. 2. 풀이 이게 쉽나?? 되게 어려운데 이분탐색에 얽매이다보니 적절한 생각이 안드네 답을 보니까 약간 소름돋았다 배열에서 K번째 수를 어떻게 찾을 수 있을까?를 생각해본다면.. 1부터 n까지 들어있는 배열 A에서, k번째 수를 나타내는 A[k]의 의미는? k이하의 수가 k개라는 뜻이다. 배열에 빈 부분이 없으니까 이게 무슨소리야? 하겠지만.. 그러면 이제 1부..

• format_list_bulleted 이분 탐색
• · 2023. 4. 7.
• textsms

[Java]예시문제로 자바 매개변수 탐색 기본기 배우기1

1. parametric search란 무엇인가1 - 합에 대한 탐색 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 문제를 푼다면, 1,2,3,...,30 전까지 계속 더해보면서 최초로 합이 100을 넘는 경우, 그 숫자를 return하게 된다. 하지만 다음과 같이 시도해본다면? 1차시도: n = 15 15까지의 합은 120이므로 15는 답의 후보이며, n의 최솟값을 찾기 위해 이러한 합보다 더 작은 합은 1~14중 하나에서 찾을 수 있다. 2차시도: n = 7 7까지의 합은 28이므로, n은 확실히 7보다 커야하며, 8~14를 조사해본다. 3차시도: n = 11 11까지의 합은 66이므로, n은..

• format_list_bulleted 이분 탐색
• · 2023. 4. 5.
• textsms

자바 HashMap - 개발자가 정의한 class를 key로 만드는 방법

자바의 HashMap은 파이썬의 dict처럼, 고유한 key와 대응하는 value를 하나의 쌍으로 하여, 저장하는 자료구조 일반적으로 key를 문자열, 정수값으로 사용하지만, 필요에 따라 특정한 class를 key로 하고 싶을 수 있다 시험에 아래와 같은 Point라는 클래스를 key로 하고 싶었는데... class Point { int x,y; public Point(int x, int y) { this.x = x; this.y = y; } } 이걸 HashMap의 key로 사용해서 자료를 관리해볼려 했는데.. 원하는대로 동작을 안하더라고? 그립습니다 파이썬님 자연스럽게 두 객체 p1, p가 같다는 것은 x,y가 서로 같다는 것인데.. 문제는 key로 사용한 p1의 주소와 get을 하면서 넣은 p의 주..

• format_list_bulleted Java 기초
• · 2023. 4. 3.
• textsms

[Java]자바로 이진탐색 연습2 -올바르게 사고하기-

1. 문제 n개의 점과 m개의 선분이 주어질 때, 각 선분 위에 몇개의 점이 있는지 구하는 프로그램을 작성해보세요. 첫 번째 줄에 n과 m이 공백을 두고 주어집니다. 두 번째 줄에는 점의 좌표가 공백을 사이에 두고 주어집니다. 세 번째 줄부터 m개의 줄에 걸쳐 선분의 시작점과 끝점이 공백을 두고 한 줄에 하나씩 주어집니다. 1 ≤ n, m ≤ 100,000 1 ≤ 주어지는 수 ≤ 1,000,000,000 3 4 10 30 50 1 5 5 21 22 59 210 293 2. 풀이 아무 생각없이 사고 한다면... 선분의 시작점 끝점 예를 들어 1 5를 기준으로, 여기에 점의 좌표 10,30,50이 들어있는지 검사해보는 식으로 이렇게하면 O(MN)인가? 사실 이러면 이진탐색이고 뭐고 점의 좌표 10,30,50..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms