CareTim

다낭에서 가족들이 돌아가고나서 베트남 다낭 →라오스 비엔티안 방비엔 -> 태국 우돈타니→치앙마이로 육로 이동을 하기로 결정했다 방비엔에서 조금 길게 있으려했지만 태국 송크란축제가 9일정도 남아서  라오스에 일주일 정도 머물고 태국으로 이동하는 계획을 세우고 다낭에서 라오스로 이동하는 버스를 찾음

Hoàng Nguyệt tourist이라는 여행사를 통해 라오스 비엔티안으로 이동할 수 있다는걸 알고 리셉션에 부탁해서 예약했다. https://maps.app.goo.gl/y6L8X4Rp1sFx46kX7

이 여행사 주소의 맞은편에 요 간판이 있고 옆에서 버스가 대기하고 있다

다낭에서 라오스 팍세, 사바나캣, 비엔티안 세 곳을 갈 수 있고  나는 비엔티안으로 가는 버스를 예약
비용은 100만동 + 셔틀 픽업 10만동(승용차로 데리러옴)

셔틀 픽업에 안좋은 기억이 있어서 픽업을 안받으려 했는데 리셉션이 그랩이랑 가는 비용 비슷하다고 강력하게 주장해서 탄다고 했다.


아침 일찍 체크아웃해서 조식을 못먹어서
아침 6시30분에 온다했는데 역시나 데리러 온 시간은 7시 30분이었음 ㅎㅎ... 이럴거면 조식 먹고왔지 🤔
(대신 호텔직원분이 이른아침에 체크아웃하니까 조식 대신 밀박스 챙겨주심굳  👍)

버스는 아침 8시 30분부터 탑승 가능했고 일찍온다고 자리를 맡거나 그런거 없으니 다른 여행자분은 조식 드시고  픽업서비스 말고 인드라이브 택시 예약해서 오시는걸 추천해요 미케비치에서 20분정도 걸리고 인드라이브 기준 8만동에 탈 수 있을듯

와서 가만히 지켜보니 전화로 예약안하고 직접 아침에 와서 매표소에서 표를 구매하시는분들도 있었어요

버스 아래 트렁크에는 라오스로 가는 수화물들이 들어가고 맨 위에 승객들의 캐리어와 가방들을 쌓고 방수천 비 안맞게 막는듯

좌석은 다행히 넓었다 슬리핑버스를 타다보면 좌석이 짧아서 다리를 못뻗는 버스가 있는데 (내 키 179) 요 버스는 좌석이 넓어서 다리를 뻗고 갈 수 있음

주어지는 문장의 알파벳이 중복되지 않게 나오도록 코드를 만들면 되는 문제이다.

중복된 알파벳이 아니라면 출력문제에 순서대로 삽입시켜주면 된다. 

ex ) 입력 aabbcc ,출력 - >abc  

fun main() {
    var visited = BooleanArray(26) { false }
    val n = readLine()!!.toInt()
    var result = ""
    for (i in 0 until n){
        var word = readLine()!!.replace(" ","")
        for (j in word){
            var k = j.toInt()
            if (visited[k-65] == false){
                result+=j
                visited[k-65]=true
            }


        }
    }
    println(result)
}

입력
13
CITADEL POPPY
H O O U A L I
ARROW MASSAGE
S S N B S C L
SHOULDER BARD
I   O R T T
SQUEAL FRIEZE
  N D A O   X
FILE CLAPTRAP
E U J T I A L
VACCINE CARGO
E K V R A E D
RHYME SPLURGE


출력
CITADELPOYHURWMSGNBQFZXJVK

파이썬의 ord함수와 동일한 함수가 존재하느니 찾아봤지만 코틀린에서는 char의 클래스타입을 가지고있는 데이터를 Int로 변환하면 아스키코드값이 나오게 된다. 

전역변수와 지역변수

전역변수 코드 내에 모든부분에서 사용 가능한 함수

지역변수 일정한 지역 안에서만 사용 가능한 변수

package section2
//전역변수 a,b 선언
var b=1
var a=2


fun main(){
    // input 한줄로 입력을 받고 널이라면 1 반환 , 널이 아니라면 정수로 변환
//    var input =readLine()?.toInt() ?:1
//    var result = 0f
//
//    // 입력받은 인풋많큼 숫자 받기
//    for (i in 0..input){
//        var n = readLine()!!.toFloat()
//        result += n
//    }
//    println(result)
    //지역변수1
    var a =30
//    print(aver(1f,2f,3f,4f,5f))
    ///지역함수 main -  v 함수 선언 후 a를 1 증가시켰을때
    fun v(){  
       
        ++a main 안에서 선연된 //지역변수 a  +1 증가
    }
    v()
  
    //지역변수 a 가31로 증가된 값이 프린트 됨 
    print(a)
    print(b)
}


//최상위 함수 aver에서 a를 증가시킬때 전역변수 a가 증가된걸 알 수 있음
fun aver(vararg numbers:Float):Float{
    //전역변수 a 증가
    a+=1
    var result = 0f
    for (num in numbers){
        println(num)
        result += num}
    println("result = ${result} / ${numbers.size})")
    result = result/numbers.size

    return result
}

백트래킹(Backtracking)은 해결책을 찾기 위해 모든 가능한 경우를 탐색하면서 해를 찾는 알고리즘 기법
완전탐색과 유사하지만 , 백트래킹은 불필요한 탐색을 줄이기 위해 재귀적으로 시행되며 조건에 따라 
시행 가능한 상태의 후보군과 시행 불가능한 후보군을 확인하여 시행 가능한 후보군만 탐색을 하며 현재 상태에서 가능한 모든 탐색지를 
탐색했다면 이전 상태로 돌아가 다음 시행 가능 후보군을 탐색한다.  

재귀적으로 가능한 후보군을 탐색하여 최종적으로 해결책을 찾아가는 알고리즘 

백트래킹이 알고리즘은 일반적으로 재귀 함수를 사용하여 구현-> 코드의 일반화를 통해 가독성 상승
하지만 재귀함수를 사용하면서 시간복잡도 지수시간을 가지게되어 최적의 해결책을 찾는데 효과적이지 않을 수 있음

가능한 불필요한 탐색을 줄이는 방법을 찾아내어 시간복잡도를 최적화 하는게 중요하다

백트래킹 문제

백준 15649 n과m(1) 문제  https://www.acmicpc.net/problem/15649

stack = []
def backtraking(m):
    if len(stack)==m:
        print(' '.join(map(str,stack))) # 현재 함수 종료조건 - 문제의 최대 길이 도달시 
        return
    for i in range(1,n+1):  
        if i not in stack:   #현재 값이 스택에 안들어가 있다면, 값 추가 후 재귀적으로 탐색시행
            stack.append(i)
            backtraking(m)   
            stack.pop()

n,m = map(int,input().split())
backtraking(m)

진행 가능한 모든 경우의 수를 모두 시행하며 문제의 조건인 m 도달시 현재 스택의 값을 프린트해준다.

백준 30242 N-Queen (eazy) https://www.acmicpc.net/problem/30242

n = int(input())

visited = list(map(int,input().split()))


diag1 = set()#왼쪽 대각선
diag2 = set()# 오른쪽 대각선
for i in range(len(visited)):
    if visited[i]!=0:
        diag1.add(i+visited[i])
        diag2.add(i-visited[i])

#퀸 대각선 움직임 체크를 어떻게할까
#행에 존재한다면 진행 못하고, 위에서부터 아래로 진행함,
# 왼쪽 대각선 (-1,-1) # 오른쪽 대각선 (-1,1)
#  왼쪽 대각선은 x+y를의 열 , 오른쪽 대각선은 x-y의 열

def queen(now):
    if now ==n:
        print(*visited)
        exit() # 마지막 도달 종료조건
    if visited[now]!=0: #해당 이미 queen 있을 경우
        queen(now+1)
    else: # 해당 행에 퀸이 없을 경우 
        for i in range(n+1):
            if i in visited or (now+i) in diag1 or (now-i)  in diag2: #가지치기 조건
                continue # 같은 열에 퀸이 존재여부, 왼쪽대각선, 오른쪽 대각선 퀸 여부
            diag1.add(now+i) # 왼쪽 대각선 추가
            diag2.add(now-i) # 오른쪽 대각선 추가 
            visited[now]=i # 열에 퀸 위치 추가 
            queen(now+1) # 재귀함수 시행 종료 후 입력 조건 철회
            visited[now]=0
            diag1.remove(now+i)
            diag2.remove(now-i)
        
queen(0)
print(-1)

대각선 퀸 체크는 set을 통해 조회하여 O(n)의 시간복잡도를 가지게하여 퀸의 같은 열에 존재 여부, 대각선  존재 여부를 기준으로 가지치기하여 문제를 해결하였다.

문제 링크  - https://www.acmicpc.net/problem/1202

처음엔 배낭알고리즘 문제로 생각했으나 조건에 가방에 들어갈 수 있는 보석의 수는 최대 1개인걸 알고 그리디하게 풀면 되는 문제로 파악했다. (조건 최대 30만개 가방 c의 개수가 최대 1억개 , 제한시간 1초 - > dp활용 배낭알고리즘으로 풀게되면 시간초과 예상)

생각

1.보석은 무게 기준으로 정렬, 가방도 크기 기준으로 정렬 , 

2.가방들을 하나씩 순회하며 가방보다 적거나 같은 무게를 가진 보석들 중 가치가 가장 큰 보석 담기

3, 보석의 중복을 막기 위해 가방에 담긴 보석의 가치를 0으로 변경

4.가방의 무게 이하로 포함된다면 무게값은 필요가 없고, 가치가 가장 높은것만 고르면 됨

최초코드

10퍼센트에서 틀림

반례

4 4
1 100
10 500
13 300
2 200
13
13
13
13

-> 인덱스를 변수 now가 문제였다 보석 마지막까지 다 순회하고 보석을 values에 모두 넣었다면 더 이상 for문으로 순회하지 말아야하는데 계속해서 마지막 보석을 values에 넣어줘서 문제가 보석값이 복사가 되었다.

import sys
import heapq
input= sys.stdin.readline

n,k =map(int,input().split())

#각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
#보석은 무게 Mi와 가격 Vi
jewel = [list(map(int,input().split())) for __ in range(n)]
#가방 중복판매 방지 -> 가방에 담은 보석의 가치 0으로 변경 
bags = []

for __  in range(k):
    bags.append(int(input().rstrip()))

jewel.sort()
bags.sort()

values= [] #가치가 제일 큰 보석만 뽑으면 됨 

now = 0
flag= 0
result = 0

for bw in bags:
    for i in range(now,len(jewel)):# 틀리는 부분이 여기일거같은데
        if flag: # for문 모두 순회했다면 플래그 설정
            break
        if jewel[i][0]<=bw:
            heapq.heappush(values,-jewel[i][1])
            if i == len(jewel)-1:
                flag=1
        else:
            break
    now = i #가방 범위 이내의 인덱스 모두 방문해야함 
    if values: # 0개일떄 인덱스 오류 발생
        result-=heapq.heappop(values)

print(result)

보석을 모두 순회했다면 flag True로 만들어서 더이상 보석을 추가하지 않게 만들었다.

flag 사용말고도 wihle문이나 큐를 통해 원소를 제거하게 만들어도 괜찮을것같다

문제 링크 - https://www.acmicpc.net/problem/1520

그래프탐색과 방문리스트를 담아서 쓰면 간단하게 풀릴거라 생각했다.

최초코드 (틀림)

노드를 탐색하며 지나온 좌표를 리스트에 담아서 종점에 도착하거나 , 이미 지나간 경로의 노드를 방문하면 갖고 있던 배열의 좌표에 가중치를 적용한다.

https://www.acmicpc.net/problem/1520
import sys
from collections import deque
input= sys.stdin.readline
from copy import deepcopy 

dy,dx= [0,0,1,-1],[1,-1,0,0]

n,m = map(int,input().split())
 # 중첩되는 경로 도착시, 이미 진행한 경로를 또 지나가면서 탐색함 - > 시간초과
 # 각 좌표에 도착하는 노드를 모두 체크 후 각 노드에 모두 추가하기

matrix = [list(map(int,input().split())) for __ in range(n)]
dp = [[0]*(m) for __ in range(n)]


def check_point(path_matrix):
     for py,px in path_matrix: # 경로 도달시 패스노드 체크
        dp[py][px]+=1
    
def dfs(sy,sx):
    result = 0
    stack = []
    stack.append(((sy,sx,[])))
    while stack:
        y,x,path_matrix = stack.pop()
        for i in range(4):
            ny,nx = y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and matrix[ny][nx]<matrix[y][x]:
                if (ny,nx) == (n-1,m-1):
                    check_point(path_matrix)
                    result+=1
                    continue
                elif dp[ny][nx]>0:
                    check_point(path_matrix)
                    result+=dp[ny][nx]
                    continue
                next_path = deepcopy(path_matrix)
                next_path.append((ny,nx))
                stack.append((ny,nx,next_path))
    return result
print(dfs(0,0))

경우의 수가 작은범위에서는 맞았지만 분기가 많은 테스트케이스의 경우에서 값이 달랐다.

ex)

2 18
98 91 89 80 76 74 65 58 50 49 44 32 26 23 17 15 14 8
95 91 83 82 70 67 65 55 54 50 41 27 22 20 14 10 7 3

왜인지 생각을 해보니 check_point의 함수에서 값을 1씩 추가해서 문제가 되었다. 현재 도착해서 체크포인트함수에 들어가는 현재노드를 도착할 수 있는 경우의 수를 더해줘야하는데 단순하게 한번 방문하니 1 추가해야지 해서 답이 다르게 나왔다 이후에 변경한 check_point함수

def check_point(path_matrix,padd):
    for py,px in path_matrix: # 경로 도달시 패스노드 체크
       dp[py][px]+=padd # 지나온 경로에 현재 도달 할 수 있는 분기 더해주기

코드 변경 후 테스트케이스의 답은 모두 맞았지만 백준 ac에서 40%쯤 시간 초과가 나왔다,

이유는 check_point함수를 for문으로 순회하며 각 노드에 방문값을 계속해서 추가해주는데,  각 좌표에서 범위가 넓어지고 분기가 달라질 수록 경우의수가 커지면 기하급수적으로 방문범위가 넓어지고 중복해서 방문해서 연산횟수가 늘어난다.

-> 방문리스트를 갖고 탐색하지말고 방문시 실시간으로 방문횟수 갱신하기

#  # 중첩되는 경로 도착시, 이미 진행한 경로를 또 지나가면서 탐색함,
#  # 경로중 분기점일떄 , 분리되어 도착하는 경로 수만 세어서 도착시
#  # 현재 도달가능 경로수 * 도착지점 도달 가능 경로수

import sys
import heapq
input= sys.stdin.readline
from copy import deepcopy 

dy,dx= [0,0,1,-1],[1,-1,0,0]

n,m = map(int,input().split())


matrix = [list(map(int,input().split())) for __ in range(n)]

visited = [[0] * m for __ in range(n)]

def bfs(sy,sx):
    q =[]
    heapq.heappush(q,(-matrix[sy][sx],sy,sx))
    visited[sy][sx]=1
    while q:
        now,y,x =heapq.heappop(q)
        for i in range(4):
            ny,nx = y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and matrix[ny][nx]<matrix[y][x]:
                if visited[ny][nx]==0:
                    heapq.heappush(q,(-matrix[ny][nx], ny, nx))
                visited[ny][nx] += visited[y][x]
bfs(0,0)
print(visited)
print(visited[n-1][m-1])

1.시작점에서부터 큰 값을 가지고 작은 값을 탐색해야 하기에 출발 시 제일 큰 값을 가지게 된다.

2. 이를 활용해서 최대힙을 사용하여 제일 큰 값부터 낮은 값으로 내려가며 탐색하기, 

3. 현재 진행 가능한 좌표들중 가장 큰 값을 먼저 진행하여 내림차순으로 탐색을 진행하게 된다, 

4. 이미 지나간 경로를 방문하게 된다면 현재 노드의 분기횟수 +  지나간 노드의 분기횟수를 더해주며 visited값 갱신

5. n-1,m-1 마지막지점에 지나갈 수 있는 경로의 수 리턴

조건

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

1번과 N번집의 색이 달라하여 인접한 집끼리는 같은 색을 가지면 안된다.

문제 생각

1번 집의 색을 정함으로써 1번집의 비용과 마지막 집의 비용 범위 (첫번째 집 비용 제외 나머지 두개)를 결정하게 된다

1.첫집의 최소 비용을 결정 한 후 각 분기별로 최소 비용값 탐색하기 , 

 최선인지 확인하며 분기탐색하기  (n번값 선택시 나눠지는 분기값 + 그다음분기값) 

각 범위의 값을 탐색하며 최소값 구하기 

각 집의 색 범위 안에서 최소값 갱신하며 첫 집을 선택분기로 최소값 구하기

import sys
input =sys.stdin.readline

INF = 400000000
n= int(input())

color_values = [list(map(int,input().split())) for __ in range(n)]


#시작과 끝은 색이 달라야한다.
#각 노드의 인접노드와 색이 달라야한다.

# 시작점과 끝점 값 비교해서 시작값 끝값 절대값으로 결정
# 중간노드 선택 분기 나눠서 가기?
# last_n = {1:[0,2], 2:[1,0],0:[1,2]}

result=INF
for i in range(3):
    dp = [[INF,INF,INF] for __ in range(n)]
    dp[0][i] = color_values[0][i]
    for j in range(1,n):
        dp[j][0] = min(dp[j-1][1],dp[j-1][2]) +color_values[j][0]
        dp[j][1] = min(dp[j-1][0],dp[j-1][2]) +color_values[j][1]
        dp[j][2] = min(dp[j-1][1],dp[j-1][0]) +color_values[j][2]
    dp[j][i] =INF
    curMin  = min(dp[n-1])
    result = min(result,curMin)
print(result)

첫집을 정한 후 진행 가능한 분기에서 최소값 갱신 (첫 출발 집 외의 출발지는 INF값 지정)

최소 값을 갱신하며 INF값의 경로로 들어온 값들은 저절로 걸러지게 된다.

마지막집에서 첫집과 같은 색이면 안되기에 처음엔 딕셔너리로 i값에 따라 결정값을 변경하려했다.

다른 사람의 코드를 보고 그냥 간단하게 INF처리를 하게되면 저절로 필터링된다는것을 알고 INF로 처리했다.

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

#풀이

그래프 탐색을 통해서 최단거리를 구하는 문제이다. 다익스트라랑 bfs로 각각 한번씩 풀어봤다.

1. visit을 통해서 방문한 곳을 체크한다, (bfs 방문확인, dijkstra 이동횟수 체크)

2. 주사위로 1,2,3,4,5,6을 굴려서 이동한다 (bfs 방문했다면 pass , dijkstra 방문했어도, 이동횟수가 기록보다 적다면 이동)

3. 현재 위치가 마지막 위치 (n*n) 위치인지 확인한다.  -> 마지막 위치라면 return 

dijkstra는 heapq을 사용해 우선순위(이동횟수)를 두고 탐색하게 했다. 하지만 이 문제에서는 각각의 이동거리가 비슷하고 ,각각 선형으로 이동하는거리가 대부분 동일하게 1로 움직이기에 생각보다 탐색속도가 빠르지 않았다.

반대로 bfs는 넓이탐색을 통해서  이미 방문했던 곳이라면, 본인보다 이동횟수가 적은게 확실하기에 모든 이동경로를 1번 이상 방문하지 않기에 다익스트라보다 비교적 빠르게 탐색이 가능했다. 

Dijkstra

import heapq
import sys
INF = sys.maxsize
class Solution(object):
    def snakesAndLadders(self, board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        visit = [INF] *((n**2)+1)
        visit[1]=0
        q= []
        heapq.heappush(q,(0,1))
        while q:
            move,cur = heapq.heappop(q)
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!= -1:
                    next = line[next]
                if next <(n**2) and visit[next]>move+1:
                    visit[next]=move+1
                    heapq.heappush(q,(move+1,next))
                    # print(move,next)
                if next == (n**2):
                    return move+1
        return -1

BFS

from collections import deque

class Solution(object):
    def snakesAndLadders(board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        print(line)
        visit =[0]*((n**2)+1)
        visit[1]=1
        q= deque()
        q.append((0,1))
        while q:
            move,cur = q.popleft()
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!=-1:
                    next = line[next]
                if visit[next] ==0:
                    visit[next] = move+1
                    q.append((move+1,next))
                    print(next)
                if n**2 == next:
                    return move+1

        return -1


    
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

print(Solution.snakesAndLadders(board))

bfs는 방문 리스트를 통해 방문처리하게 되면 방문하지않는다,  반면 다익스트라는 방문을하고나서, 다음에 들어오는 방문인자가 횟수가 적다면 다시 방문처리를 한 후 이동을 하게된다,  dp의 배낭알고리즘과 다익스트라를 합쳐서 사용하면 속도 향상을 할 수 있지 않을까라는 생각을 해봤다.