>알고리즘 문제
1. 롤케이크 자르기
1)문제
문제 설명
철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.
예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.
롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ topping의 길이 ≤ 1,000,000
- 1 ≤ topping의 원소 ≤ 10,000
2)솔루션
class Solution {
fun solution(topping: IntArray): Int {
var answer: Int = 0
val forward=IntArray(topping.size)
val backward=IntArray(topping.size)
val types=HashSet<Int>(topping.size)
for(i in topping.indices){
types.add(topping[i])
forward[i]=types.size
}
types.clear()
for(i in topping.size-1 downTo 0){
types.add(topping[i])
backward[i]=types.size
}
for(i in 0..forward.size-2){
if(forward[i]==backward[i+1]) answer++
}
return answer
}
}-자르는 기준 앞, 뒤 조각내 토핑종류가 같아야 하므로 정순으로 순회하여 잘랐을때 앞부분 토핑종류와 역순으로 순회하여 잘랐을때 뒷부분 토핑종류를 저장해서 그 수가 같아지는 지점의 개수를 반환한다.
2. 트리 트리오 중간값
1)문제
문제 설명
n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다.
- 어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다.
- 임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다.
트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주어집니다. 주어진 트리에서 임의의 3개의 점을 뽑아 만들 수 있는 모든 f값 중에서, 제일 큰 값을 구해 return 하도록 solution 함수를 완성해주세요.
제한 사항
- n은 3 이상 250,000 이하입니다.
- edges의 행의 개수는 n-1 입니다.
- edges의 각 행은 [v1, v2] 2개의 정수로 이루어져 있으며, 이는 v1번 정점과 v2번 정점 사이에 간선이 있음을 의미합니다.
- v1, v2는 각각 1 이상 n 이하입니다.
- v1, v2는 다른 수입니다.
- 입력으로 주어지는 그래프는 항상 트리입니다.
2)솔루션
class Solution {
fun solution(n: Int, edges: Array<IntArray>): Int {
var answer: Int = 0
val route=Array(n){HashSet<Int>()}
for(i in edges){
route[i[0]-1].add(i[1]-1)
route[i[1]-1].add(i[0]-1)
}
//임의의 노드를 가지고 가장먼 노드를 찾는 이유
//가장 긴 루트가 ai와 aj사이라고 하자
//임의의 노드 ak에 대해 ai와 aj사이를 지나는 루트상 노드중 ak에 가장 가까운 노드를 at라 하자
//만약 ak에서 가장 먼 노드가 ai와 aj중 하나가 아닌 al이라 가정하자(al은 at방향의 반대쪽에 위치)
//괄호의 이유:al이 at쪽 방향에 위치하고 가장 먼 노드라 하면 al-at가 at-ai와 at-aj보다 길어야 한다.
//근데 그러면 ai-aj가 가장 긴 루트의 노드 쌍이 아니라 ai-al이나 aj-al이 가장 긴 루트가 되므로 모순.
//ak-ai의 거리는 ai-at+at-ak
//ak-aj의 거리는 aj-at+at-ak
//ak-al의 거리는 ak-al
//맨 아래가 가장큼.
//이때 al-ai와 al-aj거리는
//ai-at+at-ak+ak-al
//aj-at+at-ak+ak-al
//둘의 합보다 ai-aj거리 곱하기 2한것이 더 커야함
//둘의 합:ai-at+at-ak+ak-al+aj-at+at-ak+ak-al=ai-aj+2(at-ak+ak-al)
//ai-aj거리 곱하기2:ai-aj+ai-aj
//ai-aj+ai-aj>ai-aj+2(at-ak+ak-al) <=>ai-aj>2(at-ak+ak-al)
//맨 위3개의 식으로 하나 더 만들면
//ai-aj+2(at-ak)<2ak-al <=>ai-aj<2(ak-al - at-ak)
//즉 모순된 두 식이 나오므로 임의의 노드에 대하여 가장 먼거리의 노드는 반드시 가장 긴 루트를 가진 노드 쌍중 하나이다.
val leaf=find(route,n,0)
var max=0
var maxidx=0
for(i in leaf.indices){
if(leaf[i]>max){
max=leaf[i]
maxidx=i
}
}
val end1=find(route,n,maxidx)
var cnt=0
max=0
maxidx=0
for(i in end1.indices){
if(end1[i]>max){
max=end1[i]
maxidx=i
cnt=1
}else if(end1[i]==max) ++cnt
}
if(cnt>1) return max
//다시 종단점에서 재탐색하는 이유
//우선 이번에 구한 루트가 가장 긴 루트를 가진 노드쌍인것은 증명함(위에서)
//두 노드쌍중 하나를 포함하는 가장긴 루트가 더 있는지 체크해야함.
//첫번째에선 A,B노드쌍중 A하나만 가지고 체크했으니 B도 체크해야 하는것.
val end2=find(route,n,maxidx)
cnt=0
for(i in end2.indices){
if(end2[i]==max) ++cnt
}
if(cnt>1) return max
else return max-1
}
fun find(route:Array<HashSet<Int>>,n:Int,p:Int):IntArray{
val dist=IntArray(n)
val visited=BooleanArray(n){false}
val q=ArrayDeque<Int>()
q.addLast(p)
visited[p]=true
dist[p]=0
while(q.isNotEmpty()){
val cur=q.removeFirst()
for(i in route[cur]){
if(!visited[i]){
visited[i]=true
q.addLast(i)
dist[i]=dist[cur]+1
}
}
}
return dist
}
}-주석 참고
3. 등대
1)문제
문제 설명
인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.
예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.
등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 2 ≤ n ≤ 100,000
- lighthouse의 길이 = n – 1
- lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
- 1 ≤ a ≠ b ≤ n
- 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.
- lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
2)솔루션
class Solution {
fun solution(n: Int, lighthouse: Array<IntArray>): Int {
var answer: Int = 0
val route=Array(n){HashSet<Int>()}
for(i in lighthouse){
route[i[0]-1]+=i[1]-1
route[i[1]-1]+=i[0]-1
}
//bfs로 계층을 구해서 각 계층별로 dp값을 구함
val q=ArrayDeque<Pair<Int,Int>>() //노드,계층
val hier=Array(n){Pair(0,0)}
val visited=BooleanArray(n){false}
var idx=1
q.addLast(Pair(0,0))
visited[0]=true
while(q.isNotEmpty()){
val (cur,dep)=q.removeFirst()
for(i in route[cur]){
if(!visited[i]){
q.addLast(Pair(i,dep+1))
hier[idx++]=Pair(i,dep+1)
visited[i]=true
}
}
}
val map=HashMap<Int,Int>()
for((i,j) in hier){
map.put(i,j)
}
//하위 계층부터 dp구성
val dp=Array(n){IntArray(2)} // dp[루트노드][1:on 0:off]=최소 라이트수
for(i in hier.size-1 downTo 0){
val (cur,dep) = hier[i]
//dp[cur][0]:꺼져있는경우-자식은 다 켜져있어야함
//dp[cur][1]:하위노드가 꺼져있는 켜져있든 상관없으므로 최솟값들로 더해줌
var sum=0
var sum1=0
var curhier=map[cur] as Int
for(i in route[cur]){
if((map[i] as Int) > curhier){
sum+=minOf(dp[i][0],dp[i][1])
sum1+=dp[i][1]
}
}
dp[cur][1]=sum+1
dp[cur][0]=sum1
}
return minOf(dp[0][0],dp[0][1])
}
}-임의의 노드 하나를 루트노드로 두고 bfs로 탐색을 해서 계층별로 dp를 구함.
-자신이 켜져있으면 자식은 꺼져있든 켜져있든 상관X
-자신이 꺼져있으면 자식은 무조건 켜져있어야 함.=>뱃길 기준 두개중 하나는 켜져있어야 하므로
-위의 조건을 만족하는 dp를 구성해서 루트노드에서의 dp의 최솟값을 구하면 됨
4. 미로 탈출
1)문제
문제 설명
신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다.
위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다.
출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.
- 그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다.
- 방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
- 화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다.
- 화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
- 그림에 표시된 빨간색 방인 2번 방은 함정입니다.
- 함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어있는 모든 길의 방향이 반대가 됩니다.
- 위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다.
- 똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
- 미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다.
- 1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다.
- 함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다.
- 2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다.
- 탈출에 성공했습니다. 총 이동시간은 5입니다.
방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ n ≤ 1,000
- 1 ≤ start ≤ n
- 1 ≤ end ≤ n
- 1 ≤ roads의 행 길이 ≤ 3,000
- roads의 행은 [P, Q, S]로 이루어져 있습니다.
- P에서 Q로 갈 수 있는 길이 있으며, 길을 따라 이동하는데 S만큼 시간이 걸립니다.
- 1 ≤ P ≤ n
- 1 ≤ Q ≤ n
- P ≠ Q
- 1 ≤ S ≤ 3,000
- 서로 다른 두 방 사이에 직접 연결된 길이 여러 개 존재할 수도 있습니다.
- 0 ≤ traps의 길이 ≤ 10
- 1 ≤ traps의 원소 ≤ n
- 시작 방과 도착 방은 함정이 아닙니다.
- 항상 미로를 탈출할 수 있는 경우만 주어집니다.
2)솔루션
class Solution {
fun solution(n: Int, start: Int, end: Int, roads: Array<IntArray>, trap: IntArray): Int {
val road=Array(n+1){ArrayList<IntArray>()} //인덱스는 한쪽 연결점. 배열은 3짜리: 반대연결점, weight, 화살표(1안,0바깥)
for(i in roads){
road[i[0]]+=intArrayOf(i[1],i[2],0)
road[i[1]]+=intArrayOf(i[0],i[2],1)
}
for(i in road){
i.sortBy{it[1]}
}
val traps=HashSet<Int>()
for(i in trap) traps.add(i)
//BFS로 탐색
val q=ArrayDeque<Node>()
val first=Node(start)
for(i in traps){
first.traps.put(i,0)
}
q.addLast(first)
var min=Int.MAX_VALUE
while(q.isNotEmpty()){
val cur=q.removeFirst()
//end에 도달했으면 최솟값갱신
if(cur.n==end) min=minOf(min,cur.total)
//현재위치가 트랩이고 밟은 횟수가 3이면 스킵
if(cur.traps[cur.n]==3) continue
//현재까지 값이 min이상이면 탐색할 필요없음
if(cur.total>=min) continue
//현재 밟은 곳이 한번 밟은 트랩인지 체크-1
//i로 연결된곳이 한번 밟은 트랩인지 체크-2
//해당없으면 정상 진행
//1만 해당되면 화살표 반대것만 타고 감
//2만 해당되면 화살표 반대것을 타고감
//1,2 둘다 해당되면 원래것을 타고 감
//트랩 체크후 추가
val flag1=cur.traps[cur.n]==1
for(i in road[cur.n]){
val flag2=cur.traps[i[0]]?:0 ==1
val node=cur.copy(i[0])
if((flag1&&!flag2)||(flag2&&!flag1)){
if(i[2]==1){
//밟은 곳이 트랩일때 횟수 증가
if(traps.contains(i[0])){
node.traps.put(i[0],node.traps[i[0]] as Int +1)
}
node.total+=i[1]
q.addLast(node)
}
}else{
if(i[2]==0){
//밟은 곳이 트랩일때 횟수 증가
if(traps.contains(i[0])){
node.traps.put(i[0],node.traps[i[0]] as Int +1)
}
node.total+=i[1]
q.addLast(node)
}
}
}
}
return min
}
}
class Node(val n:Int){
val traps=HashMap<Int,Int>()
var total=0
fun copy(m:Int):Node{
val new =Node(m)
new.total=this.total
for((i,j) in this.traps){
new.traps.put(i,j)
}
return new
}
}-각 노드엔 트랩별 밟은 횟수와 움직인 거리 총합을 저장
-시작 지점부터 bfs를 이용하여 탐색
-트랩을 세번밟은 순간부터는 한번 밟았을때와 다를 것이 없으므로 더이상의 탐색이 낭비가 되어 제외
-현재까지의 값이 도착지에 도착한 값들중 최솟값보다 크면 더이상의 탐색이 낭비가 되어 제외
-이동은 현재 위치가 트랩인지, 가려는 위치가 트랩인지 체크해서 이동
5. 가사 검색
1)문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
- words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
- queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
- 검색 키워드는 중복될 수도 있습니다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
- 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
- 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
- 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
2)솔루션
class Solution {
fun solution(words: Array<String>, queries: Array<String>): IntArray {
//words의 각 단어를 정순, 역순으로 두개 집합을 둔다.
//각각 trie에 집어넣음
//앞이 물음표이면 역순 비교, 뒤가 물음표이면 정순 비교
//개수별로 정순 역순 문자열들을 모아둠
//nodes[i][j]:i는 문자 길이, j는 0은 정순, 1은 역순
//자기자리 찾아 내려가면서 1씩 더해 하위트리의 총 단어수를 저장해둠
val nodes=Array(10001){Array(2){Node()}}
for(i in words){
var curNode=nodes[i.length][0]
curNode.total++
for((idx,j) in i.withIndex()){
if(curNode.child.keys.contains(j)){
curNode=curNode.child[j] as Node
curNode.total++
}else{
val node=Node()
curNode.child.put(j,node)
curNode=node
node.total++
}
}
}
for(j in words){
val i=j.reversed()
var curNode=nodes[i.length][1]
curNode.total++
for((idx,j) in i.withIndex()){
if(curNode.child.keys.contains(j)){
curNode=curNode.child[j] as Node
curNode.total++
}else{
val node=Node()
curNode.child.put(j,node)
curNode=node
node.total++
}
}
}
val answer=IntArray(queries.size){0}
//정순, 역순, ????인것으로 구분
for(i in queries.indices){
val q=queries[i]
if(q[0]=='?'){
val r=q.reversed()
answer[i]=match(nodes[r.length][1],r)
}else{
answer[i]=match(nodes[q.length][0],q)
}
}
return answer
}
//정순이면 단어 그대로 넣고 역순이면 뒤집어서 넣기
fun match(head:Node, str:String):Int{
var idx=-1
var cur=head
while(true){
if(str[idx+1]=='?') break
else idx++
}
//물음표로 시작하는 경우는 이과정 생략(idx==0인경우)=>이경우는 전체가 물음표
if(idx!=-1){
for(i in 0..idx){
if(cur.child.keys.contains(str[i])){
cur=cur.child[str[i]] as Node
}else{
return 0
}
}
}
return cur.total
}
}
class Node(){
val child=HashMap<Char,Node>()
var total=0
}
-이 문제에서 사용되는 아이디어는 세 가지
<1>query의 물음표위치가 앞이냐 뒤냐에 따라 달라짐
=>물음표위치가 앞에 있으면 문자열을 뒤집어서 물음표가 뒤로가도록 한 뒤 비교
=>즉, words도 뒤집어서 비교해야함.
<2>query의 길이
=>query와 길이가 같은 word만 비교하면 되므로 words를 길이별로 나누어줌
<3>trie구조
=>참고 자료:https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
[자료구조] 트라이 (Trie)
트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조
velog.io
=>문자열 비교를 할때 trie구조를 사용해서 시간초과를 막아야함.
=>trie에 집어넣으면서 각 노드별로 하위 트리에 단어가 몇개 들어있는지 저장
=>이렇게 하면 탐색할때 물음표가 아닌부분만큼 노드를 타고 내려간 뒤 물음표 부분에 해당하면 단어가 몇개인지 바로 구할 수 있음
>코드카타 리뷰
1. 좌표만 알때 다각형 넓이 구하기
2)BigDecimal
<1>조건: 자바 임포트 필요
<2>용도: 고정 소수점을 사용해서 부동소수점으로 생기는 오류를 원할하게 다루어 낼 수 있음
<3>지원 함수: 산칙연산 뿐만 아니라 반올림, 비교, 스케일 조정 등의 메서드도 제공함
-add(숫자): 더하기
-multiply(숫자):곱하기
-setScale(소수점자리, RoundingMode.속성) : 소수점자리에서 속성에 맞춰 반올림함
-divide(숫자, 소수점자리, RoundingMode.속성): 숫자로 나누고 소수점자리에서 속성에 맞춰 반올림함
-RoundingMode
<1> HALF_UP: 반올림. 반올림하고자 하는 자리가 5면 올림
<2> HALF_DOWN: 반올림. 반올림하고자 하는 자리가 5면 내림
<3> HALF_EVEN: 반올림. 반올림 하고자 하는 자리가 5면 윗자리중 더 가까운 짝수쪽으로 반올림
=>ex) 1.5면 2와 0중 2가 더 가까우므로 2로 반올림. 2.5면 2와 4중 2가 더 가까우므로 2로 반올림
3)입문 과제 해설 강의
-빠르게 스트링리소스를 drawable로 뽑아내는 법: xml상에 적은 스트링에서 전구 표시를 누르고 Extract string resource를 누르면됨
-trim(): 스트링에서 빈 공간 빼주는 기능
-drawable내 string파일에 들어있는 리소스를 코드상에 가져오는법: getString(R.string.아이디)
-코틀린에서 범위로 랜덤 순자 뽑는법: (a..b).random() =>a와 b사이의 값으로 랜덤하게 나옴
-constraintLayout도 gravity넣기 가능
-위젯을 묶어서 움직이기 위해서는 chain을 줘야함: 그러면 여러 위젯을 묶을 수있음
<1>Spread: 사용가능 공간내 일정간격으로 배치됨
<2>Spread Inside:제일 바깥뷰는 가장가리에 나머지는 일정간격으로 배치
<3>packed: 묶어서 중앙에 배치
-chain에는 wieght속성 넣기 가능
-뷰를 버튼처럼 사용하고 그 안에 위젯들을 넣을시 각 위젯별로 selector를 넣을 수 있음: 뷰 클릭시 내부 위젯별로 selector작동
=>이미지뷰나 텍스트뷰도 텍스트 색깔이나 이미지뷰내의 그림등을 클릭여부에 따라 바꿀 수 있음
-selector 속성(속성없이 적은것은 default 상태를 의미)
<1>아무것도 없는 기본상태
ex)<item android:drawable="이미지경로"/>
@drawable은 이미지, color는 텍스트 컬러 등 여러속성 지정 가능
<2>android:state_pressed: 뷰가 눌렸을때-터치나 클릭시
<3>focused:뷰에 포커스가 위치-예를들어 edittext입력을 위해 커서가 깜빡이는 상태
<4>checkable: 체크 가능한 상태-체크박스
<5>checked: 체크된 상태
<6>enabled: 사용가능할때-터치나 클릭 이벤트등을 받을 수 있는 상태
4)git&github강의
-git branch 이름: 이름의 브랜치를 생성
-git branch: 브랜치 목록. 현재 위치한 브랜치가 초록색으로 뜸
@q: end라는 단어가 있는 화면에서 빠져나오기
-git switch(혹은 checkout) 브랜치이름: 브랜치 이동
-git switch -c 브랜치 이름 / git checkout -b 브랜치 이름: 브랜치를 생성하자마자 이동
@a브랜치에서만 짠 코드가 있으면 b브랜치로 이동시 사라짐.(다시 돌아가면 있음)
-git switch 합쳐질 기준 브랜치: 보통 main으로 이동해서 합침
git merge 합칠 브랜치 이름: 합칠 브랜치가 합쳐질 브랜치로 합쳐짐.
=>그런데 이부분은 잘 안씀. 보통 깃헙에서 합침
=>코드 한눈에 비교 후 합칠 수 있기때문
=>pull request이용
-pull request: pull(당기는것. 합침을 의미) request:요청 =>합치는것을 요청함
@commit은 저장 push는 깃헙에 올림
=>base가 최종 합칠 브랜치, compare는 합쳐질 브랜치.
=>create pull request후 코드비교후 된다면 merge를 누르면 합쳐짐
-깃헙에서 합쳤으면 내 코드 작성하는 위치에서 git pull을 해서 가져와 합침
=>git pull origin 내 브랜치 이름
-main브랜치와 기능 브랜치 사이에 develope 브랜치(dev)를 만들음:main은 배포용이므로 다 완성하고 머지해야함
=>기능 별로 완성될때마다 develope에 합치고 최종에 main에 합침
-깃을 올리기 전에 git pull해서 가져와 합쳐 테스트 해보고 충돌같은거 처리한 뒤 push해서 합쳐야함(file changed에서 확인)
-default를 dev로 설정: 왜냐하면 pull request에서 합쳐질때 default브랜치가 기본 베이스로 설정되므로
-리뷰:files changed에서 코드별 +를 눌러 코멘트를 남길수 있고 최종적으로 finish your review를 눌러 끝냄
=>코멘트만 남기는것, 합치기 허용(approve), 코드 바꾸기 요청(request change)가 있음
-충돌처리법(예를 들어 같은 위치에 다른사람과 내가 코드를 짠 경우or 동일 이름의 변수가 여러개가 된 경우)
=>머지하기전에 미리 깃헙에서 git pull origin dev로 가져와 내 기능 브랜치와 합쳐 수정 후 다시 푸시함. 이후 내 dev브랜치에도 git pull로 가져와줌.
'코틀린-안드로이드' 카테고리의 다른 글
| 40일차)알고리즘 문제(2개 이하로 다른 비트), 팀 프로젝트 (0) | 2024.07.03 |
|---|---|
| 39일차)알고리즘 문제(숫자 변환하기), 챌린지반 2회차 강의(OOP설계), 팀프로젝트(입문주차) (0) | 2024.07.02 |
| 37일차)알고리즘 문제(뒤에 있는 큰수) (0) | 2024.06.30 |
| 36일차)알고리즘 문제(모음사전, 안티세포**중요!!) (0) | 2024.06.29 |
| 35일차)알고리즘 문제(주차요금 계산) (0) | 2024.06.28 |