CareTim

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

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

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로 변환하면 아스키코드값이 나오게 된다. 

백트래킹(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의 배낭알고리즘과 다익스트라를 합쳐서 사용하면 속도 향상을 할 수 있지 않을까라는 생각을 해봤다.  

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

풀이

주어지는 그래프를 깊은 복사* (참조가 아니라 메모리에 새로 저장)하여  복사한 그래프를 리턴하면 되는 문제이다.

사실 문제를보고 간단하게  deepcopy 함수를 사용하면 바로 풀릴거라 생각했지만 ㅋㅋ 그래프를 탐색해서 풀라는 문제이니  deuqe을  사용해서 딕셔너리로 방문한 리스트 기록하며  bfs탐색을 했다.

1. 주어지는 첫 노드를 deque에 넣는다..

2.deque가 완전히 비워질 때 까지 while을 순회하며 bfs 탐색을한다.

3. cur을 통해 큐에 들어온 원소들을 뽑아서 인접한 노드를 탐색한다.

4.만약 딕셔너리에 현재 돌고있는 이웃 노드를  방문을 안했다면 딕셔너리 노드에 현재 인덱스 dict[cur]에 노드 생성,

-> neighbors에 인접한 노드의 딕셔너리 인덱스를 넣어준다, (딕셔너리를 통해 각 노드인덱스를 모두 방문할 때 까지 갱신)

5.최초 방문이라면 큐에 다시 넣어준다.

5. 방문을 했다면 딕셔너리의 해당 인접노드의 딕셔너리 인덱스의 값을 현재 노드의 딕셔너리의 이웃으로 재갱신 해준다.

from collections import deque
class Solution(object):
    def cloneGraph(self, node):
        if node == None:
            return 
        q = deque()
        visit = dict()
        visit[node.val]= Node(val=node.val)
        q.append(node)
        while q:
            cur=q.popleft()
            for i in cur.neighbors:
                if i.val not in visit:
                    visit[i.val]=Node(i.val)
                    q.append(i)
                visit[cur.val].neighbors.append(visit[i.val])

        return visit[node.val]

처음에 문제를 제대로 이해 못하고, 기존 node클래스에 neighbors속성이 리스트로 구성되어 있는줄 알고 리스트로 계속 넣으려고 하다가 실패했다. 

            for i in cur.neighbors:
                if i.val not in visit:
                    visit[i.val]=Node(i.neighbors)
                visit[node.val].neighbors.append(visit[i.val].neighbors)
        return visit[node.val]

백준으로 문제를 풀 때는 각 리스트를 변수에 저장해서 사용하기에 쉽게 느껴졌는데, 클래스를 통해 문제를 풀려고하니 좀 헤멨던 것 같다.  

다른사람의 코드 

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return
        d = {node: Node(node.val)}
        stack = [node]
        while stack:
            curNode = stack.pop()
            for nei in curNode.neighbors:
                if nei not in d:
                    d[nei] = Node(nei.val)
                    stack.append(nei)
                d[nei].neighbors.append(d[curNode])
        return d[node]

dfs로 깊이탐색을 진행하며, 방법은 동일한다, 순서가 상관없기에 bfs든 dfs던 그래프를 모두 탐색하여 값을 찾아오면 된다.  

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

풀이

알파벳으로  이루어진 2차원 리스트가 주어지고  단어의 배열이 주어진다,

배열안에 존재하는 단어를 리스트에 담아서 제출하면 된다.

방법

트라이트리(trietree) 자료구조를 활용해서 단어를 넣은 트라이트리를 만들고 매트리스마다 y,x축으로 나누어 dfs로 2차원리스트를 탐색해 어떤 단어들이 존재하는지 찾는다. 

class Node:
    def __init__(self):
        self.children={}
        self.endof =0

class Trie(object):
    def __init__(self):
        self.root = Node()
    def insert(self, word): # 노드 삽입, 딕셔너리로 존재하지않는다면 생성, 존재한다면 추가 
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = Node()
            node= node.children[i] 
        node.endof =1   # 완성문자열



class Solution(object):
    def findWords(self, board, words):
        self.result = []
        trie = Trie() # trieTree 생성
        node = trie.root
        for i in words: # 트라이트리에 단어 삽입
            trie.insert(i)
        for y in range(len(board)):
            for x in range(len(board[0])):
                self.search(node,board,y,x,"")
    def search(self,node,board,y,x,temp):
        dy,dx = [0,0,1,-1],[1,-1,0,0]
        if node.endof: # 현재 완성된 단어라면 tmep result에 추가 
            self.result.append(temp)
            node.endof = 0 #방문체크 
            if not node: 
                return
        if 0>y>=len(board) or 0>x>=len(board[0]): #범위체크
            return
        char = board[y][x] # 현재 위치의 문자열 확인
        if char not in node.children: # 현재 노드의 해시맵에 없다면 리턴
            return
        node = node.children[char] #node 현재 char의 인덱스로 변경
        for i in range(4): # ny,nx재지정 상하좌우
            ny,nx = y+dy[i],x+dx[i]
            self.search(node,board,ny,nx,temp+char) # 재귀적으로 탐색

오류나서 생긴 문제

1.board의 방문리스트를 사용하지 않아서 최초에 오류가 났었는데 ( 왔던 경로 재방문) , 이걸 위해 board를 '*'문자열로 바꿨다가 findword의 2차원탐색에서 다른 위치에서 시작할 때 오류 발생,  변경된 문자열로 새로 찾을 수 없음

   -> search의 for문으로 ny,nx 변경시에만 값 변경

2.시간초과

모든 경로를 2차원리스트에서 dfs로 모두 찾으려하니 시간이 초과됨