코부캠 연습

24480 - dfs

인접리스트 꼴로 사용하는 거 까먹음
그래프 n by n 비워놓고 삽입
미방문 노드의 처리 고민

1트) 런타임에러
재귀함수는 런타임에러가 자주 나므로 sys.setrecursionlimit(10**8) 써줘야 함

dfs는 몇 번을 해도 익숙해지지가 않는구먼

---

24444 - bfs

bfs가 최고야

---

7562 - 나이트 이동

현재 위치 - 다음 위치
최소 몇 번의 이동이 필요한가?
나이트 가능한 이동
dx = [1,1, 2,2, -1,-1, -2, -2]
dy = [2,-2, 1, -1, 2, -2, 1,-1]
총 8방향
q.pop 방향으로 간다.
아이디어) 도착한 다음 좌표가 이전좌표 거리보다 작아지는 조건만 탐색
초기 00 -> 70 거리제곱 49
다음 12 -> 70 40
다음 -2-1 -> 82 안감
거기에 방문한 체스 보드에 깊이정보까지 한 번에 queue에 저장해주기

풀어보고 나니 짧은 거리만 갈 필요가 없었다. 이미 이동한 다음 좌표가 같으면 깊이를 출력하고 종료하는 조건문에서 검사되기 때문에..
나이트 방향에 맞춰 이동 + 체스보드 범위 안 + not visited 로 충분했던 것이다.
또 뻘짓했다.

from collections import deque
import math
import sys
input = sys.stdin.readline

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


def bfs(x, y, fx, fy):
    cnt = 0
    q = deque([])
    q.append([x, y, 0])
    v[x][y] = True
    while q:
        cx, cy, steps = q.popleft()
        if cx == fx and cy == fy:
            print(steps)
            return
        for dir in range(8):
            nx, ny = cx+dx[dir], cy+dy[dir]
            if 0 <= nx < l and 0 <= ny < l and not v[nx][ny]:
                v[nx][ny] = True
                q.append([nx, ny, steps + 1])


n = int(input())
for _ in range(n):
    l = int(input())
    ix, iy = map(int, input().split())
    fx, fy = map(int, input().split())

    v = [[False] * (l) for _ in range(l)]

    if ix == fx and iy == fy:
        print(0)
    else:
        bfs(ix, iy, fx, fy)

6137 - 문자열 생성

투포인터 쓰는 문제
투포인터는 또 뭔데

투포인터 연습 문제도 몇 개 풀어보자.

ACDBCB
아이디어 - 펠린드롬
1) 양 끝에서 부터 l, r 다가옴
l과 r이 다르다 = 아스코드 값 중 작은 값을 T에 삽입, 삽입한 부분을 업데이트 (l이면 +1 r이면 -1)
2) 같다 = 두 값이 달라지는 부분까지 탐색 = 달라진다 = 아스키코드 값 중 작은 값을 T에 삽입, 삽잆한 값 업데이트

투 포인터 구현 능력 부족 다른 문제 풀어보기

import sys
input = sys.stdin.readline


def build_string(s):
    l, r = 0, len(s) - 1  # 출발값
    T = []

    while l <= r:  # 좌우 값이 다를 때

        if s[l] != s[r]:
            if s[l] < s[r]:  # 파이썬은 문자열 간의 비교도 가능하다
                T.append(s[l])
                l += 1
            else:
                T.append(s[r])
                r -= 1

        else:
            temp_l, temp_r = l, r
            while temp_l < temp_r and s[temp_l] == s[temp_r]:  # 다를 때까지 찾기
                temp_l += 1
                temp_r -= 1

            if temp_l >= temp_r or s[temp_l] < s[temp_r]:
                T.append(s[l])
                l += 1
            else:
                T.append(s[r])
                r -= 1
    return ''.join(T)


n = int(input())
s = [input().strip() for _ in range(n)]
s = ''.join(s)
result = build_string(s)
# 출력하기 (80글자마다 줄 바꿈)
for i in range(0, len(result), 80):
    print(''.join(result[i:i+80]))