개발자 아지트

1. CRUD API

CURD는 대부분의 소프트웨어가 가지는 기본적인 데이터 처리 기능으로, Create(생성), Read(읽기), Update(갱신), Delete(삭제)를 의미하는 말임. 리소스를 관리하는 일반적인 API를 만들때도 CRUD 기능을 구현한다. 

2. create

:리소스 생성을 요청하는 API. 서버에 데이터를 제출하기 위해 POST메서드를 사용함. 

리소스 생성 시 필요한 데이터를 json 형태로 body에 담아 요청을 보냄.

요청에 성공하면 201 응답코드로 응답받음.

Location 헤더에 생성된 리소스의 위치를 담아 응답을 받음.

생성된 리소스를 확인할 수 있도록 body에 생성된 리소스를 담아 응답할 수 있음

* ResponseEntity()

: 스프링 프레임워크에서 사용되는 클래스 중 하나로, HTTP 응답(response)의 전체 구성을 표현하는데 사용됨.

주로 컨트롤러에서 클라이언트로 반환할 HTTP 상태 코드, 응답 본문, 헤더 등을 포함할 수 있음.

이것을 통해 클라이언트로 정보를 받아 처리하기 위해서 일반적으로 @RequestBody 어노테이션과 함께 사용되며, 클라이언트가 보내는 JSON 또는 다른 형태의 자바 객체로 변환하여 받을 수 있다. 

* @RequestBody

: 어노테이션이고, HTTP 요청의 본문(body)을 자바 객체로 변환해주는 역할을 한다. 주로 JSON 형식의 데이터를 클라이언트에서 서버로 보낼 때 사용된다. 이 어노테이션은 스프링의 HttpMessageConverter을 통해 요청 본문을 읽고 자바 객체로 변환한다. 

사용방법: 컨트롤러 메서드 에서 @RequestBody를 사용해 요청 본문을 받아올 수 있다. 

3. read

: 리소스 조회를 요청하는 API이다. 서버에 리소스의 정보를 검색하기 위해 GET 메서드를 사용한다. 

== 즉, read메서드는 주로 클라이언트 입장에서 사용되는 메서드이다. 

클라이언트가 서버에 데이터를 요청하면, 서버는 이 요청을 처리하고 필요한 데이터를 반환한다. 

이 메소드의 역할은 서버가 가지고있는 리소스(데이터)를 클라이언트에게 전달하는것이다. 

(개발자 입장에서는 데이터를 반환하는 작업임)

요청에 성공하면 사용자는 200 응답코드를 응답 받는다. 조회된 정보를 body에 담아 응답할 수 있다. 

아까 ResponseEntity는  스프링프레임워크에서 HTTP응답을 표현하기 위한 클래스라고 설명했다. 

이는 데이터를 반환할 뿐만 아니라 데이터를 받을 때도 유용하게 사용될 수 있다. 

HttpStatus.OK

: 개발자가 ResponseEntity객체를 생성하여 데이터를 반환할 때, HttpStatus.OK도 함께 반환한다. 

이는 HTTP 상태 코드 200을 의미하며, 이는 요청이 성공적으로 처리되었음을 나타낸다. 

주요 HTTP 상태 코드 예시  

• HttpStatus.OK (200): 요청이 성공적으로 처리되었음을 나타낸다. 
• HttpStatus.CREATED (201): 요청이 성공적으로 처리되었으며, 새로운 리소스가 생성되었음을 나타낸다. 
• HttpStatus.NO_CONTENT (204): 요청이 성공적으로 처리되었으나, 반환할 콘텐츠가 없음을 나타낸다.
• HttpStatus.BAD_REQUEST (400): 잘못된 요청임을 나타냅니다. 클라이언트의 요청 구문이 잘못되었을 때 사용한다.
• HttpStatus.UNAUTHORIZED (401): 인증되지 않은 요청임을 나타낸다. 
• HttpStatus.FORBIDDEN (403): 서버가 요청을 이해했지만, 권한이 없어 거부되었음을 나타낸다. 
• HttpStatus.NOT_FOUND (404): 요청한 리소스를 찾을 수 없음을 나타낸다.  
• HttpStatus.INTERNAL_SERVER_ERROR (500): 서버 내부 오류가 발생했음을 나타낸다.  

4. update

:클라이언트가 리소스 수정을 요청하는 API. 리소스를 대체하기 위해 PUT 메서드를 사용한다. PATCH를 이용할 수 있으나, 전체 리소스를 대체하기 위해 PUT을 사용한다. 수정할 리소스의 식별자를 url path에 포함해서 요청을 보낸다.  body  값에는 수정할 정보를 담아서 보낸다. 

*@PutMapping

:웹사이트 안에서 바꾸고 싶은 특정 대상이 있는 경우 해당 어노테이션을 이용한다. 

*@PathVariable 

:URL에서 변수를 추출하여 메소드 파라미터로 전달한다. 통해 데이터를 가져온다. 

*@RequsetBody

: 요청 본문에 있는 JSON 또는 XML 데이터를 자바 객체로 변환하여 메소드 파라미터로 전달한다. 

5. delete

리소스 삭제를 요청하는 API. 리소스를 삭제하기 위해 DELETE 메서드를 사용한다. 삭제할 리소스의 식별자를 url path에 포함해서 요청을 보낸다.

*@DeleteMapping

: HTTP DELETE요청 처리를 위한 어노테이션.

해당 어노테이션을 사용하고, 반환값으로는 ResponseEntity<>(HttpStatus.NO_CONTENT)를 통해 적절한 상태코드를 반환해줘야 한다. 

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

문제 해결 방법

1. 시간이 1초씩 감에 따라서 봄버맨의 행동과 폭탄의 상태가 달라지니 시간을 변수로 둔다. 

2. 봄버맨의 움직임 패턴을 분석한다. 

종이에 쓰인 까만색깔 숫자는 시간 초를 의미한다. 

봄버맨은의 행동 패턴은 1초 단위로 다음과 같이 흐른다.

설치

->유지(현재 놓여진 폭탄에 대해서만 시간초를 매김=시간증가)

->설치와 동시에 현재 놓여진 폭탄도 시간초를매김 == 모든 좌표값을 +1 해준다.

->폭발

위 패턴을 폭탄 패턴이라 하겠다. 

그런데 이게 2초 부터는 폭탄이 설치 되어있지 않은 모든 칸에 또 폭탄을 설치하기 때문에, 2초부터 또다른 폭탄 패턴이 진행된다. 

따라서 0초부터 N초 까지는 직사각형 격자판에 2개의 폭탄 패턴이 돌고있다고 보면된다. 

이 2개의 서로 다른 초에 시작한 폭탄 패턴을 어떻게 패턴화 할까?

종이에 쓰인 폭탄 패턴을 0초, 1초는 제외해두고 2초부터 N초까지 보면,

증가와 설치, 폭발과 유지, 설치와 증가, 유지와 폭발 이 네가지 패턴이 반복됨을 알 수 있다. 

(유지와 폭발, 폭발과 유지는 폭발->유지로 친다. 왜냐하면 폭발이 우선순위이기 때문이다. )

이 네가지 패턴이 등장하는 숫자를 따로 모아보면, 

n%4 ==3, n%4 ==1, 이외의 경우로 정리할 수 있다. 

이렇게 정리된 경우를 잘 고려해 출력까지 잘 해주면 된다. 

코드 구현

틀린 코드

# 크기 RxC 격자 
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X


# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys

input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.

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


r, c, n = map(int, input().split()) 

bombMap = []
for i in range(r):
    tmp = list(input().strip())
    bombMap.append(tmp)

print(bombMap)

time = 0
check=0
for i in range(r):
    for j in range(c):
        if bombMap[i][j] == '.':
            bombMap[i][j]=0
        else:
            bombMap[i][j]=1
print('초기상태')
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
    print('check', bombMap[i])
print()

realzero=1


while 1:
    
    time+=1
    check+=1
    
    if check==1:
        if realzero==1:
            realzero=0
            for i in range(r):
                for j in range(c):
                    if bombMap[i][j] > 0:
                        bombMap[i][j]+=1
        elif realzero ==0:
            for i in range(r):
                for j in range(c):
                    bombMap[i][j]+=1
    else:
        if check ==2 :
            for i in range(r):
                for j in range(c):
                    bombMap[i][j]+=1

            rem = [item[:] for item in bombMap]  
            if time >=5:
                for i in range(r):
                    for j in range(c):
                        if rem[i][j]==3:
                            bombMap[i][j]=0
                            for k in range(4):
                                ni = i + dy[k]
                                nj = j + dx[k] 
                                if  0<=ni<r and 0<=nj<c: 
                                    bombMap[ni][nj]=0
        elif check ==3:
            for i in range(r):
                for j in range(c):
                    if rem[i][j]==3:
                        bombMap[i][j]=0
                        for k in range(4):
                            ni = i + dy[k]
                            nj = j + dx[k] 
                            if  0<=ni<r and 0<=nj<c: 
                                bombMap[ni][nj]=0

    if time >= n:
        print('check', check)
        print('time: ', time)
        for i in range(len(bombMap)):
            print('hello', bombMap[i])
        print()
        for i in range(r):
            tmpS=''
            for j in range(c):
                if bombMap[i][j]>0:
                    s='O'
                    tmpS+=s
                else:
                    s='.'
                    tmpS+=s
            print(tmpS)
        break

    rem = [item[:] for item in bombMap]  
    
    print('check', check)
    print('time: ', time)
    for i in range(len(bombMap)):
        print('hello', bombMap[i])
    print()

    if check ==3:
        check=1

정답 코드

# 크기 RxC 격자 
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X

# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys
input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.

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

r, c, n = map(int, input().split()) 

bombMap = []
for i in range(r):
    tmp = list(input().strip())
    bombMap.append(tmp)

time = 0
for i in range(r):
    for j in range(c):
        if bombMap[i][j] == '.':
            bombMap[i][j]=0
        else:
            bombMap[i][j]=1

# 유지 time ==1
time+=1
for i in range(r):
    for j in range(c):
        if bombMap[i][j] > 0:
            bombMap[i][j]+=1

if n==1:
    if time == n:
        for i in range(r):
            tmpS=''
            for j in range(c):
                if bombMap[i][j]>0:
                    s='O'
                    tmpS+=s
                else:
                    s='.'
                    tmpS+=s
            print(tmpS)

else:
    while 1:
        time+=1
        
        if time % 4==1:
            # 유지
            for i in range(r):
                for j in range(c):
                    if bombMap[i][j] > 0:
                        bombMap[i][j]+=1
            rem = [item[:] for item in bombMap]  
            # 폭발
            for i in range(r):
                for j in range(c):
                    if rem[i][j]==3:
                        bombMap[i][j]=0
                        for k in range(4):
                            ni = i + dy[k]
                            nj = j + dx[k] 
                            if  0<=ni<r and 0<=nj<c: 
                                bombMap[ni][nj]=0
        elif time % 4 == 3:
            # 폭발
            rem = [item[:] for item in bombMap]  
            for i in range(r):
                for j in range(c):
                    if rem[i][j]==3:
                        bombMap[i][j]=0
                        for k in range(4):
                            ni = i + dy[k]
                            nj = j + dx[k] 
                            if  0<=ni<r and 0<=nj<c: 
                                bombMap[ni][nj]=0
        else:
            # 설치, 증가
            for i in range(r):
                    for j in range(c):
                        bombMap[i][j]+=1


        if time == n:
            for i in range(r):
                tmpS=''
                for j in range(c):
                    if bombMap[i][j]>0:
                        s='O'
                        tmpS+=s
                    else:
                        s='.'
                        tmpS+=s
                print(tmpS)
            break

시간/공간 복잡도

시뮬레이션 문제 같아서 아예 시간복잡도 계산을 배제하고 문제를 풀었다. 

최적화 및 개선

• 따로 하지않음

어려웠던 점

• 이 문제는 문제를 풀 때 단순하게 생각하면 안된다. 
• 시간을 보내는것과 보내는 중일때 할 일을 잘 구분해야한다. 
• 처음에 폭탄 패턴이 두개 돌거란 생각을 하지 못했다. 따라서 문제 자체가 이해 안되고, 심지어 문제에 문제가 있는거 아닌가 하는 생각을 했었다. 항상 무조건 진행 과정에 대해서 헷깔리거나 파악이 안될때 종이에 해당 과정을 손으로 쓰면서 따라가보는게 중요한 것 같다. 
• 규칙을 찾아야한다. 규칙을 찾는게 제일 중요한 것 같다. 

알게된 것

• sys모듈의 sys.stdin.readLine는 코드로 작성할 때 괄호를 붙이면 안된다. 
• sys.stdin.readLine을 사용할때, 뒤에 개행문자가 따라붙는다. 따라서 사용시 주의해줘야한다. 

개행문자를 제거하는 함수 사용시 참고할 부분이다. 

• strip()이랑 rstrip() 무슨차이인가?
  
  • .strip()과 .rstrip()은 모두 문자열의 양 끝에서 공백 문자를 제거하는 메서드이지만, 제거하는 위치가 다름
    • .strip(): 문자열의 앞과 뒤 양쪽에 있는 모든 공백 문자를 제거한다.
    • .rstrip(): 문자열의 오른쪽(뒤쪽) 끝에 있는 공백 문자만 제거한다.

쿼리 스트링(Query String)이란?

:웹 주소(URL)의 일부로, 클라이언트에서 특정 페이지나 기능을 요청할 때 추가적인 정보를 서버에 전달하기 위해 사용된다.

URL의 끝에 붙으며, ?로 시작하고 여러 개의 키-값 쌍으로 이루어져 있음.

쿼리 스트링이 필요한 상황 예시

: 인터넷 쇼핑몰에서 장난감을 검색하려한다. 이때 필요한 쇼핑몰 웹사이트의 주소는 http://www.toyshop.com이다.

검색어를 입력하고 검색 버튼을 누르면, 웹사이트는 클라이언트가 어떤 장난감을 검색했는지 서버에 알려줘야 한다.

이때 쿼리 스트링이 사용된다. 

쿼리 스트링이 사용된 예시 URL

http://www.toyshop.com/search?product=lego&color=red

URL 요소별 설명

• http://www.toyshop.com/search: 기본 URL (검색 페이지)
• ?: 쿼리 스트링의 시작을 알림
• product=lego: 첫 번째 키-값 쌍. 키는 product 값은 lego
• &: 여러 개의 키-값 쌍을 구분하는 구분자
• color=red: 두 번째 키-값 쌍, 키는 color 값은 red

즉, 이 URL은 "lego"라는 제품과 "red"라는 색상을 검색하겠다는 정보를 서버에 전달한다. 

쿼리 스트링은 URL에 포함되어 서버에 전달되며, 서버는 이 정보를 사용해 요청한 데이터를 반환한다. 

이렇게 하면 사용자가 웹사이트에서 원하는 것을 쉽게 찾을 수 있다. 

쉽게 기억하는 방법

:쿼리 스트링은 마치 웹 주소에 붙이는 "메모"와 같다. 주소 자체가 어디로 갈지 알려주고, 쿼리 스트링은 그 주소에서 무슨 일을 해야 하는지 더 자세히 알려주는 것이라고 생각하면 편하다. 

• 기본 주소: 집 주소 (어디로 갈지)
• 쿼리 스트링: 방문할 때 가져갈 목록 (무엇을 할지)

Static resource

: 서버 처리 필요 없이 바로 클라이언트로 응답하는 처리 방식

특징

•  특정 URL로 요청이 오면 static resource로 인식하고 바로 응답 수행 필요

(반대개념)

Dynamic resource

: 요청을 보내면 서버측까지 도달해서 필요한 메소드를 호출하고 리턴하는 방식

Spring에서는 Static resource와 Dynamic resource를 분리해, static resource 응답을 빠르게 해줄 수 있도록 지원한다. 

요구사항 1. /hello 요청 시 resources/templates/static.html 페이지가 응답할 수 있도록 설정

=> localhost:8080/hello 요청이 들어오면 내부에서 resources/templates/static.html 정적 파일을 보여줄 수 있도록 설정

요구사항 2. 쿼리 파라미터로 name 요청이 들어왔을 때 해당 값을 hello.html에서 사용할 수 있도록 하기

=> 쿼리 파라미터로 name 요청이 들어왔을 때, 해당 값을 hello.html에서 보여주기 

1. 컨트롤러 메서드 작성

2. 쿼리 파라미터로 전달된 값을 'hello.html'템플릿에서 사용할 수 있도록 하기 

[@GetMapping]

: Spring Framework에서 제공하는 어노테이션

HTTP GET 요청을 처리하기 위해 사용된다. 이 어노테이션을 사용해, 특정 URL 경로에 대한 GET 요청을 특정 메서드에 매핑할 수 있다. 

이는 주로 RESTful 웹 서비스에서 데이터를 조회하는 용도로 사용된다. 

*매핑(mapping): 특정 URL 요청을 특정 메서드에 연결하는 것을 의미한다. 

import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class MyController {
	
    @GetMapping("/hello")
    public String sayHello() {
    	return "Hello, World!";
    }
}

@GetMapping("/hello")는 "/hello" 경로로 들어오는 GET 요청을 'sayHello' 메서드에 매핑한다. 

따라서 사용자가 브라우저에서 'http://localhost:8080/hello'로 접근하면, "Hello, World!"라는 문자열을 응답으로 받게 된다. 

(@GetMapping은 @RequestMapping 어노테이션의 축약형으로, 아래와 같은 방식으로도 구현이 가능하다. )

import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;

@RestController 
public class MyController {

	@RequestMapping(value = "/hello", method = ReqeustMethod.GET)
    public String sayHello() {
    	return "Hello, World!";
    }
}

=> @GetMapping은 코드의 가독성을 높이고 RESTful 서비스 개발을 편하게 만들어 준다. 

@RestController는 이 클래스가 RESTful 컨트롤러 임을 나타낸다. 

그러면 RestController는 라우터는 아닌거지?=> yes

: @RestController는 Spring Framework에서 제공하는 어노테이션으로, 해당 클래스가 RESTful 웹 서비스의 엔드포인트를 정의하고 있다는 것을 나타냄 

그러나, 이것 자체는 라우터는 아님.

그냥 라우팅 설정역할을 하는 메서드와 함께 사용될 뿐임

Spring에서 라우팅을 담당하는 부분

:@RequestMapping

@GetMapping

@PostMapping 등의 어노테이션

위 어노테이션들이 HTTP 요청을 특정 메서드에 매핑함. 

@RestController는 위 어노테이션을 포함하는 클래스이고, RESTful API를 제공한다는 의미를 가짐. 

Membercontroller.class

package cholog;

import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;

@Controller
public class MemberController {
    @GetMapping("/hello")
    public String world(@RequestParam (name = "name", required = false, defaultValue = "World") String name, Model model) {
        // TODO: /hello 요청 시 resources/templates/static.html 페이지가 응답할 수 있도록 설정하세요.
        // TODO: 쿼리 파라미터로 name 요청이 들어왔을 때 해당 값을 hello.html에서 사용할 수 있도록 하세요.
        model.addAttribute("name", name);
        return "static";
    }

    public Person json() {
        // TODO: /json 요청 시 {"name": "brown", "age": 20} 데이터를 응답할 수 있도록 설정하세요.
        return null;
    }
}

그동안 나혼자 이상한거하고 있었는듯; main에서 가이드 안보고 코드부터 뜯을 생각(MemberController부터 할 생각)했음

다시 cholog  https://cho-log.github.io/docs/spring/spring-mvc-1  이 페이지 보고 다시 하는중 

스프링 시작하기

1. Welcome Page​

스프링 부트는 정적 페이지와 템플릿 시작 페이지를 모두 지원한다.

먼저 구성된 정적 콘텐츠 위치(main/resources/static/)에서 index.html 파일을 찾습니다. 하나라도 없으면 index 템플릿 (main/resources/templates/)을 찾는다. 둘 중 하나라도 찾으면 자동으로 응용 프로그램 시작 페이지로 사용된다.

처리 방법: 일단 main에 있는 resources/static/hi.html 의 이름을 index.html로 바꾸고 실행하니까 테스트 통과함

2 Static Page​

resources/static 아래의 경로에 위치한 파일은 접근이 가능하다.  서비스에서 필요한 정적 자원들을 해당 경로에 위치시킨 후 활용할 수 있다. 

static과 templates폴더의 차이는?

:static 디렉토리와 tmeplates 디렉토리는 서로 다른 목적을 가진 파일들을 저장한다.

static 디렉토리

목적: 정적 리소스를 저장한다.

내용: css, javaScript, image, font 등과 같은 정적 파일.

기본 경로: src/main/resources/static

접근 방법: 브라우저에서 '/static' URL 경로를 생략하고, 정적 리소스의 경로를 직접 사용한다. 

ex) src/main/resources/static/image/logo.png => http://localhost:8080/images/logo.png 로 접근할 수 있다. 

templates 디렉토리

목적: 동적 템플릿 파일을 저장한다. 

내용물: Thymeleaf, FreeMarker, JSP 등과 같은 템플릿 파일.

기본 경로: src/main/resources/templates

접근 방법: 컨트롤러를 통해 템플릿을 렌더링하고 클라이언트에게 HTML 페이지로 제공함. 

ex) src/main/resources/templates/hello.html 파일은 컨트롤러에서 return "hello"; 와 같이 반환하면 브라우저에 렌더링 된다. 

처리 방법: 일단 main에 있는 resources/templates/static.html을 resources/static/static.html 으로 위치 변경함 

3. Template Engine

동적으로 페이지 처리를 하기 위해서는 템플릿 엔진을 활용할 수 있다. 이번에는 Thymeleaf를 활용해 요청에 대한 동적 처리를 한다.

쿼리 스트링(?name=brown)으로 전달된 name 값을 @RequestParam을 활용하여 컨트롤러 메서드의 파라미터로 주입받는다.

컨트롤러 메서드 내에서 뷰로 값을 전달하기 위해서 Model 객체를 활용한다.

Model 객체는 컨트롤러 메서드의 파라미터로 주입 받을 수 있고, addAttribute 메서드를 통해 값을 전달할 수 있다. 

처리 방법: 일단 main에 있는 MemberController 코드 수정하고 name 코드가 있는 경우와 없는 경우 조건문으로 반환값 다르게 작성해줌. 단, 쿼리 파라미터가 없는 경우에는 static을 반환해야한다고 기존 코드 가이드라인 주석에 적혀있었는데, static.html은 static폴더에만 존재했는데 아마 자동으로 static폴더에서 static.html을 반환하지 않았나 싶음.. 맞는지 확인 필요함 

4. Json 응답

컨트롤러 메서드(웹 요청을 처리하는 함수)의 리턴타입을 그대로 body에 담아 응답하기 위해서는 @ResponseBody를 활용할 수 있음 

해당 어노테이션을 사용하면, 컨트롤러 메서드가 반환하는 데이터를 그대로 웹 응답의 본문(body)에 담아 보낼 수 있음 

해당 상황은 다음과 같이 비유하여 설명할 수 있음.

: 친구에게 편지를 보내는 상황이고, 편지지에 글을 써서 편지 봉투에 넣어 보낼 수 있는 상황임.

그러나 친구가 바로 편지가 쓰여진 편지지을 받고 싶어 한다면, 편지 봉투 없이 바로 편지만 보낼 수있음

• 편지지에 글을 쓰고 편지 봉투에 넣는 것 => 컨트롤러 메서드가 HTML 페이지를 반환하는 것을 의미함
• 편지지를 바로 보내는 것=> 컨트롤러 메서드가 데이터를 그대로 웹 요청의 응답으로 보내는 것이고, 이때 @ResponseBody를 사용

처리 방법: 바로 return 값에 데이터를 넣어 보내면됨 

참고

*쿼리 스트링: https://dayae-dev.tistory.com/356

따로 궁금했던점

• 자바는 왜 클래스에서 한줄 띄우고 시작하는지?
• => 가독성을 높이기 위한 관습
• => 컨벤션(많은 Java 코딩 스타일 가이드와 컨벤션에서 클래스 선언부와 클래스 몸체 사이에 한 줄을 띄우는 것을 권장함)

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

문제 해결 방법

1. 시간을 key로 모기수를 value로 한 딕셔너리를 만든다. 

2. key를 통해 딕셔너리를 정렬한 후, 순회하면서 현재 들어온 모기 수랑 그동안 순회하며 들어온 최대 모기 수를 갱신한다. 최대 모기 수를 갱신하는 중에는 flag변수를 통해 계속 인지하고있는다. 또한 최대 모기 수를 갱신하기 시작한 시간을 표시해준다. 

3. 최대 모기 수를 유지하다가 모기가 나가기 시작하면 최대 모기 수는 깨진다. 따라서 이때 flag변수를 통해 다시 이를 인지할 수 있도록 값을 바꿔주고, 그동안 최대 모기 수를 유지했던 시간을 표시해준다. 

4. 출력

코드 구현

시간 초과된 코드

import sys

n=int(sys.stdin.readline())
total=[]
minn=2100000000
maxx=0

for i in range(n):
    # 입장시간, 퇴장시간
    e, x = map(int, sys.stdin.readline().split()) 
    #print(e, x)
    if e<minn:
        minn=e
    
    if x>maxx:
        maxx=x

    total.append([e,x-1])

#print(minn, maxx)

total 

tmp=[]
for i in range(maxx):
    tmp.append(0)

for i in total:
    s, e = i
    for i in range(s, e+1):
        tmp[i]+=1

#print(tmp)

check = 0
start = -1
end = -1

result = []

cnt=0

for i, value in enumerate(tmp):
    if value == max(tmp):
        if start != -1:
            check=1
            continue
        else:
            #최초로 넣을때 
            check=1
            start = i
            result.append(i)
            cnt+=1
            start=-1
            

    else:
        if check==1:
            check=0
            end=i
            result.append(i)
            end = -1

#print(result)

print(max(tmp))


origin = result[0]
originEnd = 0
originStart=0
for i, value in enumerate(result):
    if i ==0:
        originStart=value
        continue

    if origin +1 == value:
        origin+=1
    else:
        originEnd=result[i-1]
        break

if originEnd==0:
    originEnd=result[-1]

    
print(originStart, originEnd)

정답 코드

(주석 있는 버전)

import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
d = defaultdict(int)
print('defaultdict', d)
for i in range(n):
    s, e = map(int, input().split())
    d[s] += 1
    d[e] -= 1




m, cnt = 0, 0 # cnt는 모기 마릿수 m은 최대갱신 모기 마릿수 
tem, txm = 0, 0# 최댓값 갱신시 시간과 갱신 해제시 시간
flag = False
for i in sorted(d.keys()):
    print(i)
    cnt += d[i]
    # 기존 최대 모기수 보다 현재 모기수가 더 클때
    # == 최고일때만 계산함 
    if cnt > m:
        m = cnt
        tem = i
        flag = True
    # 현재 모기수 cnt보다 최대 갱신 모기수가 더 크고
    # 만약, 현재 값이 모기가 나가는 타이밍일때
    # 현재 모기수에서 지금 시간의 모기를 빼면 음수값이라 더한 격이 되어
    # 지금 나간 모기를 더했을때의 값 = 최대값이 m인 경우이다. 
    # FLAG가 TRUE인 상태 
    # 마찬가지로 최고자리가 박탈 됐을때 계산함 
    elif cnt < m and cnt - d[i] == m and flag:
        txm = i
        flag = False
print(m)
print(tem, txm)

(주석 없는 버전) - 변수명 변경됨

import sys
from collections import defaultdict
input = sys.stdin.readline

n=int(input())
dict = defaultdict(int)

for i in range(n):
    # 입장시간, 퇴장시간
    e, x = map(int, input().split()) 

    dict[e] += 1
    dict[x] -= 1
    

maxx, nowMos = 0, 0
startTime, endTime = 0, 0
flag = False
for i in sorted(dict.keys()):
    nowMos += dict[i]

    if nowMos > maxx:
        maxx = nowMos
        startTime = i
        flag = True
    elif  nowMos < maxx and nowMos - dict[i] == maxx and flag:
        flag = False
        endTime = i

print(maxx)
print(startTime, endTime)

시간/공간 복잡도

입력값보다 입력값의 값의 범위가 워낙 커서 웬만하면 N으로 구현해야 했다. 

최적화 및 개선

• 기존에는 입력값의 범위를 전부 순회하면서 최대 모기수를 체크해서 시간초과가 발생했었다. 
  • 이런 방식의 관점을 바꿨다. 
  • => 현재 방에 있는 모기의 수가 갱신이 되는 모기의 수일 경우에만 체크 

어려웠던 점

시간복잡도에 대한 개념은 알고있지만, 여전히 문제 풀기전에 시간복잡도에 대한 계산을 하는것이 어렵다. 

파이썬의 경우 1초에 최대 연산횟수가 logN인 알고리즘으로 계산해도 최대 연산 횟수가 10억번인데, 이 문제의 경우 값의 범위가 10억을 훌쩍넘어 20억쯤 된다. 이런 경우는 시간복잡도 계산을 어떻게 해야하는지 모르겠다. 

알게된 것

• sys모듈의 sys.stdin.readLine() 함수를 input 변수로 저장 할 생각을 못하고 계속 수기로 작성해왔었는데 이제는 변수로 저장할 줄 알게됐다. 
• 딕셔너리 자료구조가 이런경우에 유용함을 다시 상기시킬수 있었다. 

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

문제 해결 방법

시간복잡도를 고려햐여 문제를 잘 읽고 그대로 구현하면 됨.

아래의 조건을 고려하여 코드를 작성하였음.

• 노트북에 스티커를 붙이기전에 모눈종이의 크기만으로 노트북에 들어갈 수 있는지 확인한다. 
  
  • 모눈종이의 행이 노트북의 행의 크기를 넘거나 모눈종이의 열이 노트북의 열의 크기를 넘는 경우, 모눈종이의 행과 열을 뒤집었을때(90도 회전한다고 가정했을때)도 노트북의 범위를 벗어나는지 확인한다. 
    
    • 범위를 벗어나지 않는다면 90도 회전
    • 범위를 벗어난다면 다음 스티커로 넘어간다. 
• 노트북에 모눈종이의 크기가 들어갈 수 있을때, 노트북의 빈곳에 스티커를 붙이는 시도를 한다. 
• 노트북에 붙여진 스티커의 현황과 스티커는 겹쳐도 되지만, 붙이려는 스티커의 빈칸이 노트북에 붙여진 스티커 일부를 지워서는 안된다.(모눈종이 전체를 붙이려고 할 경우 주의)
• 노트북에 스티커를 붙일때 회전을 먼저 해서는 안되고 일단 생긴 그대로 붙이려는 시도를 반드시 해야한다. 
  • 그 후 90도 회전을 3번 할 수 있다. (단, 90, 180, 270 순으로 진행해야함)
  • 3번의 회전이 끝나면 더이상의 회전은 의미가 없으므로, 스티커를 버린다.(다음 스티커로 넘어간다. )

코드 구현

시간초과난 코드 1

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

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

print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    stickerPocket[i]=tmpList
    stickerPocketEntire[i]=[mm, nn]
    print('checkcnt: ', cnt)
    cnt+=1
    print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        if cnt <=3:
            cnt = rotation(cnt, i)
            r, l = stickerPocketEntire[i]
        else:
            i+=1
            cnt=0
                
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                
                print('hi')
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

시간초과난 코드 2

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

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

print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    print('after',tmpList)
    print('checkcnt: ', cnt)
    cnt+=1
    print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                print('hi')
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

시간초과 해결후 틀린 코드 1

import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

#print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

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

#print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    #print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    # print('after',tmpList)
    # print('checkcnt: ', cnt)
    cnt+=1
    # print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    rem = copy.deepcopy(visited)
    # print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                # print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        visited=copy.deepcopy(rem)
                        check = 0
                        # print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                # print("뭐지 nr:", nr, "nl:", nl)
                visited=copy.deepcopy(rem)
                check = 0
                # print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                # print('hi')
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                # print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

#print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

시간초과 해결후 틀린 코드 2

import sys
#import copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님

# 다른 스티커와 겹침X, 노트북 벗어나면X, 
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽) 

# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기

# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?

#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)

n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    tmp2=[]
    for j in range(r):
        tmp1 = list(map(int, sys.stdin.readline().split()))
        tmp2.append(tmp1)
    stickerPocket.append(tmp2)

#print(stickerPocket)

#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임. 
# 단, 붙일 수 없는 경우는 판별해줌 
# 붙일 수 없는 경우
#   1. 노트북을 벗어나는경우[조건문]
#   2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
#   ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
#   ->다음 스티커로 넘어간다. 

# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다. 

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

#print('visited', visited)

def rotation(cnt, i):
    
    r, l = stickerPocketEntire[i]
    # 3번만 돌림 
    
    #90도로 돌리기 
    tmp = stickerPocket[i]
    nn=len(tmp) 
    mm=len(tmp[0])
    tmpList =[]
    for qq in range(mm):
        tmpList2=[]
        for pp in range(nn-1, -1, -1):
            tmpList2.append(tmp[pp][qq])
        tmpList.append(tmpList2)
    #print('before',stickerPocket[i])
    stickerPocket[i]=tmpList
    
    stickerPocketEntire[i]=[mm, nn]
    # print('after',tmpList)
    # print('checkcnt: ', cnt)
    cnt+=1
    # print('cnt: ', cnt)
    return cnt

def backtrack(p, q, i, r, l, visited):
    #rem = copy.deepcopy(visited)
    rem = [item[:] for item in visited]
    # print('초기 rem', rem)
    # 이부분 백트래킹으로 구현해야할듯 
    for j in range(r):
        for jj in range(l):
            #왼쪽 위부터 조회
            nr = p+j
            nl = q+jj
            if 0<=nr<n and 0<=nl<m:
                # print('i:', i, "j:", j, "jj", jj)
                if stickerPocket[i][j][jj]==1:
                    #두번째 스티커를 자리에 붙여본다
                    if visited[p+j][q+jj]!=1:
                        #겹치는지 확인후 붙여보기
                        visited[p+j][q+jj]=1
                    else:
                        #겹친다.
                        #스티커를 붙이기 전으로 원래대로 돌아가기 
                        #visited=copy.deepcopy(rem)
                        visited=[item[:] for item in rem]
                        check = 0
                        # print('리턴 visited', visited)
                        return visited, check
                check = 1
            else:
                # print("뭐지 nr:", nr, "nl:", nl)
                #visited=copy.deepcopy(rem)
                visited = [item[:] for item in rem]
                check = 0
                # print('리턴 visited', visited)
                return visited, check
                
    if check == 1:
        return visited, check

i=0
cnt=0 # 회전 횟수
check=1
while(1):
    r, l = stickerPocketEntire[i]
    if (n<r or m<l) or check ==0: 
        if l<=n and r<=m:
        # 모눈종이의 크기가 노트북을 넘어가면
        # 90도 회전 적용
        # 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
            if cnt <3:
                cnt = rotation(cnt, i)
                r, l = stickerPocketEntire[i]
            else:
                i+=1
                cnt=0
        else:
            i+=1
    
    if i == 0:
        #항상 0,0에서 부터 시작해야함
        for j in range(r):
            for jj in range(l):
                if stickerPocket[0][j][jj]==1:
                    visited[j][jj]=1
        i+=1
        cnt=0
    else:
        for p in range(n):
            for q in range(m):
                if i ==k:
                    break
                r, l = stickerPocketEntire[i]
                # print('hi')
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                visited, check = backtrack(p, q, i, r, l, visited)
                # print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
                # print('hi end')
                if check==1 or cnt>3: #스티커를 제대로 붙였을 때
                    i+=1
                    cnt=0

                if check==0 and cnt>3:
                    break
            if check==0 and cnt>3:
                break

    if i ==k:
        break

#print("?????????")
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

정답 코드

import sys

n, m, k = map(int, sys.stdin.readline().split())

# 스티커 받고, 스티커 함에 넣기 
stickerPocket = []     # 모눈종이 각각 map 모음
stickerPocketEntire=[] # 모눈종이 r, l 모아놓는 함
for i in range(k):
    #모눈종이의 행, 열
    r, c = map(int, sys.stdin.readline().split()) 
    stickerPocketEntire.append([r,c])
    sticker=[]
    for j in range(r):
        tmp = list(map(int, sys.stdin.readline().split()))
        sticker.append(tmp)
    stickerPocket.append(sticker)

# 붙여졌나요?
visited=[[0] * m for i in range(n)]

# 90도 회전 함수
def rotation(cnt, i): 
    r, l = stickerPocketEntire[i] 
    # (90, 180, 270)도에 해당하게끔 3번만 돌림 
    
    sticker = stickerPocket[i]
    nn=len(sticker) # 기존의 행을 열로 사용
    mm=len(sticker[0]) # 기존의 열을 행으로 사용
    newSticker =[]

    for qq in range(mm):
        tmp=[]
        for pp in range(nn-1, -1, -1):
            tmp.append(sticker[pp][qq])
        newSticker.append(tmp)
    stickerPocket[i]=newSticker
    stickerPocketEntire[i]=[mm, nn]
    # 회전카운트 증가시킴
    cnt+=1  
    return cnt

def backtrack(p, q, i, visited):
    # 스티커를 붙일 수 없을 경우, 붙이려는 스티커를 붙이기 전 상태로 돌아오기위한것 
    rem = [item[:] for item in visited]
    # 붙이려는 스티커의 행열 조회
    r, c = stickerPocketEntire[i] 
    for j in range(r): # 행
        for jj in range(c): # 열
            #왼쪽 위부터 조회
            nr = p+j # 행/ 기존 행:n
            nc = q+jj # 열/ 기존 열:m
            # 스티커가 노트북 범위 안에 들어오면
            if 0<=nr<n and 0<=nc<m: 
                # 모눈종이에서 붙여야 하는 지점인 경우 
                if stickerPocket[i][j][jj]==1:
                    # 미리 붙여진 스티커가 없다.
                    if visited[nr][nc]!=1:
                        # 스티커 붙이기 
                        check = 1
                        visited[p+j][q+jj]=1
                    # 미리 붙여진 스티커가 있다. 겹친다.
                    else:
                        # 스티커를 붙이기 전(원래대로)으로 돌아가기 
                        visited=[item[:] for item in rem]
                        # 스티커를 못붙였다는 표식
                        check = 0
                        return visited, check
                # 모눈종이에서 빈칸인 경우
                else:
                    continue
            # 스티커가 노트북 범위 안에 못을어오면
            else:
                # 노트북 원상복구
                visited = [item[:] for item in rem]
                # 스티커를 못붙였다는 표식
                check = 0
                return visited, check
    # 스티커를 정상적으로 붙인 경우
    if check == 1:
        return visited, check

# 시작 스티커 번호
i=0
# 붙일 스티커 번호가 증가한 후 한번도 스티커를 회전한적 없는경우를 가리기 위한 변수
first=1
# 회전 횟수
cnt=0 
# 스티커를 붙이지 않았다는 표식
check=0
needRotation=0
while(1):
    rotat=0
    
    # 붙일 스티커가 없는 경우 종료 
    if i == k:
        break

    # 스티커의 행 열
    r, c = stickerPocketEntire[i]

    # 스티커의 행이나 열중 하나가 노트북을 벗어나는 경우
    if n<r or m<c: 
        #스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 들어가는 경우
        if c<=n and r<=m: 
            if cnt <3: # 0-0, 90-1, 180-2, 270-3
                cnt = rotation(cnt, i)
                rotat = 1
            # 회전을 4번다 한 경우, 다음 스티커로 넘어감 
            else:
                i+=1
                cnt=0
                first=1
        # 스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 안들어가는 경우=붙일 수 없는 경우
        elif c>n and r>m:
            # 다음 스티커로 넘어감 
            first=1
            i+=1
            cnt=0

    # 스티커가 붙여지지 않았고 0도 일때 스티커 붙이는 시도를 다 해본경우 
    # 회전이 270까지 되지 않은 경우=> 회전
    if check == 0 and first==0 and rotat==0 and needRotation==1:
        if cnt<=3:
            cnt = rotation(cnt, i)
        
    for p in range(n):
        for q in range(m):
            # 한번 돌았으면 first=0
            rotat=0
            first=0
            
            # 붙일 스티커가 없는 경우 종료 
            if i == k:
                break

            # 붙일 스티커 붙여보기 
            visited, check = backtrack(p, q, i, visited)
            #스티커를 제대로 붙였으면 빠져나감
            if check==1: 
                break
        #다음으로 붙일 스티커로 넘어가고, 회전 횟수 초기화
        #스티커를 붙였으면 빠져나감
        if check==1:
            check = 0
            i+=1
            cnt=0
            first=1
            needRotation=0
            break
    if check == 0:
        needRotation=1

    if cnt==3:
        i+=1
        first=1
        cnt=0

    # 붙일 스티커가 없는 경우 종료 
    if i ==k:
        break

# 노트북에 붙여진 스티커 개수 세기
sum=0
for end in visited:
    for end2 in end:
        if end2==1:
            sum+=1
print(sum)

시간/공간 복잡도

N(40)*M(40)*K(100) = 16000이라  1초 기준으로 NlogN으로 풀어야 하는 문제이다. 근데 문제에서 2초를 주엇으니 사실상

2NlogN인건가? 

스터디할 때 물어볼 것 

최적화 및 개선

• sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
• copy 모듈의 deepcopy함수는 시간을 많이 잡아먹으니, 다른 방식으로 리스트 복사를 해야 시간초과가 나지 않는다. 

어려웠던 점

문제를 정확하게 이해해야 빈틈없이 구현할 수 있다. 

시뮬레이션 문제는 빈틈없이 구현하는게 가장 중요한것 같다. 

알게된 것

• copy모듈의 deepcopy()함수는 시간을 많이 잡아먹는다. 따라서 다른 방법을 이용해야한다.(시간초과의 주범)

[CPU 아키텍처란?]

:하드웨어(CPU)가 작동하는 방식을 나타냄. =마이크로 아키텍처(microarchitecture) 

상용화된 제품은 ARM(RISC)과 x86(CISC) 등이 대표적인 예시임

[왜 알아야 하는가?]

: 서비스나 애플리케이션 운영 환경은 하드웨어에서부터 다양함. 

- arm, x86과 같은 CPU부터 GPU, TPU, NPU 까지 고려해야할 환경이 많음

- 사용 가능한 리소스의 제한에 따라서 개발 방향도 변경될 수 있음 

(리소스는 CPU, 메모리, Storage 성능, 네트워크 성능 등 다양한 변수가 존재함)

[실무와 가까운 중요이야기]

• 리눅스의 멀티 유저 특성
  • 리눅스는 여러 사용자가 하나의 시스템에서 동시에 작업할 수 있는 환경을 지원함
  • 각 사용자는 자신의 환경, 파일, 프로세스 등을 독립적으로 관리할 수 있음
• 컨테이너 기술
  • 이는 리눅스의 멀티유저를 지원하는 특성을 확장해서, 프로세스와 리소스 등을 격리된 환경에서 사용할 수 있도록 제공함
  • 이는 나아가서 클라우드 컴퓨팅과 마이크로서비스 아키텍처를 구성하는데 있어서 중요한 역할을 하게됨

[자주 겪는 문제]

• Too many open files / 최대 생성 프로세스 제한
  • 설명 
    • 보안상의 이유로 Linux상에서 생성할 수 있는 프로세스나 프로세스가 열 수 있는 파일의 수 등을 제한하고 있음
    • 따라서 개발 과정에서 한번쯤은 마주치는 오류 중 하나임
      • 실제로 프로세스 생성이나 파일 접근을 동시에 다량으로 하거나, Socket 을 다루는 과정에서 발생할 수 있음
        (Socket이 파일로 관리되기 때문)
  • 해결 방법
    • /etc/security/limits.conf 혹은 ulimit 명령어를 통해 제한 값을 조정할 수 있음
• 부모 프로세스 - 자식 프로세스의 관리
  • 필요에 따라서 자식 프로세스를 생성할 때, 부모 프로세스에 종속되지 않게 독립된 프로세스로 생성할 수 있음
  • 고아 프로세스/좀비 프로세스 문제
    • 시스템 자원이 낭비되고 있는 상태
    • 프로세스 관리의 어려움
    • PID(Process ID)의 낭비
      • 시스템에서 사용할 수 있는 PID 수가 제한되어 있으므로, 프로세스 생성이 불가능해질 수 있
• OOM(Out of Memory)
  • 메모리 누수(Memory Leak)의 경우
    • 해결 방법
      • 메모리 누수 
        • APM(Application Performance Monitoring) 혹은 프로파일러를 활용해 메모리 누수 지점을 찾고 분석함
        • GC(Garbage Collector)최적화
        • 미사용 자원 해제
  • 계획된 메모리를 초과하는 요청이 오는 경우
    • (하드웨어적 제한) 32bit CPU의 경우 최대 4GB, 물리적인 메모리의 한계에 달하는 경우 등
    • (소프트웨어적 제한) JVM이나 V8 Engine(Node.js에서 관리하는 것) 등에서 제한하는 경우 등
    • 해결 방법
      • 정답은 없음=설득의 영역
      • 상황에 가장 알맞은 사양을 결정해야함. 어떨 때는 스펙 변경으로, 또 다룰 상황에서 코드의 최적화 등으로 해결할 수 있다. 
      • 트레이드 오프를 고려하여 적절한 선택을 할 수 있어야 한다. 

[사용 이유]

• 비용절감
  • 온프레미스 환경(하드웨어를 직접 구매해서 인프라를 구성하는 환경)과 달리, 사용한만큼 비용을 지불하기 때문에 비용 절감 효과가 큼
• 유연한 확장
  • 리소스 사용량, 네트워크 트래픽을 기준으로 사용량에 맞게 확장과 축소를 할 수 있음
• 효율적인 관리
  • 인프라 유지보수도 클라우드 벤더사에서 담당하기 때문에 제품 개발에 집중 할 수 있음

[위험성]

• 데이터 보안
  • 데이터가 클라우드 환경에 저장됨으로써, 온프레미스 환경에 비해 훨씬 해킹이나 데이터 유출 위험에 노출되기 쉬움
• 서비스 가용성
  • 클라우드 벤더사에 의존하는 격으로, 해당 벤더사에 문제가 생기면 그대로 서비스 문제로 연결됨
• 비용 관리의 어려움
  • 확장이 쉽게 이루어지는 만큼, 이를 효과적으로 관리하지 못할 경우 비용이 필요 이상으로 지불하게 되는 경우가 발생할 수 있음

[반면 온프레미스 환경의 적합한 사용 환경은??]

• 보안에 민감한 서비스에서 사용 ex) 금융권, 의료, 정부 사업 등 인프라, 데이터가 물리적으로 분리되어있을 필요가 있는 경우
• 낮은 지연 시간이 필요한 서비스에서 사용 ex)게임 산업, 금융 서비스, 군사 산업 등의 산업에서 필요로함 

클라우드의 단점을 보완하기 위한 조짐

• 하이브리드 클라우드, 멀티 클라우드 등 다양한 형태의 클라우드 사용 사례들이 나타나고 있음

[이분탐색(이진탐색)의 정의]

: 오름차순으로 정렬된 리스트에서 찾고자 하는 값의 위치를 찾는 알고리즘

[이분탐색의 특징]

: 모든 값을 순회하는 일반탐색 보다 빠른 속도.

시간복잡도: O(logN)

[이분 탐색 진행 과정]

오름차순으로 정렬된 배열에서 특정 데이터를 탐색하는 상황

1. 오름차순으로 정렬된 배열에서 맨처음 값의 인덱스를 low라고 하고, 맨 뒤의 인덱스의 값을 high의 변수에 저장함. 

2.  배열의 중앙값을 선택: 중앙값은 mid가 된다. 

3. 중앙값과 특정 데이터의 값을 비교한다. 

만약, 중앙값보다 특정 데이터가 클 경우, 중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다. 

(반대의 경우는 high가 중앙값-1의 값을 가짐)

4. 선택된 우측 요소의 중앙값을 선택한다. (mid갱신)

5. 중앙값과 특정 데이터를 비교한다.

만약, 특정 데이터가 중앙값 보다 클 경우,중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다.

(반대의 경우는 high가 중앙값-1의 값을 가짐)

6. 남은 배열(2개)중에 좌측 요소를 선택하여 특정 데이터를 비교한다. 

만약 두 값이 같으면 탐색 종료 

[구현]

• 반복문
• 재귀

1. 탐색 대상값이 속한 자료를 오름차순으로 정렬한다. 

2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. 

3. 중간값(mid)이 찾고자 하는 값(target)과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid값이 같을 때까지 아래 조건에 따라 2번 3번을 반복한다. 

1. 찾고자 하는 값(target)이 중간값(mid)보다 작으면 end값을 mid-1의 값으로 바꾼다. 
2. 찾고자 하는 값(target)이 중간값(mid)보다 크면 high값을 mid+1의 값으로 바꾼다.

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

문제 해결 방법

시간복잡도를 고려햐여 이분탐색을 통해 문제를 풀이해야 함 

코드 구현

시간초과난 코드

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
    k, value = input().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
# check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(input())
    tmp.append(value)

tmp.sort()

cnt = 0
for i in tmp:
    if i <= check[cnt][1]:
        print(check[cnt][0])
    else:
        while 1:
            cnt+=1
            if i <= check[cnt][1]:
                print(check[cnt][0])
                break

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
    k, value = input().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
# check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(input())
    tmp.append(value)

tmp.sort()
############################
mid, high, low = (n-1)//2, n-1, 0

print('mid, high, low:', mid, high, low)

for i in range(m):
    target = tmp[i]
    print("target:", target)
    print("check:", check)
    while 1:
        if target <= check[mid][1]:
            print(check[mid][0])
            break
        elif target > check[mid][1]:
            low = mid+1
            mid = (low+high)//2
        elif target < check[mid][1]:
            high = mid-1
            mid = (low+high)//2

bisect 모듈을 통해 풀이한 코드

from bisect import bisect_left
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
checkChing=[]
checkValue=[]

for i in range(n):
    k, value = sys.stdin.readline().split()
    checkChing.append(k)
    checkValue.append(int(value))

# 값 받고
tmp = []
for i in range(m):
    value = int(sys.stdin.readline())
    tmp.append(value)

for i in range(m):
    target = tmp[i]
    tmpIndex=bisect_left(checkValue, target)
    print(check2[tmpIndex])

bisect 모듈 없이 풀이한 코드

import sys

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, sys.stdin.readline().split())
check=[]
for i in range(n):
    k, value = sys.stdin.readline().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(sys.stdin.readline().rstrip())
    tmp.append(value)

for i in range(m):
    high = len(check)
    low = 0
    result = 0
    target = tmp[i]
    while low <= high:
        mid = (low + high)//2
        if target <= check[mid][1]:
            high = mid-1
            result = mid
        elif target > check[mid][1]:
            low = mid+1
    print(check[result][0])

시간/공간 복잡도

모든 경우를 다 조회할 경우 N은 100만까지 가능함. 

이 경우, 시간 초과를 면하기 위해서는 O(NlogN)의 시간복잡도가 되게끔 코드를 작성해야 한다. 

(기존에 작성한 코드에서 사용한 이중 반복문으로 구현하면 안됨,,)

(백준한정)추가시간 없음 이라는 말은 파이썬은 기존에 1초에 2천만번 연산 가능함 원래는 이런말 없으면 1초에 1억번 연산가능함 

최적화 및 개선

sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음

어려웠던 점

이분탐색 개념이 가물가물 했다. 

어이없는 실수: 받은 값을 정렬함으로써 아무리 알고리즘을 맞게 짜도 출력 자체가 이상하게 되도록 함; (스스로 재앙을 불러옴)

알게된 것

• 이분탐색
  • 따로 포스팅 했음. https://dayae-dev.tistory.com/341
• bisect 모듈
  •  
• sys 모듈 sys.stdin.readline: 반복적으로 입력받을 때 input()에 비해 시간을 확 줄여줌
  • 단, 반복적으로 받지만 하나의 값만을 받는 경우 rstrip()을 통해 받은 값의 오른쪽에 붙는 개행문자를 지워줘야함.