• CSRF 공격을 막기 위한 방법
  • CSRF 토큰이란 다른 사이트에서 접근할 수 없는 특정 사이트에 고유한 비밀값이라고 보면 된다.
  • Django에서는 CsrfViewMiddleware에 의해 설정된다.
  • 원래는 form태그에서 {% csrf_token %} 태그를 설정
{% csrf_token %}
  • 해당 태그가 존재하는 페이지에 접속하게 되면 csrf_token이 쿠키에 추가되는것을 볼 수 있다.
  • CsrfViewMiddleware에서는 먼저, POST에 있는 csrfmiddlewaretoken을 찾고, 없다면 X-csrftoken을 찾는다.
  • X-CSRFToken의 경우는 Ajax 등 api에서 사용된다.

과정


  1. response에 set_cookie를 설정하여 csrf_token 쿠키를 넣어서 전달한다.
  2. request에서는 전달받은 csrf_token을 POST의 csrfmiddlewaretoken에 넣어서 전달하거나, 아니면 헤더에 추가한다. ⇒ X-CSRFToken에 넣어서 전달
  3. 서버에서는 쿠키에 존재하는 csrf_token의 값하고 csrfmiddlewaretoken이나 X-CSRFToken의 값을 비교하는 방식으로 진행한다.

관련 데코레이터


  • ensure_csrf_cookie 데코레이터 추가
    • csrf_token set-cookie 추가
@method_decorator(ensure_csrf_cookie)
def post(self, request, *args, **kwargs):
  • csrf_protect 데코레이터 추가
    • csrf_token 인증 진행
@method_decorator(csrf_protect)
def post(self, request, format=None):

'프레임워크 > Django' 카테고리의 다른 글

[ Django ] Q, F object  (0) 2021.10.20
[ Django ] Session  (0) 2021.10.17
[ Django ] JWT(djangorestframework-simplejwt)  (0) 2021.10.15
[ Django ] JWT  (0) 2021.10.14
[ Django ] Choice  (0) 2021.09.15

https://www.acmicpc.net/problem/22865

 

22865번: 가장 먼 곳

$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할

www.acmicpc.net


풀이 과정


  1. A지점, B지점, C지점에서 시작해서 다익스트라 알고리즘 적용
    • 그러면.. A지점에서 각 지점까지의 거리, B 지점에서 각 지점까지의 거리, C 지점에서 각 지점까지의 거리가 따로 나오게 된다.
  2. 각각의 지점에서 A지점, B지점, C지점까지의 거리의 최솟값을 구한다.
    1. A, B, C를 다익스트라 알고리즘으로 구해진 거리, A[i]는 A지점에서 i지점까지의 거리
    2. 예시로 2번 지점이라고 할때, min(A[2], B[2], C[2])를 해주면 된다.
  3. (2)의 최댓값이 나올 때의 지점 번호를 구해서 출력해주면 된다. 지점 번호의 경우 최솟값이 같은 경우 번호가 작은걸 출력해주라 하였으므로 지점 번호를을 왼쪽(1)에서 오른쪽(n)으로 진행하면서 갱신한다.

소스 코드


 

import sys
import heapq

input = lambda : sys.stdin.readline().rstrip()

N = int(input())
A, B, C = map(int, input().split())

graph = [[] for _ in range(N+1)]
M = int(input())

for _ in range(M):
    D, E, L = map(int, input().split())
    graph[D].append([E, L])
    graph[E].append([D, L])

def dijkstra(graph, start):
    INT_MAX = int(10e9)
    distance = [INT_MAX] * len(graph)
    distance[start] = 0
    heap = [[0, start]]
    while heap:
        dist, node = heapq.heappop(heap)
        if distance[node] != dist:
            continue

        for next_node, next_dist in graph[node]:
            if dist + next_dist < distance[next_node]:
                distance[next_node] = dist + next_dist
                heapq.heappush(heap, [distance[next_node], next_node])

    return distance

max_size = 0
answer = 0
dist_a = dijkstra(graph, A)
dist_b = dijkstra(graph, B)
dist_c = dijkstra(graph, C)

for i in range(1, N+1):
    if max_size < min(dist_a[i], dist_b[i], dist_c[i]):
        max_size = min(dist_a[i], dist_b[i], dist_c[i])
        answer = i
        
print(answer)
  • 이전에는 DjangoRestFramework-jwt를 사용하였으나, 찾아보니 DjangoRestFramework-jwt가 더이상 업데이트 되지 않으며, simplejwt 사용이 권장되고 있다고 함.

설치


# 구버전 ㅂㅇ..
pip uninstall djangorestframework-jwt

# 신버전 ㅎㅇ~ 
pip install djangorestframework-simplejwt

Settings.py 설정


  • INSTALLED_APPS에 추가
INSTALLED_APPS = [
    ...
    'rest_framework_simplejwt',
    ...
]
  • 인증방식에 JWTAuthentication 추가
REST_FRAMEWORK = {
    ...
    'DEFAULT_AUTHENTICATION_CLASSES': (
        ...
        'rest_framework_simplejwt.authentication.JWTAuthentication',
    )
    ...
}

urls.py 설정


  • TokenObtainPairView

    • POST 방식의 API
    • username, password를 넘겨주면 만약 사용자 인증이 된다면 토큰 발급
    • 기존 djangorestframework_jwt와 다르게 refresh, access 토큰이 따로 발급된다.
  • TokenRefreshView

    • POST 방식의 API
    • refresh 토큰을 넘겨주면 새로운 토큰을 발급받음.(access 토큰)
  • 여기서, 실제로 우리가 사용하게 될 토큰은 access 토큰이라고 보면 된다.

from rest_framework_simplejwt.views import (
    TokenObtainPairView,
    TokenRefreshView,
)

urlpatterns = [
    ...
        path('apitokenauth/', TokenObtainPairView.as_view()),
    path('apitokenrefresh/', TokenRefreshView.as_view()),
    ...
]

쿠키 설정


  • 사용자 브라우저로 하여금 쿠키를 설정하게 하기 위해선 Set-cookie 헤더를 넘겨주어야 한다.
  • response의 set_cookie 메서드를 사용하여 쿠키를 설정해 준다.
  • 예제에서는 쿠키의 키를 'JWT'로 설정하였으며 httponly를 설정하여 Script에서는 읽지 못하도록 하였음.
class TokenObtainPairView_ud(TokenObtainPairView):
    def post(self, request, *args, **kwargs):
        response = super().post(request, *args, **kwargs)
        if response.status_code != 200:
            return response

        response.set_cookie(
            key = 'JWT',
            value = response.data['access'],
            max_age = 300,
            httponly = True,
            samesite = 'Lax'
        )
        return response

# urls.py는 아래로 당연히 바꾸어주어야 함.
path('apitokenauth/', TokenObtainPairView_ud.as_view()),

request → 쿠키


  • 서버에서 set_cookie 헤더가 포함된 response를 전달하면, 클라이언트에서는 키값이 'JWT'인 쿠키가 생성되어 있을 것이다.
  • 클라이언트에서 서버로 다음에 쿠키가 포함된 request를 보낼 때, 서버에서는 쿠키를 읽어서 인증하는 과정이 필요하다.
  • 따라서, 쿠키에서 JWT 토큰을 가져와서 읽고, 토큰을 검증하면 된다.
    • JWTAuthentication을 커스터마이징
class Custom_JWTAuthentication(JWTAuthentication):
    def authenticate(self, request):
        raw_token = request.COOKIES.get('JWT', None)
        if raw_token is None:
            return None

        validated_token = self.get_validated_token(raw_token)
        return self.get_user(validated_token), validated_token

class APITest(APIView):
    authentication_classes = [Custom_JWTAuthentication]

    def get(self, request, format=None):
        return Response({'message': 'success call api'})
  • set-cookie를 직접 사용해 보면서 쿠키에 대해 좀 더 알게된 것 같지만, cors 문제가 생기는 경우 브라우저에 쿠키가 설정되지 않는 문제점이 발견되었다.
    • CORS 관련 허용과 CREDENTIALS 설정을 해주어도 안되서 템플릿 자체를 서버에 넣어서 해결하긴 했으나.. 근본적인 해결책은 아닌것 같아서 조금 더 해봐야 할 것 같다.

'프레임워크 > Django' 카테고리의 다른 글

[ Django ] Session  (0) 2021.10.17
[ Django ] CSRFToken  (0) 2021.10.16
[ Django ] JWT  (0) 2021.10.14
[ Django ] Choice  (0) 2021.09.15
[ Django ] MySQL 연동  (0) 2021.09.14

https://www.acmicpc.net/problem/1446

 

1446번: 지름길

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주

www.acmicpc.net

 


풀이 과정


  1. 지름길 데이터를 정리한다.
    1. 시작점과 도착점이 같은데 이동 거리가 다른 지름길이 있을 수 있으므로 최소 거리로 해주어야 한다.
    2. 최소 거리로 조정한 다음, 딕셔너리를 사용하여 [시작점] = [[도착점, 이동거리], ... ] 형식으로 데이터를 저장한다. 
  2. BFS를 진행한다.
    1. 시작점과 이동거리를 a, b라고 할 때, 두가지 경우가 존재한다. 
    2. 현재 지점의 다음 지점을 큐에 삽입한다. (a+1, b+1)
    3. 만약 현재 지점에 대응하는 키가 딕셔너리에 존재한다면(지름길이 존재한다면) 지름길로도 이동해보면 된다. (도착점, b+지름길 이동 거리)
    4. 현재 지점이 D라면, 정답을 갱신시켜 준다. 이 때 유의할 점은, 일방통행이므로 D를 넘게 되면 정답 처리가 되지 않음에 유의한다.
  3. 정답을 출력한다.

문제의 분류는 다익스트라 알고리즘이었으나.. 처음 떠오른 방식이 BFS라 BFS로 풀이함. BFS가 아니더라도 다익스트라 알고리즘이나 DP로도 풀수 있다고 생각한다.

 


소스 코드


import sys
from collections import defaultdict, deque

input = lambda : sys.stdin.readline().rstrip()

N, D = map(int, input().split())
temp = defaultdict(lambda:int(10e9))

for _ in range(N):
    s, e, d = map(int, input().split())
    temp[(s, e)] = min(temp[(s, e)], d)

shortcut = defaultdict(lambda:[])
for (s, e), d in temp.items():
    shortcut[s].append([e, d])

queue = deque()
queue.append([0, 0])

answer = int(10e9)
while queue:
    current, movement = queue.popleft()
    if current > D:
        continue
    if current == D:
        answer = min(answer, movement)
        continue
    if shortcut.get(current) != None:
        for e, d in shortcut[current]:
            queue.append([e, movement + d])    
    queue.append([current+1, movement+1])
    
print(answer)

 

https://jwt.io/introduction

  • 로그인 시 Token 발급
  • 발급된 Token으로 서비스 이용 가능
  • JWT Web Token의 구조는 다음과 같다.
    • Header.Payload.Signature

Header

  • Header에는 Token의 type과 알고리즘(SHA256이나 RSA)으로 구성
    • Base64Url 방식으로 인코딩되어 있다.

Payload

  • 개체(유저 등)의 상태나 부가 정보가 포함된 여러개의 claim으로 구성

  • registered, public, privated claim이 존재한다.

    Registered claims

    • (iss)issuer, (exp)expiration time, (sub)subject, (aud)audience 등 유용한 정보 제공

    • claim의 이름은 3글자

      Public claims

    • 마음대로 정의 가능하나 충돌 방지하기 위해서는 IANA JSON 웹 토큰 레지스트리에 정의하거나 충돌 방지를 포함하는 URI 정의

      Private claims

    • 정보 공유를 위해 생성된 사용자 지정 claim

Signature

  • 인코딩된 Header, 인코딩된 payload, 키(secret), 알고리즘을 가져와서 서명한 부분
  • 메세지가 도중에 변경되지 않았는지 확인하는데 사용

  • JWT Token : Header, Payload, Signature을 모두 합침.

Django에서 JWT 사용


  1. DjangoRestFramework-jwt 설치

     pip install djangorestframework-jwt
  1. Settings.py에 다음 내용 추가

     REST_FRAMEWORK = {
         'DEFAULT_PERMISSION_CLASSES': (
             'rest_framework.permissions.IsAuthenticated',
         ),
         'DEFAULT_AUTHENTICATION_CLASSES': (
             'rest_framework_jwt.authentication.JSONWebTokenAuthentication',
             'rest_framework.authentication.SessionAuthentication',
             'rest_framework.authentication.BasicAuthentication',
         ),
     }
  1. urls.py에 다음 내용 추가

    • url명은 자유로이 변경 가능

    • obtain_jwt_token ⇒ jwt token 획득

      • POST 메서드, data로 username, password 주면 token 획득
    • refresh_jwt_token ⇒ jwt token 갱신

      • POST 메서드, data로 기존 token 주면 새로운 토큰을 response
    • verify_jwt_token ⇒ jwt token 검증

      • POST 메서드, data로 token 주어야 함.
      path('apitokenauth/', obtain_jwt_token),
      path('apitokenrefresh/', refresh_jwt_token),
      path('apitokenverify/', verify_jwt_token),
  1. Token 생성 / 사용 테스트

    • 간단한 api를 만들어 주는데, authentication을 JSONWebTokenAuthentication으로 해주어야 JWT를 사용하여 인증이 진행된다.

      path('api/', APITest.as_view())
      
      class APITest(APIView):
        authentication = [JSONWebTokenAuthentication]
      
        def get(self, request, format=None):
            return Response({'message': 'success call api'})
    • JavaScript로 테스트

      • cors 문제가 발생하여 API 호출이 잘 안되는 문제점이 있었음.

      • django-cors-headers 라이브러리 추가

          pip install django-cors-headers
      • 현재는 API 접근 제한을 따로 걸 필요가 없으므로 전체 허용(CORS_ALLOW_ALL_ORIGINS)

        # INSTALLED_APPS에 추가
        INSTALLED_APPS = [
          ...,
          "corsheaders",
          ...,
        ]
        
        # Settings.py의 맨 아래에 추가
        CORS_ALLOW_ALL_ORIGINS=True
        
        # MIDDLEWARE에 추가, 적어도 CommonMiddleware보다는 위에 가도록
        MIDDLEWARE = [
          ...,
          "corsheaders.middleware.CorsMiddleware",
          "django.middleware.common.CommonMiddleware",
          ...,
        ]
      • 자세한 점은 https://github.com/adamchainz/django-cors-headers

        let userdata = {
          username : 'admin',
          password : 1234,
        };
        
        async function get_JWT_token() {
          try {
              const response = await fetch('http://127.0.0.1:8000/apitokenauth/', {
                  method: "POST",
                  headers: {
                      "Content-Type": "application/json"
                  },
                  body: JSON.stringify(userdata)
              });
              const data = await response.json();
              const token = data["token"];
              console.log(token);
              return token;
          } catch (error) {
              console.log('error');
          }
        };
        
        async function call_api() {
          let api_token = await get_JWT_token();
          const token = api_token;
          const called_api = await fetch('http://127.0.0.1:8000/test/api/', {
                  method: "GET",
                  headers: {
                      "Content-Type": "application/json",
                      "Authorization": "JWT " + token
                  }
              });
          const api_result = await called_api.json();
          return api_result;
        };
      • 오랜만에 async / await 써보니까 많이 헷갈림..

      • 소스를 전체적으로 설명하자면 username이 'admin', password가 1234인 유저의 JWT Token을 얻은 다음, 토큰을 가지고 API를 호출하는 소스이다.

      • API 호출 시에는 headers에 Authorization을 추가해주어야 한다. 값은 JWT + " " + 토큰

      • 유저 데이터가 서버에 없는 경우 JWT 토큰이 발급되지 않으며 당연히 API 호출 시에도 unauthorized가 나타난다.

      • 크롬 개발자 도구에서 console.log가 잘 출력되지 않는다면 필터에 뭐가 입력되어 있는지, 아니면 정보 부분이 체크가 잘 되어있는지 확인해야 한다.

      • 토큰을 로컬 저장소에 저장하거나, 쿠키에 저장할 수 있다는데.. JS를 통해 로컬 저장소에 있는 토큰을 가져올 수 있어서 XSS 공격에 취약하고, 쿠키같은 경우는 secure, httpOnly 속성을 활용하여 막을 수 있다고 한다. 쿠키에 저장하는 방법이 그나마 나아보이긴 하지만, CSRF 문제가 있을 수 있다고 한다.

'프레임워크 > Django' 카테고리의 다른 글

[ Django ] CSRFToken  (0) 2021.10.16
[ Django ] JWT(djangorestframework-simplejwt)  (0) 2021.10.15
[ Django ] Choice  (0) 2021.09.15
[ Django ] MySQL 연동  (0) 2021.09.14
[ Django ] 게시판에 Summernote 에디터 적용  (0) 2021.09.07

https://www.acmicpc.net/submit/14938

 

로그인

 

www.acmicpc.net


풀이 과정


  1. 사실 이 문제는 다익스트라 알고리즘보다는 플로이드 알고리즘으로 풀이하는게 훨씬 쉽고 간단하게 풀린다. 다익스트라 알고리즘을 연습하고자 사용하였음..
  2. 시작점을 1~n까지 각각의 지점에서 다익스트라 알고리즘을 적용한다.
    1. 최소 히프를 사용하여, 현재 갈수있는 노드 중 길이가 최소인 노드를 방문한다.
    2. 현재 노드를 거쳐갈때의 거리로 인접 노드들의 거리를 갱신할 수 있으면 갱신 후 히프에 해당 노드를 넣어준다.  
    3. 1-2를 반복하다 보면 히프에 같은 노드가 쌓일수도 있다. 따라서 히프에 저장된 길이와 현재 저장된 길이를 비교해준 다음, 다른 경우는 최솟값이 갱신된 경우이므로 그냥 넘어간다.
  3. 다익스트라 알고리즘이 종료되면 거리가 m 이내인 지점의 모든 아이템의 개수를 더한 후, 최대 아이템 개수를 갱신한다.
  4. 최대 아이템 개수를 출력한다.

소스 코드


import sys
import heapq

INT_MAX = int(10e9)
input = lambda: sys.stdin.readline().rstrip()

n, m, r = map(int, input().split())
item_count = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]

for _ in range(r):
    a, b, l = map(int, input().split())
    graph[a].append([b, l])
    graph[b].append([a, l])

answer = 0

# 전체 지점에서 시작해본 다음, 아이템을 몇개 구할수 있는지 구한다.
# 이후 최대 아이템의 개수 갱신
for start in range(1, n+1):
    distance = [INT_MAX] * (n+1)
    distance[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])

    while heap:
        node, dist = heapq.heappop(heap)
        if distance[node] != dist:
            continue

        for next_node, next_distance in graph[node]:
            if distance[next_node] > distance[node] + next_distance:
                distance[next_node] = distance[node] + next_distance
                heapq.heappush(heap, [distance[next_node], next_node])
    
    total_item_count = sum([item_count[i] for i in range(1, n+1) if distance[i] <= m])
    answer = max(answer, total_item_count)

print(answer)

https://www.acmicpc.net/problem/1743

 

1743번: 음식물 피하기

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다

www.acmicpc.net

 


풀이 과정


  1. 근처에 있는 음식물끼리 뭉칠수 있으므로, BFS를 진행하면 된다.
  2. 우선 크기가 (N+1, M+1)인 배열을 하나 만들고, 모든 초깃값을 0으로 둔다.
  3. 음식물이 떨어진 좌표의 값을 1로 수정한다.
  4. 왼쪽 위에서 오른쪽 아래로 검사하면서, 값이 1인 경우 BFS를 진행한다.
    1. BFS를 진행하면서, 방문하는 좌표의 값을 0으로 수정한다.
    2. 현재 좌표 기준으로 상,하,좌,우 확인하여 값이 1인 경우 해당 좌표 큐에 저장(다음에 방문할 좌표)
    3. BFS를 종료할 때, 방문한 좌표의 수를 리턴하여 정답 갱신 (최댓값으로)

소스 코드


import sys
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

N, M, K = map(int, input().split())

matrix = [[0] * (M+1) for _ in range(N+1)]

def bfs(matrix, x, y):
    count = 1
    matrix[x][y] = 0
    queue = deque([[x, y]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx, ny = a + dx[i], b + dy[i]
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and \
               matrix[nx][ny] == 1:
                matrix[nx][ny] = 0
                count += 1
                queue.append([nx, ny])

    return count

for _ in range(K):
    a, b = map(int, input().split())
    matrix[a][b] = 1

answer = 0
for i in range(1, N+1):
    for j in range(1, M+1):
        if matrix[i][j] == 1:
            answer = max(answer, bfs(matrix, i, j))

print(answer)

 

https://programmers.co.kr/learn/courses/30/lessons/87377

 

코딩테스트 연습 - 10주차

[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -

programmers.co.kr

 


풀이 과정


  1. 각각의 선분들의 교점을 따로 저장해 둔다.
    1. 문제 아래의 수식을 기반으로 ad - bc가 0일때는 일치하거나 교점이 없는 경우이므로 생략하고 0이 아닐때만 교점 x,y를 구해준다.
    2. 교점 x, y가 정수가 아닌 경우는 저장하지 않아야 함 
      • 나머지 연산 사용
    3. x, y가 정수인 경우, 나중에 필요하기 때문에 최소 x,y 와 최대 x,y를 갱신시켜 준다.
  2. 따로 1000 x 1000 배열을 만들어 둔 다음, 각각의 교점에서 최소 x, 최소 y를 빼준 지점에 * 표시를 해준다.
    • 교점들의 시작점을 모두 (0, 0)으로 설정한다고 생각하면 됨.
  3. 이제 y의 범위를 (최대 y - 최소 y) ~ 0까지의 배열을 저장해주면 된다.
    • x의 범위는 (0 ~ 최대 x - 최소 x) 까지
  • 헤맸던 점은.. 우선 교점 x,y가 정수가 아닌 경우도 고려해서 틀렸었고 다음으로 최댓값의 경우 초기값을 1000000000으로 해두어서 괜찮았는데, 최솟값을 0으로 두었다가 계속해서 틀린 문제점이 있었다. 최솟값도 -1000000000으로 두어 해결함.

소스 코드


def check(a, b, c, d):
    return (a*d) - (b*c) != 0

def get_xy(a, b, e, c, d, f):
    if ((b * f) - (e * d)) % ((a * d) - (b * c)) != 0 or \
       ((e * c) - (a * f)) % ((a * d) - (b * c)) != 0:
            return (-int(10e9), -int(10e9))
    
    x = ((b * f) - (e * d)) // ((a * d) - (b * c))
    y = ((e * c) - (a * f)) // ((a * d) - (b * c))
    
    return (x, y)

def solution(line):
    answer = []
    point_set = set()
    matrix = [['.'] * 1001 for _ in range(1001)] 
    min_x, max_x = int(10e9), -int(10e9)
    min_y, max_y = int(10e9), -int(10e9)
    
    for i in range(len(line)):
        for j in range(i):
            if check(line[i][0], line[i][1], line[j][0], line[j][1]):
                x, y = get_xy(line[i][0], line[i][1], line[i][2],
                             line[j][0], line[j][1], line[j][2])
                
                if x == -int(10e9):
                    continue
                
                if (x, y) not in point_set:
                    min_x, max_x = min(min_x, x), max(max_x, x)
                    min_y, max_y = min(min_y, y), max(max_y, y)
                    point_set.add((x, y))
    
    for x, y in point_set:
        if y - min_y <= 1000 and x - min_x <= 1000:
            matrix[y-min_y][x-min_x] = '*'
        
    max_y = max_y - min_y
    max_x = max_x - min_x
    
    for i in range(max_y, -1, -1):
        answer.append("".join(matrix[i][:max_x+1]))
        
    return answer

 

https://www.acmicpc.net/problem/6550

 

6550번: 부분 문자열

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

www.acmicpc.net

 

풀이 과정


  1. s의 문자들로 구성된 큐를 생성한다.
  2. t의 문자들을 왼쪽에서 오른쪽으로 순서대로 비교
    1. 큐의 맨 앞 요소가 t의 문자와 같다면 제거 후 다음 문자 진행
    2. 큐의 맨 앞 요소가 t의 문자와 같지 않다면 그냥 다음 문자 진행
  3. 큐가 비어있다면 부분 문자열이고, 큐가 비어있지 않다면 부분 문자열이 아닌 것으로 볼 수 있다. 

소스 코드


import sys
from collections import deque

while True:
    try:
        s, t = input().split()
        queue = deque(list(s))

        for c in t:
            if queue and c == queue[0]:
                queue.popleft()

        if queue:
            print('No')
        else:
            print('Yes')
    except:
        break

https://www.acmicpc.net/problem/16401

 

16401번: 과자 나눠주기

첫째 줄에  조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN 

www.acmicpc.net

 


풀이 과정


  1. 이분 탐색으로 나누어 줄 과자의 길이를 찾는다.
    • 과자의 길이가 구간의 중간값일 때, 과자를 나누어줄 수 있는지 확인한다.
    • 확인하는 방법은 모든 과자의 길이를 중간값으로 나눗셈한 값의 합이 나누어주어야 하는 인원 수보다 많거나 같은 경우 나누어줄 수 있는것이며, 반대인 경우 나누어줄 수 없는 경우이다.
      • 예시로는.. (1, 3, 5, 7, 9)라고 하고 중간값이 3이라고 하면, 3, 5일때는 1명이고 7일때는 2명, 9일때는 3명 나누어줄 수 있으므로 총 6명 나누어줄 수 있다. 
    • 나누어줄 수 있다면 과자의 길이의 최댓값을 구해야 하므로 정답을 저장하고 중간값 기준 오른쪽 구간에 대해서 진행하고, 나누어줄 수 없다면 왼쪽 구간에 대해서 진행한다.
  2. 구한 과자의 길이를 출력한다.
  • 구간의 초기값을 문제를 보고 잘 조정해주어야 한다.. 처음에는 단순하게 1000000으로 했다가 틀렸는데, 문제를 다시 보니 과자의 길이가 1000000000까지이므로 최대 1000000000까지 나올 수 있으므 맞추어서 조정해 주었다.

소스 코드


import sys

input = lambda : sys.stdin.readline().rstrip()
M, N = map(int, input().split())
snacks = list(map(int, input().split()))

def test(snacks, target, target_people_count):
    people_count = 0

    if target == 0:
        return False
    
    for snack in snacks:
        people_count += (snack // target)

    if people_count >= target_people_count:
        return True
    else:
        return False

left, right = 0, int(10e9)+1

answer = 0
while left <= right:
    mid = (left + right) // 2
    if test(snacks, mid, M):
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)

+ Recent posts