Karice의 여행 & 코딩 블로그

1. 정의

부하분산 또는 로드 밸런싱은 컴퓨터 네트워크 기술의 일종으로 중앙처리 장치 혹은 저장장치와 같은 컴퓨터 자원들에게 작업을나누는 것을 말한다.

서버에 가해지는 부하(=로드)를 분산(=밸런싱) 해주는 기술이다.

사업의 규모가 확장되고, 클라이언트의 수가 늘어나게 되면 기존 서버만으로는 정상적인 서비스가 불가능하게 되는데, 이런 증가한 트래픽에 대처할 수 있는 방법은 크게 두가지 이다.

• Scale Up : 서버 자체의 성능을 높이는 것
• Scale Out : 여러대의 서버를 두는것

Scale-out방식에서 로드밸런싱이 필요하다. 각각의 서버에 균등하게 트래픽을 분산시켜주는 것이 바로 load balancer입니다.

2. 로드밸런싱 알고리즘

라운드 로빈

서버에 들어온 요청을 순서대로 돌아가며 배정하는 방식 

서버와의 연결이 오래 지속되지 않는 경우 적합하다.

가중 라운드로빈 방식

각서버에 가중치를 매기고 가중치가 높은 서버에 요청을 우선적으로 배정하는 방식

서버의 트래픽 처리 능력이 다른 경우 사용한다.

최소 연결 방식

요청이 들어온 시점에 가장 적은 연결 상태를 보이는 서버에 트래픽을 배정하는 방식

서버에 분배된 트래픽들이 일정하지 않은 경우에 적합하다.

IP 해시 방식

클라이언트의 IP주소를 특정 서버로 매핑하여 요청을 처리하는 방식

사용자가 항상 동일한 서버로 연결된다.

3. 주요 기능

NAT (Network Address Translation)

--> 사설 IP 주소를 공인 IP주소로 바꾸는데 사용하는 통신망의 주소 변조기입니다.

Tunneling

--> 인터넷 상에서 눈에 보이지 않는 통로를 만들어 통신할 수 잇게 하느 ㄴ개념

--> 데이터를 캡슐화해서 연결된 상호 간에만 캡슐화도니 패킷을 구별해 캡슐화를 해제할 수 있습니다.

DSR(Dynamic Source Routing protocol)

--> 로드 밸런서 사용시 서버에 클라이언트로 되돌아가는 경우 목적지 주소를 스위치의 IP 주소가 아닌 클라이언트의 IP 주소로 전달해서 네트워크 스위치를 거치지 않고 바로 클라이언트를 찾아감

4. 구조

5. 종류

L2 - Mac 주소를바탕으로 Load Balancing 합니다.

L3 - IP주소를 바탕으로 Load Balancing 합니다.

L4 - Transport Layer(IP와 Port) Level에서 Load Balancing을 합니다. ex) TCP, UDP

L7 - Application Layer(사용자의 Request) Level에서 Load Balancing을 합니다. ex) HTTP, HTTPS

6. 동작방식

1. 클라이언트의 브라우저에서 abc.net이라고 입력
2. 클라이언트에 설정된 메인 DNS 서버로 abc.net의 IP주소를 문의
3. 메인 DNS 서버는 abc.net 주소를 관리하는 별도의 DNS 서버에 IP 주소 문의
4. 별도 관리 DNS 서버는 로드 밸런서의 IP 주소를 메인 DNS 서버에게 알려줌
5. 메인 DNS 서버는 획득한 VIP 주소를 클라이언트에 전송
6. 클라이언트에서 로드밸런서의 VIP 주소로 HTTP요청
7. 로드밸런서는 별도 로드밸런싱 방법을 통해 서버에 요청 전송
8. 서버의 작업 결과를 받은 로드밸런서는 전달받은 HTTP 결과를 클라이언트에게 전송 

참조 : 

https://velog.io/@jisoo1170/Load-Balancing%EC%9D%B4%EB%9E%80

https://nesoy.github.io/articles/2018-06/Load-Balancer

https://www.stevenjlee.net/2020/06/30/%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%EC%9D%98-%EB%B6%80%ED%95%98%EB%B6%84%EC%82%B0-%EB%A1%9C%EB%93%9C%EB%B0%B8%EB%9F%B0%EC%8B%B1-load-balancing-%EA%B7%B8/

1. HTTP란

Hyper Text Transfer Protocol의 약자로 서버/클라이언트 모델을 따라 데이터를 주고 받기 위한 프로토콜이다.

즉 HTTP는 인터넷에서 하이퍼텍스트를 교환하기 위한 통신 규약으로 80번 포트를 사용하고 있다. 따라서 HTTP 서버가 80번 포트에서 요청을 기다리고 있으며 클라이언트는 80번 포트로 요청을 보낸다.

애플리케이션 레벨의 프로토콜로 TCP/IP위에서 작동한다. HTTP는 상태를 가지고 있지 않아 stateless 프로토콜이다.

HTTP의 단점으로는 암호화가 되지 않아서 정보를 제 3자가 조회하기가 너무 쉬웠다. 그래서

HTTPS가 등장하게 되었다.

2. HTTPS란

HTTP에서 암호화가 추가된 프로토 콜이다. 433번 포트를 사용하며, 네트워크 상에서 중간에 제 3자가 정보를 볼 수 없도록 공개키 암호화를 지원하고 있다.

공개키 암호화 : 공개키로 암호화를 하면 개인키로만 복호화(암호를 푸는 것) 할 수 있다. -> 개인키는 나만 가지고 잇으므로, 나만 볼 수 있음

개인키 암호화 : 개인키로 암호화하면 공개키로만 복호화 할 수 있다. -> 공개키는 모두에게 공개되어 있으므로, 내가 인증한 정보임을 알려서 신뢰성 확보

3. HTTPS의 동작 과정⭐

서버는 클라이언트가 요청을 보낼 때 암호화를 하기 위한 공개키를 생성해야되는데, 일반적으로는 인증된 기관에 공개키를 전송하여 인증서를 발급받고 있다. 

자세한 과정은

1. A기업은 HTTP 기반의 애플리케이션에 HTTPS를 적용하기 위해 공개키/개인키를 발급함
2. CA 기업에게 돈을 지불하고, 공개키를 저장하는 인증서의 발급을 요청함
3. CA 기업은 CA 기업의 이름, 서버의 공개키, 서버의 정보 등을 기반으로 인증서르 ㄹ생성하고, CA 기업의 개인키로 암호화하여 A기업에게 이를 제공함
4. A기업은 클라이언트에게 암호화된 인증서를 제공함
5. 브라우저는 CA기업의 공개키를 미리 다운받아 갖고 있어, 암호화된 인증서를 복호화함
6. 암호화된 인증서를 복호화하여 얻은 A기업의 공개키로 데이터를암호화하여 요청을 전송함

추가적인 HTTPS의 장점은

검색엔진 최적화(SEO)에 있어서도 도움을 받는다.

4. 결론

개인 정보와 같은 민감한 데이터를 주고 받아야 한다면 HTTPS를 이용해야 하지만, 단순한 정보 조회 등만을 처리하고 있다면 HTTP를 이용하면 된다

참고 : 

https://mangkyu.tistory.com/98

http://blog.wishket.com/http-vs-https-%EC%B0%A8%EC%9D%B4-%EC%95%8C%EB%A9%B4-%EC%82%AC%EC%9D%B4%ED%8A%B8%EC%9D%98-%EB%A0%88%EB%B2%A8%EC%9D%B4-%EB%B3%B4%EC%9D%B8%EB%8B%A4/

https://velog.io/@blackb0x/HTTPHTTPS%ED%86%B5%EC%8B%A0%EA%B3%BC-%EC%86%8C%EC%BC%93%ED%86%B5%EC%8B%A0

https://jeong-pro.tistory.com/89

def get_client_ip(request):
    x_forwarded_for = request.META.get('HTTP_X_FORWARDED_FOR')
    if x_forwarded_for:
        ip = x_forwarded_for.split(',')[0]
    else:
        ip = request.META.get('REMOTE_ADDR')
    return ip

참고 : https://stackoverflow.com/questions/4581789/how-do-i-get-user-ip-address-in-django

1. 세션이란?

웹 브라우저와 서버가 HTTP 프로토콜을 통해서 하는 모든 커뮤니케이션은 무상태(stateless)라고 합니다. 메시지가 완벽하게 각각 독립적이라는 뜻이다.

그렇기에 우리는 사이트와 특정 브라우저 사이의 state를 유지시키기 위해서 세션을 사용한다. 세션은 매 브라우저마다 임의의 데이터를 저장하게 하고, 이 데이터가 브라우저에 접속할 때 마다 사이트에서 활용될 수 있도록 한다. 세션에 연결된 각각의 데이터 아이템들은 'key'에 의해 인용되고, 이는 또 다시 데이터를 찾거나 저장하는데 이용된다.

클라이언트 별 정보를 브라우저가 아닌 웹서버에 저장하는 것

웹브라우저에 저장 : cookie

웹서버에 저장 : session

session의 라이프 사이클은 브라우저에 의존한다. 같은 브라우저를 사용하고 있다면 링크를 통해서 다른 사이트로 이동해도 session_id는 유지가 된다. 하지만 브라우저를 닫으면 사라진다.

Django는 세션을 활용할때, session_id를 포함하는 쿠키를 사용해서 세션을 알아낸다.

2.설정

세션사용설정은 프로젝트 settings.py에서 아래와 같이 INSTALLED_APPS 와 MIDDLEWARE 부분에 있다.

INSTALLED_APPS = [ ... 'django.contrib.sessions', ....

MIDDLEWARE = [ ... 'django.contrib.sessions.middleware.SessionMiddleware', ....

3. 사용

세션은 request.session으로 바로 사용할 수 있다. dictionary 형식으로 key값을 넣어주면 된다.

# Get a session value by its key (e.g. 'my_car'), raising a KeyError if the key is not present
my_car = request.session['my_car']

# Get a session value, setting a default if it is not present ('mini')
my_car = request.session.get('my_car', 'mini')

# Set a session value
request.session['my_car'] = 'mini'

# Delete a session value
del request.session['my_car']

4. Session의 원리

1. 유저가 웹사이트에 접속
2. 웹사이트의 서버가 유저에게 session_id를 부여
3. 저의 브라우저가 이 session_id를 cookie에 보존
4. 통신할때마다 session_id를 웹서버에 전송
5. session_id에 의해 웹사이트는 많은 접속 유저중 특정 유저를 인식할 수 있음

5.Cookie란

웹사이트에서는 cookie를 사용해 유저의 로그인 상태를 유지하거나 유저의 사이트 이용설정을 기억시킵니다.

6. 캐시(Cache)란?

리소스 파일들의 임시저장소. 같은 웹 페이지에 접속할 때 사용자의 PC에서 로드하므로 서버를 거치지 않아도 된다. 자주 사용되는 데이터들은 빠르게 접근 가능하게 cache에 넣는다.

캐시 순서 : 

1. URL이 오면, 그 페이지를 먼저 캐시에서 찾는다.
2. 캐시에 있다. -> 캐시된 페이지를 보여준다.
3. 캐시에 없다. -> 페이지를 가져오고 캐시에 저장하고, 보여준다.

7. 캐시 설정

pip install django-redis

Settings.py에 설정을 해준다.

CACHES = {
    'default': {
        'BACKEND': 'django_redis.cache.RedisCache',
        'LOCATION': 'redis://{URL}:6379',
    },
}

아래는 캐시를 사용하는방법이다.

from django.core.cache import cache

def get_post_count():
        cache_key = 'my_blog_post_count'
        count = cache.get(cache_key, None)
        if not count:
            count = self._get_post_count()
            cache.set(cache_key, count, 60 * 60)
        return count

cache.get()을 통해 캐시에 접근하고,

cache.set()을 통해 캐시를 저장한다.

캐시는 Key-Value구조이다.

cache.set할때 마지막 인자값은 캐시의 유효기간이다. 

8. Redis

Key - Value 기반의 인-메모리 데이터 저장소입니다. 그래서 쿼리를 따로 할 필요없이 결과를 바로 가져올 수 있습니다. 디스크에 데이터를 쓰는 구조가 아니라 메모리에서 데이터를 처리하기 때문에 속도가 빠르다.

싱글 스레드라서 한번에 하나의 명력어만 실행할 수 있다.

Redis의 데이터 구조

1. Strings : 단순한 키-값 매핑 구조입니다.

2. Lists : Array형식의 데이터구조입니다. List를 사용하면 처음과 끝에 데이터를 넣고 빼는 것은 속도가 빠르지만 중간에 데이터를 삽입할 때는 어려움이 있습니다.

3. Sets : 순서가 없는 Strings 데이터 집합입니다. Sets에서는 중복된 데이터는 하나로 처리하기 때문에, 중복에 대한 걱정을 할 필요가 없습니다.

4. Sorted Sets : 위의 Sets와 같은 구조이지만, Score를 통해서 순서를 정할 수 있습니다. Sorted Sets를 사용하면 Leaderboard와 같은 기능을 손쉽게 구현하실 수 있습니다.

5. Hashes : 키-값의 구조를 여러개 가진 object 타입을 저장하기 좋은 구조입니다.

참조 : 

https://developer.mozilla.org/ko/docs/Learn/Server-side/Django/Sessions

https://valuefactory.tistory.com/708

https://ryusae.tistory.com/7

https://lee-seul.github.io/django/2019/05/02/django-cache-framework.html

http://milooy.github.io/TIL/Django/django-cache.html#%E1%84%8F%E1%85%A2%E1%84%89%E1%85%B5

추가적인 Cache 종류

https://dingrr.com/blog/post/django-seo-%EB%8D%94-%EB%B9%A0%EB%A5%B4%EA%B2%8C-cache%EC%99%80-%EC%95%95%EC%B6%95

Redis 정리

https://brunch.co.kr/@jehovah/20

0. 프록시란?

간단히 말해서 "중계 서버"입니다.

클라이언트와 서버간 통신을 직접하지 않고 중계 서버인 프록시 서버를 사용하여 보안, 트래픽 분산 등의 여러 장점을 가질 수 있습니다.

또한 포록시 서버는 서버로 요청된 내용을 캐시 해 놓고 동일한 요청시 바로 응답을 주도록 설정할 수도 있어서 시간과 리소스 사용을 절약할 수 있습니다.

1. Reverse Proxy (리버스 프록시)

1. 정보

클라이언트 (USER)가 인터넷에 데이터를 요청 -> 리버스 프로시가 요청을 받음 -> 내부 서버에 데이터를 요청하고 리버스 프록시가 데이터를 받음 -> 클라이언트에게 전달함

클라이언트는 내부 서버에 대한 정보를 알 필요 없이 리버스 프록시에게 요청만 함.

클라이언트가 요청하는 End Point가 프록시 서버의 도메인이고 실제 서버의 정보는 알 수 없음.

2. 장점

내부 서버에 대한 설정으로 로드 밸런싱(Load Balancing)이나 서버 확장 등에 유리함

서버가 감춰짐 -> 실제 서버의 정보를 알수가 없음 -> 보안 Good

웹서버가 해킹당해도 웹 서버 권한으로는 내부망으로 연결이 불가함

2. Foward Proxy (포워드 프록시)

1. 정보

클라이언트 (USER)가 프록시 서버에 요청을 함 -> 프록시 서버가 인터넷에 요청을 보냄 -> 인터넷이 내부 서버에 데이터를 요청하고 데이터를 받음 -> 클라이언트에게 전달함

클라이언트가 요청하는 End Point가 실제 서버 도메인이고 프록시는 둘 사이의 통신을 담당해줌

2. 장점

프록시 서버는 Cache를 사용하여 자주 사용하는 데이터는  요청을 보내지 않고 캐시에서 가져올 수 있어서 속도가 빠름

정해진 사이트만 연결하게 설정하는 등 웹 사용 환경을 제한 할 수 있으므로 기업 내부 환경 등에서 많이 사용함

클라이언트가 감춰짐 -> 서버는 포워드 프록시 서버를 통해서 요청을 받아서 클라이언트의 정보를 알 수 없음

3. 정리

망 내에서 외부로의 서비스 이용 -> 포워드 프록시

망 밖에서 내부로의 서비스 이용 -> 리버스 프록시

프록시 서버를 사용하면 HTTPS의 인증서 관리를 하나의 프로시 서버가 담당하고 뒤에 동작하고 있는 서버는 HTTP로 서비스 할 수 도 있어서 인증서 관리에 용이함

사진 출처 : https://www.imperva.com/

참조 :

https://bcp0109.tistory.com/194

https://sb.pe.kr/7371

https://firework-ham.tistory.com/23

대학교에서 펄어비스와 연계해서 오피스 채용설명회를 다녀오게 되었다. 간단하게 3시간정도 일정이였는데, 게임산업 및 펄어비스 복지, 회사에 관련된 것을 많이 알게된 것 같아서 공유를 해보려고 한다. 

1. 펄어비스 소개

펄어비스 회사에 대한 소개를 들었다. 회사의 유래, 어떤 게임이 있는지, 특징, 복지는 어떤 것이 있는지 상세하게 들을 수 있었다. 그 중 인상깊었던 것들을 정리해보았다.

펄어비스 (PEARL ABYSS)의 뜻 :

심연의 진주, 아무나 찾을 수 있는 게임이 아닌 심연의 진주처럼 힘든 것을 찾아내고 가꾸어 간다는 의미

인재상 : 

집요 - 포기하지 않고, 합리화하지 않고 목표치에 도달하는 열정

야성 - 항상 최선을 다하고 누구보다도 더 성장

신뢰 - 함께하는 동료를 믿고 자기 할일에 더 최선을 다하고 마무리 할 수 있는 사람

특징 : 

솔선수범 -> 열정 + 책임의식

일을 재미있게 함

2. 점심식사 & 선배사원과의 만남

펄어비스는 구내식당(펄식당)이 따로 있고, 맛있기로 유명하다고 한다. 실제로 2가지 메뉴 + 다이어트 식단까지 푸짐하고 맛있는 점심이였고, 우리 학교 대선배님들과 함께 식사를 하면서 이야기를 하였다. 칸막이가 있어서 많이 대화는 못했지만, 학교 선배들을 만나서 기분이 좋았다. 

3. 부서소개 및 선배 사원과의 시간

현재 출시 준비중인 "붉은 사막"을 어떻게 개발하고, 관리하고 있는지 실제로 툴을 통해 보여주고, 시연해주었다. 그리고 Q&A를 통해 다양한 궁금증을 해소해주었다. 그 중 인상 깊었던 질문들을 정리해보았다.

Q. 게임 개발자가 되려면 현재 어떤 것을 준비해야될까요?

A. 게임개발자가 되려면, 현재는 학과 공부를 충실히 하고, 팀플은 꼭 해보는 것이 좋다. 당사는 C,C++에 대한 기본이 되어있으면 더 좋다.

Q.포트폴리오나 면접준비를 어떻게 하면 좋을까요?

A. 게임관련 포트폴리오가 꼭 필요한 것은 아니다. 어떤 프로젝트를 하던 문제 해결능력이 중요하다. 왜 그걸 썼고, 이해하고 썼는지가 중요함. 1개만 제대로 해도 인정해주는 경우가 많음. 질문에 대답할 수 있을 정도로

Q.펄어비스의 장점

A. 함께 하는 문화가 잘 되어있고, 어디서든 배울점이 매우 많다. 또한 복지가 좋고, 정말 힘든 것 말고는 모두 좋은 회사인것 같다.

4. 마무리

사실 나는 게임 개발에는 관심이 별로 없었는데, 최근 게임 개발사들의 트렌드, 어떻게 준비해야되는지 상세히 듣고나니 흥미가 생기기도 하였다. 무엇보다도 눈에띄었던 것은 복지가 정말 좋다는 것이였는 듯하다. 비가 오는 날이였지만, 정말 좋은 회사를 알게 된 것 같아서 기분이 좋았다.

이전다음

01

1. 연산자 끼워넣기

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1 복사

2 5 6 0 0 1 0

예제 출력 1 복사

30 30

예제 입력 2 복사

3 3 4 5 1 0 1 0

예제 출력 2 복사

35 17

예제 입력 3 복사

6 1 2 3 4 5 6 2 1 1 1

예제 출력 3 복사

54 -24

힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.

• 최댓값: 1-2÷3+4+5×6
• 최솟값: 1+2+3÷4-5×6

해결 방법 : brute force

이유 : 

문제가 백트래킹 문제영역에 있어서 어떻게 할지 계속 생각하다가, 그냥 브루트 포스로 일단 다 돌려봐야겠다라고 생각하고 정리했는데 되버렸다.. 참고자료는 코드 향상에 도움을 주려고 찾아봄

참고 자료 :

daimhada.tistory.com/93

문제 : 

www.acmicpc.net/problem/14888

import sys
input = sys.stdin.readline
 
def cal(num, idx, add, sub, multi, division):
    global n, maxv, minv
    if idx == n:
        maxv = max(num, maxv)
        minv = min(num, minv)
        return
    else:
        if add:
            cal(num + num_list[idx], idx + 1, add-1, sub, multi, division)
        if sub:
            cal(num - num_list[idx], idx + 1, add, sub-1, multi, division)
        if multi:
            cal(num * num_list[idx], idx + 1, add, sub, multi -1, division)
        if division:
            cal(int(num/num_list[idx]), idx + 1, add, sub, multi, division -1)
 
 
if __name__ == "__main__":
    maxv = -sys.maxsize - 1
    minv =  sys.maxsize
    n = int(input().strip()) # 숫자의 수
    num_list = list(map(int, input().strip().split()))
    a, b, c, d = map(int, input().strip().split())
    cal(num_list[0], 1, a, b, c, d)
    print(maxv)
    print(minv)


출처:  [Daim's blog]

1.  N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 복사

8

예제 출력 1 복사

92

해결 방법 : 백트래킹

이유 : 

백트래킹은 전체적으로 DFS를 하는 부분 + 문제별로 제한사항을 두는 코드 이렇게 두개를 짜는듯. 결국 DFS는 코드는 비슷하고 제한사항을 어떻게 할지는 노가다 조금만 해봐도 가능할듯. 아직 재귀가 부족해서 시간은 오래걸렸음

참고 자료 : claude-u.tistory.com/245

문제 : 

www.acmicpc.net/problem/9663

def adjacent(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True
        
        
#한줄씩 재귀하며 DFS를 실행
def dfs(x):
    global result
    
    if x == N:
        result += 1

    else:
        for i in range(N):
            row[x] = i
            if adjacent(x):
                dfs(x + 1)

N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)

1. N과 M (2)

해결 방법 : 백트래킹

이유 : 

그냥 저번 코드에서 조건만 변경하면 완료. 백트래킹에 대한 지식 필요

참고 자료 : X

문제 : 

www.acmicpc.net/problem/15650

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

def f(s):
  if len(s) == m:
      if s == sorted(s):
        print(' '.join(map(str, s)))
        return

  for i in range(1, n + 1):
    if i in s:
      continue
    f(s + [i])

f([])

2. N과 M (3)

해결 방법 : 백트래킹

이유 : 

그냥 저번 코드에서 조건만 변경하면 완료. 백트래킹에 대한 지식 필요

참고 자료 : X

문제 : 

www.acmicpc.net/problem/15651

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

def f(s):
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    f(s + [i])

f([])

1. N과 M (1) - 백준

해결 방법 :

백트래킹

이유 : 

DFS의 백트래킹을 사용해야됨. 키워드는 들어왔는지를 확인하고, 추가해주고, 검사하고, 다시 빼주는 것을 재귀처럼 계속 돌리면서 원하는 값이 나올때까지 brute force를 하는데 가지치기를 좀 한 방법인듯

참고 자료 :

jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/

leejunggae.tistory.com/19

문제 : 

www.acmicpc.net/problem/15649

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

def f(s):
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i in s:
      continue
    f(s + [i])

f([])