어느날 Spring 서버 개발중 Controller를 만들 때, 자연스럽게 클래스위에 @RestController를 붙이고 있었다. 단순 REST API의 Controller 담당한다는 의미로만 생각했고, 의미를 정확하게 파악하지 못한채 사용하고 있었다. 그래서 RestController에 대해서 한번 알아보려 한다.

@Controller와 @RestController

Controller를 의미하는 어노테이션은 총 2가지가 있다고 한다. 하나는 @Controller, 다른 하나는 @RestController이다. 두개의 차이점을 분석하기 위해 어노테이션을 직접 확인해 봤다.

아래는 @Controller 인터페이스이다.

@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Component
public @interface Controller {

    /**
     * Alias for {@link Component#value}.
     */
    @AliasFor(annotation = Component.class)
    String value() default "";

}

아래는 @RestController 인터페이스이다.

@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Controller
@ResponseBody
public @interface RestController {
    @AliasFor(annotation = Controller.class)
    String value() default "";

}

자세히 보면 @RestController는 @Controller를 이미 포함하고 있다. 그런데 추가로 @ResponseBody가 있다. 즉 @RestController와 @Controller의 차이는 @ResponseBody 유무의 차이인 것이다. 그래서 @ResponseBody에 대해서도 확인을 해보았다.

아래는 @ResponseBody 인터페이스이다.

@Target({ElementType.TYPE, ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface ResponseBody {

}

@ResponseBody 인터페이스에 상위에 주석이 작성되어있는데, 아래와 같다.

Annotation that indicates a method return value should be bound to the web response body. Supported for annotated handler methods.
As of version 4.0 this annotation can also be added on the type level in which case it is inherited and does not need to be added on the method level.

즉, @ResponseBody 어노테이션을 붙이면 속한 메소드의 반환값을 http 응답 body에 넣어준다는 의미이다.

@Controller와 @RestController의 차이는 response data의 목적이라고 할 수 있다. @Controller는 Spring MVC에서 주로 View를 반환을 하는 데 목적이 있고, @RestController는 JSON 데이터 타입을 주로 반환하는데 목적이 있다. 추가로 @Controller에는 View Resolver가 동작하여 반환된 문자열을 기반으로 해당하는 뷰를 찾고, 그 뷰를 사용자에게 렌더링 한다고 한다. 즉, 나는 프론트, 백엔드가 나뉘어져 백엔드 데이터만 전달하는 역할을 해왔기 때문에 @RestController를 자연스럽게 사용을 했던 것 같다.

정리

Spring MVC와 같이 View를 반환해야 한다면 @Controller를 사용하고, 데이터 전달이 목적이라면 @RestController를 사용하면 된다.

객체지향에 대해서 이야기하는데, 스프링의 핵심에 대해서 이야기 하는 이유는 무엇일까? 우리가 생각하는 스프링의 핵심은 무엇일까? 단지 웹 애플리케이션을 만들고, DB 접근을 해서 데이터를 전달해주는 것일까? 스프링의 진짜 핵심은 좋은 객체 지향 애플리케이션을 개발할 수 있게 도와주는 프레임워크이다. 좋은 객체 지향 설계를 위해서는 객체 지향 설계에 대해서 잘 알아야 한다.

객체 지향 특징

객체 지향의 특징으로는 4가지가 있다.

• 추상화 : 객체의 특징을 잡아서 설명하는 것
• 캡슐화 : 데이터와 메서드를 하나의 단위로 묶어, 외부에서 접근하지 못하도록 보호하는 것
• 상속 : 여러 개체들이 지닌 공통된 특성을 부각시켜 하나의 개념으로 성립시키는 것
• 다형성 : 객체의 속성이나 기능이 상황에 따라 여러 가지 형태를 가질 수 있는 성질

다형성

다형성에 대해서 위에서 '객체의 속성이나 기능이 상황에 따라 여러 가지 형태를 가질 수 있는 성질'이라고 하였다. 아래 그림을 보면 더 이해가 될 것 이다. 자동차 서비스는 자동차 인터페이스를 바라보고 있다. 그리고 자동차 인터페이스는 내연차와 전기차로 구현되어 있다.

자동차 서비스에서 연료주입을 하는 경우 자동차 인터페이스만 보면 된다. 즉 내연차나 전기차의 연료주입 메서드를 모두 사용할 수 있다는 것이다.

다형성을 이용한다면 인터페이스를 구현한 객체 인스턴스를 실행 시점에 유연하게 변경할 수 있다.

인터페이스를 통해서 역할과 구현을 명확하게 분리할 수 있다. 이렇게 된다면 확장이 가능한 설계를 할 수 있다. 위에 정의한 자동차 인터페이스에 구현 클래스 추가가 용이하다. 뭐 예를 들자면 수소차가 있지 않을까 싶다. 즉 역할은 자동차이고, 구현은 인터페이스를 구현한 클래스가 될 것이다. 이렇게 역할과 구현이 명확하게 분리가 된다면 확장에 대해서 용이하다.

만약에 역할(인터페이스)자체가 변경이 된다면 많은 변경 비용이 발생한다. 자동차가 비행기로 변경이 된다면, 구현 클래스들은 모두 변경이 된다. 그러므로 역할(인터페이스)를 안정적으로 잘 설계하는 것이 중요하다.

좋은 객체 지향 설계의 5대 원칙

• SRP(Single Responsibiliy Principle) : 단일 책임 원칙
• OCP(Open Closed Principle) : 개방-폐쇄 원칙
• LSP(Liskov Substitution Principle) : 리스코프 치환 원칙
• ISP(Interface Segregation Principle) : 인터페이스 분리 원칙
• DIP(Dependency Inversion Principle) : 의존관계 역전 원칙

SRP

하나의 클래스는 하나의 책임만 가져야 한다. 하나의 클래스는 명확한 기준을 가져야 한다는 뜻이다. 자동차에 대한 클래스를 만든다면 자동차를 변수와 메서드를 가져야 하는 것이다. 기준에 대해서 더 생각을 해본다면 클래스에 대해서 변경이 있을 때, 변경점이 많이 발생하지 않는 다면 원칙을 잘 따른 것이다.

OCP

소프트웨어 요소에 확장은 열려 있으나 변경에는 닫혀 있어야 한다. 이때 다형성을 많이 사용한다. 인터페이스에 새로운 구현 클래스를 생성한다면, 확장에 열려 있고 변경에 닫혀 있는 것을 볼 수 있다. (ex 자동차 인터페이스에 수소차 구현 클래스를 추가하는 경우)

LSP

서브 타입은 언제나 자신의 기반 타입으로 교체할 수 있어야 한다. 즉 부모 객체를 호출하는 동작에서 자식 객체가 부모 객체를 완전히 대체할 수 있다는 원칙이다. 객체 지향 프로그래밍에서 상속이 일어나면, 하위 타입은 상위 타입의 특성을 가질 수 있으며, 그 특성을 토대로 확장할 수 있다. 올바른 상속을 위한 원칙이다.

ISP

클라이언트는 자신이 사용하지 않는 메서드에 의존 관계를 맺으면 안된다. 즉 특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다는 뜻이다. 예를 들어서 자동차 인터페이스를 생각 해보면, 자동차에 대해서 생각해보면 여러개가 있지만 대표적으로 운전하는 것, 정비하는 것이 있다. 자동차 인터페이스 자체를 운전/정비 인터페이스로 분리해서 관리하는 것이 더 명확해지고, 대체하기도 쉽다. 범용적인 인터페이스를 여러개로 분리해서 관리하자는 원칙이다.

DIP

고차원 모듈은 저차원 모듈에 의존하면 안된다. 즉 추상화에 의존해야지, 구체화에 의존하면 안된다는 뜻이고, 구현 클래스에 의존하지 말고, 인터페이스에 의존하라는 뜻이다. 인터페이스에 의존해야 유연하게 구현 클래스를 변경할 수 있다는 원칙이다.

마무리

스프링 프레임워크를 올바르게 사용하기 위해서 객체 지향에 대해서 공부를 해보았다.

참고자료

• 스프링 핵심 원리(기본편), 김영한
• 스프링 입문을 위한 자바 객체 지향의 원리와 이해

DBMS를 알기전에 DB에 대해서 알아야 한다. DB는 간단하게 말하면 데이터의 집합이다. 서버에서 비지니스 로직을 처리할 때, 데이터를 가져오거나 저장을 할 때가 있다. 이때 데이터를 가져오거나 저장을 하는 곳이 바로 DB이다.

개념

DBMS는 DB를 관리하고 운영하는 소프트웨어이다. 즉 DB에 접근할 수 있도록 인터페이스를 제공하는 소프트웨어이다. 데이터베이스를 구축하는 틀을 제공하며, 효율적으로 데이터를 검색, 저장, 업데이트 하는 기능을 제공합니다.

DBMS 특징

1. 데이터 무결성 : 부적절한 자료가 입력되어 동일한 내용에 대해 서로 다른 데이터가 저장되는 것을 허용하지 않는 성질.
2. 데이터 일관성 : C(생성), U(갱신), D(삭제)후에도 저장된 데이터가 이상한 것이 없고 일정해야하는 성질.
3. 데이터 회복성 : 장애가 발생한 경우 특정 상태로 복구되어야하는 성질.
4. 데이터 효율성 : 응답시간, 저장공간 활용들이 최적화 되어야하는 성질.

DBMS의 장점

DBMS의 특징들에 따라서 다양한 장점들이 있다. 그리고 DB에 대해서 동시 접근이 가능하도록 해준다. DBMS의 특징중 가장 중요한 것이 나는 데이터 무결성이라고 생각한다. DB에 저장된 데이터 값과 그것이 표현하는 실제 값이 일치할 수 있도록 유지해주는 것이 서버를 구축하는데 가장 중요하다 생각한다.

DBMS의 단점

DBMS의 단점으로는 우선 운영비가 증가하는 것이다. DBMS 종류중 상업적으로 사용하는 Oracle은 유료이다. 물론 MySQL와 같은 오픈 소스형 DBMS가 존재하기도 한다. 그리고 생각보다 복잡한 백업과 회복이다. 데이터베이스는 구조가 복잡하고, 여러 사용자들이 동시에 사용하기 때문에 장애가 일어났을 때 정확한 이유를 파악하는데 쉽지 않다. 그래서 백업 조치와 회복 기법을 정교하게 생각해야한다. 그러나 백업과 회복을 할 수 있는 것 자체가 다행인 점이기도 하다.

DBMS 종류

1. Oracle

• 오라클에서 만들어 판매중인 상업용 데이터베이스이다.
• 다양한 운영체제에서 설치 가능하다.
• MySQL보다 대용량 데이터 처리가 용이하다.
• 가장 널리 사용되는 RDBMS이다.

2. MySQL

• 오픈소스로 이루어진 무료 프로그램이다. 그러나 상업적으로 사용할 때는 비용이 발생한다.
• 다양한 운영체제에서 설치 가능하다.

3. MariaDB

• MySQL에서 나온 오픈소스형 RDBMS이다.
• MySQL과 동일한 소스코드 기반이다.
• MySQL과 비교하면 애플리케이션 속도가 더 빠르다고 한다.

DBMS 동작

Web Application Server에서 비지니스 로직을 처리하다가 DB에 있는 데이터를 가져오거나, 저장을 해야할 때 우리는 DBMS를 사용한다. 즉 위에서 말한 것 처럼 WAS와 DB의 중간다리 소프트웨어 역할을 한다. 서버에서 DB의 데이터를 가져올 수 있는 이유는 DBMS의 존재이기 때문으로 알면 좋을 것 같다.

마무리

DBMS에 대해서 연구를 해보았다. 다음에는 Spring Boot에 대해서 포스팅을 할 예정이다.

참고자료

• https://m.blog.naver.com/sundooedu/221301384166
• https://konkukcodekat.tistory.com/24
• https://developer-yeony.tistory.com/18
• https://runcoding.tistory.com/4

Web Application Server(WAS)는 웹 애플리케이션과 서버 환경을 만들어 동작시키는 기능을 제공하는 소프트웨어 프레임워크이다. 간단하게 이야기 하자면 Web Client(웹 브라우저)로부터 Web Server가 요청을 받으면 애플리케이션에 대한 로직을 실행하여 Web Server로 다시 반환해주는 소프트웨어이다. Web Server와 Database 사이에서 동작하는 미들웨어이다.

Web Server와 Web Application Server의 차이

• Web Server는 간단한 요청에 대한 응답을 주지만, Web Application Server는 애플리케이션에 대한 서비스 및 Database에 연결해서 동적인 컨텐츠를 만드는 비지니스 로직 처리할 수 있다.
• Web Server는 정적인 콘텐츠인 HTML, 이미지, 파일과 같은 데이터를 주지만, Web Application Server는 애플리케이션의 서비스에 특화된 동적 데이터를 준다.

작동원리

Web Application Server는 아래와 같은 작동 원리를 갖는다.

1. Web Server는 Web Client(웹 브라우저)로부터 받은 request를 Web Application Server에 전달한다.
2. request를 전달받은 Web Application Server는 비지니스 로직을 처리를 하고, 필요하다면 Database에서 데이터를 가져온다.
3. Web Application Server에서 비지니스 로직을 모두 수행한다면, Web Server에게 response를 전달한다.
4. response를 전달받은 Web Server는 Web Client(웹 브라우저)에게 전달한다.

위 사진을 보면서 작동 원리에 대해서 설명을 하겠다.

• [작동원리1] Web Server는 정적인 데이터에 대해서 처리가 가능하므로 동적인 데이터 요청을 받은 경우 request를 Web Application Server에 전달한다.
• [작동원리2] Web Application Server는 전달받은 request를 토대로 비지니스 로직을 처리한다. Database의 데이터를 가져오거나 변경하는 경우 Database를 사용한다.
• [작동원리3] Web Application Server에서 비지니스 로직을 모두 완료한다면, response를 만들어서 Web Server에 전달한다.
• [작동원리4] Web Server에서 response를 전달을 받아서 그대로 Web Client(웹 브라우저)에 전달한다.

Web Server와 Web Application Server를 같이 사용하면 좋은 이유

사실 Web Application Server만 사용해서 Web Server의 역할을 동시에 수행할 수 있다. 그러나 통상적으로 Web Server와 Web Application Server를 따로 구성해서 Server를 셋팅하는 것이 좋다.

간단한 이유는 Web Server와 Web Application Server의 차이인 정적 컨텐츠를 다루는지, 동적 컨텐츠를 다루는지다. 부하가 많은 서비스인데 정적 컨텐츠를 Web Application Server에서 다루게 된다면 불필요하기 때문에, 정적인 컨텐츠는 Web Server에 위임을 한다.

Web Application Server는 Database와 연결이 되어있고, ssl 보안 적용이 어렵다. Web Server의 대표적인 nginx의 설정파일에서 ssl 보안을 적용할 수 있다. 그래서 보안적으로 더 안전하다.

Web Server에 여러대의 Web Application Server를 연결해서 사용할 수 있다. 실제 nginx server 블록에서 여러 대의 Web Application Server를 연결할 수 있다. 그래서 로드 밸런싱 역할을 수행할 수 있다.

종류

Web Application Server는 다양한 종류들이 있다.

• apache tomcat
• Jetty
• Jeus

Spring boot

Spring boot는 대표적인 서버 프레임워크이다. Spring boot는 Web Application Server를 따로 설정하지 않아도 된다. 그 이유는 tomcat 서버가 내장되어 있다. 그래서 Web Application Server에 대해서 전혀 신경을 쓰지 않아도 된다. Spring boot 산출물은 jar 파일인데, 이 안에 tomcat 서버가 내장되어 있다.

마무리

Web Application Server에 대해서 연구를 해보았다. 다음에는 DBMS에 대해서 포스팅을 할 예정이다.

참고자료

• https://ko.wikipedia.org/wiki/%EC%9B%B9_%EC%95%A0%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98_%EC%84%9C%EB%B2%84
• https://aws.amazon.com/ko/compare/the-difference-between-web-server-and-application-server/
• https://goldsony.tistory.com/37

사전적인 개념으로는 Web Server 소프트웨어는 클라이언트의 요청을 처리하고, 저장된 웹 페이지를 찾아 전송하는 역할을 한다고 한다. 간단하게 이야기를 하면 Web Client(사용자 브라우저)로부터 가장 먼저 http 프로토콜 Request를 받는 곳으로 알면 될 것 같다. Web Client는 정적파일(대표적으로 웹 페이지가 있고, 이미지 파일들도 있을 수 있다.)들을 다루고, 추후에 작성할 Web Application Server는 동적인 데이터들을 다룬다.

작동원리

Web Server는 아래와 같은 작동 원리를 갖는다.

1. Web Client가 Web Server에게 정적파일인 웹 페이지를 요청한다.
2. Web Server는 지정된 위치에서 웹 페이지를 찾아 Web Client에게 전송한다.
3. Web Client는 Web Server로부터 받은 데이터를 사용자 브라우저에 띄운다.

위 사진을 보면서 작동 원리에 대해서 설명을 하겠다.

• [작동원리1] Web Client(사용자 브라우저)가 Web Server에서 정적파일을 달라고 http 프로토콜을 이용해서 Request(요청)을 보낸다.
• [작동원리2] Web Server는 정적파일에 대한 Request(요청)을 받았으므로 Web Application Server에 전달하지 않고, Web Server에서 정적 파일 위치에 접근해서 정적 파일 데이터를 Web Client(사용자 브라우저)에게 Response(응답)를 보낸다.
• [작동원리3] Web Client(사용자 브라우저)는 Web Server로 부터 전달받은 정적파일을 띄운다.

종류

웹 서버는 다양한 종류들이 있다.

• Apache
• Nginx
• Microsoft IIS

여기서 Nginx를 가지고 간단하게 웹 서버 구축하는 것을 실습해볼 예정이다.

실습

셋팅은 Ubuntu 20.04에서 진행할 예정이다. Nginx를 설치하기전 이전 패키지들에 대해서 업데이트를 해준다.

sudo apt upgrade
sudo apt update

Nginx를 설치한다.

sudo apt install nginx

Nginx를 설치하면 AWS의 EC2환경이든, 그냥 Ubuntu PC든 인바운드와 아웃바운드 규칙을 설정해줘야한다. 필자는 Ubuntu PC이기 때문에 방화벽 설정 명령어인 ufw를 통해서 진행하겠다.

sudo ufw app list
sudo ufw allow 'Nginx HTTP'

위 명령어를 입력하고 난 뒤 아래 명령어를 통해 체크합니다.

sudo ufw status

만약에 Status가 inactive면 아래 명령어를 통해 변경합니다.

sudo ufw enable

그런 다음 작업한 PC의 IP주소를 입력하면 다음과 같은 화면을 볼 수 있다.

이 글은 Nginx를 위한 글이 아니므로, Nginx관련 명령어는 따로 보는 것을 추천한다. 나는 어떻게 IP주소를 입력했는데, 위 사진의 화면이 나왔는지에 대해서 설명을 할 예정이다.

Nginx Web Server관련 설정은 아래 위치에 있다.

cd /etc/nginx/sites-available
vim default

아무 설정도 진행하지 않았다면 아래 사진과 같이 default 파일이 설정되어 있을 것이다.

위 설정 파일은 http 포트인 80번 포트의 요청이 들어왔을 때, Web Server에서 처리 방법에 대해서 작성하는 곳이다. 우리는 여기서 root와 index에 대해서 집중을 할 것 이다. root는 웹 서버의 시작 지점을 의미한다. 그리고 index는 어떤 정적 파일을 줄지를 의미한다. 순서대로 index.html, index.htm, index.nginx-debian.html이 있고 이는 우선순위를 의미한다. 그러면 IP주소를 쳤을 때 root 경로에 index에 작성되어 있는 파일명이 있는지 확인할 필요가 있다. 그래서 아래 명령어를 통해 root 지점으로 이동해보자.

cd /var/www/html
ls

위 명령어들을 치니 아래와 같은 사진 결과를 볼 수 있다.

root 경로에 3순위였던 index.nginx-debian.html 파일이 있었다. 즉 IP주소를 입력했을 Welcome to Nginx가 적힌 웹 페이지가 노출 된 이유는 default 파일의 설정이 index.nginx-debian.html이라는 정적파일을 주도록 되어 있기 때문이다.

마무리

이로써 직접 실습을 해보며 Web Server의 역할에 대해서 연구를 해보았다. 다음에는 Web Application Server에 대해서 포스팅을 할 예정이다.

[참고자료]

• https://developer.mozilla.org/ko/docs/Learn/Common_questions/Web_mechanics/What_is_a_web_server
• https://dev-bucks.tistory.com/entry/%EC%9B%B9%EC%84%9C%EB%B2%84Web-Server-%EC%9D%B4%ED%95%B4%EC%99%80-%EC%9E%91%EB%8F%99%EC%9B%90%EB%A6%AC
• https://story.pxd.co.kr/1647
• https://jaehyeon48.github.io/nginx/configure-nginx-on-ubuntu-2004/

문제설명

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

• 원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
• 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.

예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.

제한사항

• 1 ≤ k ≤ 1,000,000
• 1 ≤ d ≤ 1,000,000

입출력 예1

Input : 2, 4
Output : 6

입출력 예2

Input : 1, 5
Output : 26

문제풀이1 (시간초과)

해당 문제에 대해서 BFS 탐색으로 접근을 하였다. (0, 0)좌표부터 시작해서 방문한 이력이 있는지 체크하고, 4방향으로 이동하면서 거리가 d보다 작은지 체크를 했다. 문제는 풀 수 있었지만, 제한사항을 보면 k와 d가 1,000,000까지이다. 즉, 시간 초과가 나타날 수 밖에 없었다. 그래서 더 간소화하게 풀어야함을 느꼈다.

코드1 (시간초과)

import math
from collections import deque

# 경계선 체크
def checkBorder(x, y, max):
    if x < 0 or x > max or y < 0 or y > max:
        return False
    return True


# 거리 구하는 함수
def getDistance(x, y):
    return math.sqrt((x - 0) ** 2 + (y - 0) ** 2)


# bfs 탐색
def bfs(x, y, visited, k, d):
    dx = [-1, 1, 0, 0]  # x방면 이동
    dy = [0, 0, -1, 1]  # y방면 이동

    queue = deque()  # 큐 생성
    queue.append((x, y))  # 큐 삽입
    visited[x][y] = 1  # 방문 기록
    result = 1  # 정답 1로 초기화

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            na = a + (dx[i] * k)  # k만큼 이동
            nb = b + (dy[i] * k)  # k만큼 이동

            if checkBorder(na, nb, d):
                if visited[na][nb] == 0 and getDistance(na, nb) <= d:  # 방문한 적 없고, 거리가 d미만인 경우
                    queue.append((na, nb))  # 큐삽입
                    visited[na][nb] = 1  # 방문 기록
                    result += 1  # 정답 추가

    return result


# 한개빼고 시간 초과
def solution1(k, d):
    answer = 0
    visited = [[0] * (d + 1) for _ in range(d + 1)]
    answer = bfs(0, 0, visited, k, d)

    return answer

print(solution1(2, 4))
print(solution1(1, 5))

문제풀이2 (시간초과)

제한사항을 보고 BFS탐색을 쓰면 안되겠다 생각을 해서 x좌표에 대해서 먼저 생각하기로 했다. 두 좌표 (x1, y1), (x2, y2)사이의 거리는 아래와 같다.

d^2 = (x2 - x1)^2 + (y2 - y1)^2

위 식을 이용해서 x값을 이용해서 나올 수 있는 최대 y값을 이용해 for문으로 탐색하며 해결하고자 했다. 코드는 아래와 같다.

코드2 (시간초과)

import math

# 4개빼고 시간 초과
def solution2(k, d):
    answer = 0

    for x in range(0, d + 1, k):  # k step만큼 비교
        maxY = math.floor(int(math.sqrt(d ** 2 - x ** 2)))  # 최대 max y값은 d(거리)^2 - x의 좌표^2의 루트하고 내림한 값
        for y in range(0, maxY + 1, k):  # k step만큼 허용 y값 추가
            answer += 1

    return answer

print(solution2(2, 4))
print(solution2(1, 5))

문제풀이3 (정답)

생각해보니 굳이 for문을 쓸 필요가 없었다. 최대 y값이 나온다면 그 값을 k로 나눠서 몫 + 1을 하면 됐다. 1을 더하는 이유는 x좌표 0을 위해서이다. 코드는 아래와 같다.

코드3 (정답)

import math

# 성공
def solution3(k, d):
    answer = 0

    for x in range(0, d + 1, k):
        maxY = math.floor(int(math.sqrt(d ** 2 - x ** 2)))   # 최대 max y값은 d(거리)^2 - x의 좌표^2의 루트하고 내림한 값
        answer += (maxY // k) + 1  # k 스템만큼 나누고 난 뒤 더하기 1(y좌표가 0인 경우 추가)

    return answer

print(solution3(2, 4))
print(solution3(1, 5))

문제 설명

마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.

마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.

마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 1 ≤ storey ≤ 100,000,000

입출력 예1

Input : 16
Output : 6

입출력 예2

Input: 2554
Output : 16

문제풀이

이 문제는 설명에 답이 나와있다. 16인 경우 엘리베이터를 1만큼 6번 내려간 다음 10만큼 1번 내려가는 것보다 1만큼 4번 올라간 다음에 10만큼 2번 내려가면 더 편하다고 한다. 즉, storey를 10으로 나눴을 때 나머지가 6이상인 경우에는 무조건 올라가는 것이 더 좋다. 그리고 5이하인 경우에는 내려가는 것이 더 좋다. 그러나 딱 5인 경우에 대해서 문제가 발생한다. 숫자 95를 생각해보자. 5이하인 경우 내려가는 것을 생각하게 된다면 95에서 1만큼 5번 내려가고, 10만큼 1번 올라가고, 100만큼 1번 내려가면 총 7번이 든다. 그러나 1만큼 5번 올라가고, 100만큼 1번 내려가면 6번으로 더 적게 든다. 즉, 나머지가 5인 경우에 앞의 숫자에 따라 달라진다. 나머지가 딱 5인 경우 앞의 숫자가 5이상인 경우에는 올라가는 것이 더 이득이다. 그래서 아래와 같이 코드를 설계했다.

코드

def solution(storey):
    answer = 0

    while storey:
        num = storey % 10

        if num > 5:  # 5보다 큰 경우
            storey += 10 - num
            answer += 10 - num
        elif num == 5 and (storey // 10) % 10 >= 5:  # 5이면서 앞의 자리 숫자가 5와 크거나 같은 경우
            storey += 10 - num
            answer += 10 - num
        else:  # 5 이하인 경우
            answer += num

        storey //= 10

    return answer

solution(16)
solution(2554)
solution(95)

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한 사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

입출력 예1

입력

[2, 3, 3, 5]

출력

[3, 5, 5, -1]

입출력 예2

입력

[9, 1, 5, 3, 6, 2]

출력

[-1, 5, 6, 6, -1, -1]

문제 풀이1(시간 초과 방식)

우선 해당 원소의 뒤에 있는 배열중 가장 가깝게 큰 것을 찾는 문제라서, numbers에서 하나의 원소를 고르고 난 뒤, 그 뒤부터 쭉 검사를 했고 가장 먼저 큰 수를 찾으면 answer 배열에 삽입을 했다. 그러다 마지막 원소가 된다면 answer 배열에 -1을 삽입했다. 작은 표본에서는 이게 성립이 되지만, numbers의 길이는 최대 100,000 이었다. 위와 같은 방식을 채택했다면 어마어마한 시간이 걸릴 것 이었다.

코드1(시간 초과 방식)

# 시간 초과
def solution1(numbers):
    answer = []
    count = 0
    lenNumbers = len(numbers)
    for item in numbers:
        count += 1
        if item == max(numbers):
            answer.append(-1)
            continue

        if count == lenNumbers:
            answer.append(-1)
        else:
            flag = False
            for i in range(count, lenNumbers):
                if item < numbers[i]:
                    answer.append(numbers[i])
                    flag = True
                    break

            if flag == False:
                answer.append(-1)

    return answer

print(solution1([2, 3, 3, 5]))
print(solution1([9, 1, 5, 3, 6, 2]))

문제 풀이2

stack을 사용해서 하면 좋을 것 같다는 생각이 들었다. 스택을 사용하면서 얻는 이점은 같은 값을 갖는 원소에 대해서 문제 풀이1과 같은 방법을 하지 않아도 된다. 이게 무슨 뜻이냐면 입출력 예1의 경우 1, 2번 인덱스의 3에 대해서 뒤의 원소들을 추가 분석할 필요가 없다는 뜻이다. 스택에 비교하고자 하는 인덱스를 넣고, 스택이 비어있지 않다면 비교하는 방식을 채택하면 된다. 그러면 스택에 쌓여있는 수들은 모두 뒷 큰수를 만나면 answer 배열을 변경해주기만 하면 되기 때문이다.

코드2

def solution2(numbers):
    stack = []
    answer = [0] * len(numbers)

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:  # 스택이 있는 경우 그리고 그 스택의 가장 위 값이 비교하는 숫자보다 작은 경우
            answer[stack.pop()] = numbers[i]  # 정답 인덱스에 작은 숫자 삽입
        stack.append(i)  # 스택에 인덱스 삽입
    while stack:  # 마지막 원소에 대해서 -1 처리
        answer[stack.pop()] = -1

    return answer

print(solution2([2, 3, 3, 5]))
print(solution2([9, 1, 5, 3, 6, 2]))

설명

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우였다. 하지만 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 다익스트라 알고리즘은 출발 노드가 1개이고 다른 모든 노드들의 거리를 저장하기엔 1차원 리스트를 사용했지만, 플로이드 워셜 알고리즘은 모든 지점에서 다른 지점까지의 최단 경로를 저장하기 때문에 2차원 리스트를 사용해야 한다. 플로이드 워셜 알고리즘은 어디를 거쳐 간다는 것이 가장 중요하다. 즉, 각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다. 다익스트라는 그리디 알고리즘이라고 했지만, 플로이드 워셜 알고리즘은 거쳐가는 것을 고려하여 최단 거리를 출력하기 때문에 다이나믹 프로그래밍과 관련이 있다.

설명 예시

1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우르 고려하면 된다. 즉, A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. (A, B는 임의의 노드)

점화식

플로이드 워셜 알고리즘은 다이나믹 프로그래밍이므로 아래와 같은 점화식을 도출할 수 있다.

dp[a][b] = min(dp[a][b], dp[a][k] + dp[k][b])

소스코드

import sys

INF = int(1e9)

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 가는 값은 0으로 초기화
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

for _ in range(m):
    # A에서 B로 가는 비용은 C
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == INF:
            print("INFINITY", end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

# 예제
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2

설명

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 입니다. 다익스트라 알고리즘은 그리디 알고리즘으로 분류가 됩니다. 그 이유는 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다.

원리

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
5. 위 과정에서 3번과 4번을 반복합니다.

즉, 매번 최단 거리를 선택해서 진행을 하면 된다.

** 최단 거리 테이블 : 출발 노드에 대해서 각 노드에 도달하는데 걸리는 최단 거리 정보를 저장하는 테이블. 1차원 리스트로 관리한다.

우선순위 큐

다익스트라는 항상 거리가 짧은 간선을 선택하는 알고리즘이다. 우선순위 큐는 항상 가치가 높은 물건 데이터를 꺼낼 수 있다. 즉 여기서 가치가 높은 것은 거리가 짧은 것이다. 우선순위 큐를 통해서 항상 짧은 간선을 추출할 수 있다면 시간 복잡도를 더 줄일 수 있다.

구현

원리를 토대로 위의 사진의 start가 1인 경우의 다익스트라 알고리즘을 설계했다.

소스코드

import heapq
import sys

INF = int(1e9)

n, m = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline().strip())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 시작 노드로 가기 위한 최단 경로는 0이고 큐에 삽입
    distance[start] = 0  # 시작 노드 최단 경로는 0

    while q:
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 추출
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            continue
        # 현재 노드와 연결된 다른 인접한 노드들 확인
        for item in graph[now]:
            cost = dist + item[1]  # 현재 노드 거쳐서 다른 노드로 이동하는 비용

            if cost < distance[item[0]]:  # 현재 노드를 거쳐서 다른 노드로 이동하는 비용이 더 작은 경우
                distance[item[0]] = cost  # 비용 최신화
                heapq.heappush(q, (cost, item[0]))  # 큐 삽입

dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:  # 접근할 수 없다면
        print('INFINITY')
    else:
        print(distance[i])  # 접근할 수 있다면

# 예제
# 6 11
# 1
# 1 2 2
# 1 3 5
# 1 4 1
# 2 3 3
# 2 4 2
# 3 2 3
# 3 6 5
# 4 3 3
# 4 5 1
# 5 3 1
# 5 6 2
# 3 3 4
# 3 3 5

출처

이것이 취업을 위한 코딩 테스트다 with 파이썬

문제 설명

고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다.

예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다.

모든 달은 28일까지 있다고 가정합니다. 다음은 오늘 날짜가 2022.05.19일 때의 예시입니다.

• 첫 번째 개인정보는 A약관에 의해 2021년 11월 1일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보입니다.
• 두 번째 개인정보는 B약관에 의해 2022년 6월 28일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능합니다.
• 세 번째 개인정보는 C약관에 의해 2022년 5월 18일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보입니다.
• 네 번째 개인정보는 C약관에 의해 2022년 5월 19일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능합니다.

따라서 파기해야 할 개인정보 번호는 [1, 3]입니다. 오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies가 매개변수로 주어집니다. 이때 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냅니다.
• 1 ≤ terms의 길이 ≤ 20
  • terms의 원소는 "약관 종류 유효기간" 형태의 약관 종류와 유효기간을 공백 하나로 구분한 문자열입니다.
  • 약관 종류는 A~Z중 알파벳 대문자 하나이며, terms 배열에서 약관 종류는 중복되지 않습니다.
  • 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다.
• 1 ≤ privacies의 길이 ≤ 100
  • privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냅니다.
  • privacies의 원소는 "날짜 약관 종류" 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열입니다. 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어집니다.
  • privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어집니다.
• today와 privacies에 등장하는 날짜의 YYYY는 연도, MM은 월, DD는 일을 나타내며 점(.) 하나로 구분되어 있습니다.
  • 2000 ≤ YYYY ≤ 2022
  • 1 ≤ MM ≤ 12
  • MM이 한 자릿수인 경우 앞에 0이 붙습니다.
  • 1 ≤ DD ≤ 28
  • DD가 한 자릿수인 경우 앞에 0이 붙습니다.
• 파기해야 할 개인정보가 하나 이상 존재하는 입력만 주어집니다.

입출력 예

문제 풀이

해당 문제는 단순 구현, 문자열 문제이다. 각 개인정보 처리 방침에 따라서 파기 기간이 정해져 있고, 그 기간이 넘으면 파기된 것으로 취급하면 된다. 하지만 주의해야할 점은 12월에서 기간이 12인 경우이다. 12월에서 12를 더하면 24가 되어서 12의 나머지는 0월이 되기 때문이다.

코드

def checkValidation(terms, item, today):
    duration = ''
    date = ''
    for term in terms:
        if item[1] == term[0]:  # 개인정보 수집가 같은 경우 찾기
            duration = term[1]
            date = item[0]
            break

    data = date.split('.')
    year = int(data[0])
    month = int(data[1])
    day = data[2]

    month += int(duration)
    if month > 12:
        year += month // 12  # 몫만큼 년도 더해주기
        month %= 12  # 나눈 나머지를 월로 설정해주기

    # 12월에서 기간이 12인 경우
    if month == 0:
        year -= 1
        month = 12

    year = str(year)
    month = '0' + str(month) if month < 10 else str(month)

    if year + '.' + month + '.' + day <= today:
        return True
    return False


def solution(today, terms, privacies):
    answer = []
    termArray = []
    for item in terms:
        termArray.append(item.split())

    privacyArray = []
    for item in privacies:
        privacyArray.append(item.split())

    idx = 0
    for item in privacyArray:
        if checkValidation(termArray, item, today):
            answer.append(idx + 1)
        idx += 1

    return answer

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다. 이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다. 사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한사항

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

입출력예

weights = [100,180,360,100,270] result = 4

입출력예 설명

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다. {180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다. {180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다. {270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

문제 풀이(실패)

1. 콤비네이션을 통해 2개를 추출하는 경우의 수를 구하자
2. 2개의 수에서 가장 큰 수와 가장 작은수를 나눠서 비율을 찾자
3. [1, 4/3, 4/2, 3/2] 비율을 갖는 경우 answer값을 추가하자

코드(실패)

from itertools import combinations

def solution(weights):
    answer = 0
    case = list(combinations(weights, 2))
    case.sort(key=lambda x: (x[0]))

    for item in case:
        minNum = min(item[0], item[1])
        maxNum = max(item[0], item[1])
        temp = maxNum / minNum

        if temp in [1, 3/2, 4/3, 4/2]:
            answer += 1

    return answer

실패 이유

1. 시간 초과가 발생한다.

• 콤비네이션 결과가 생각보다 오래 걸린다. 그러므로 해당 문제에 적합하지 않았다. weight의 길이는 2이기 때문에 적합하지 않았다.

문제 풀이(성공)

1. collections의 Counter를 통해 각 weigth 원소에 대해서 개수를 구함
2. 같은 원소가 있는 경우 answer 추가를 미리 해줌
3. 중복되는 원소들은 2번에서 처리를 해줬기 때문에 set을 통해서 제거
4. 같은 원소에 대해서 처리를 했기 때문에 3/4, 2/3, 2/4의 비율을 가지는 weight 원소에 대해서 처리
5. 비율에 맞는 원소가 있다면 answer값 증가

코드

from collections import Counter

def solution(weights):
    answer = 0
    count = Counter(weights)
    for k, v in count.items():
        if v > 1:
            answer += v * (v - 1) // 2

    weights = list(set(weights))
    for item in weights:
        for check in (3/4, 2/3, 2/4):
            if item * check in weights:
                answer += count[item] * count[item * check]

    return answer

문제

n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

입력조건

• 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)
• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n, m <= 20) 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 100)

출력조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

입력 예시

2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력 예시

19
16

풀이방식

해당 문제는 항상 첫 번째 열부터 출발을 하는 겁니다. 첫 번째 열부터 금광을 캘 수 있는 방법은 오른쪽 위, 오른쪽, 오른쪽 아래를 이동하는 겁니다. 여기서 중요한 포인트는 가장 위의 행에서는 오른쪽, 오른쪽 아래로만 이동이 가능하고, 가장 아래 행에서는 오른쪽, 오른쪽 위로만 이동이 가능합니다. 다이나믹 프로그래밍은 dp 배열의 의미를 설정하는 것이 가장 중요합니다. 이를 토대로 bottom-up이 가능하기 때문입니다. 이제 dp 배열의 정의를 해야할 것 같습니다. 제가 설정한 dp 배열은 아래와 같습니다.

dp[i][j]: i, j까지 이동했을 때 얻을 수 있는 가장 많은 금광값

그렇다면 dp[1][1]은 1, 1까지 이동했을 때 얻을 수 있는 가장 많은 금광값이 저장되어 있을 겁니다. 우리는 오른쪽 위, 오른쪽, 오른쪽 아래로만 이동이 가능하기 때문에 아래와 같은 점화식을 도출할 수 있습니다.

dp[i][j] = array[i][j] + max(dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1])

코드

import sys

def dynamicProgramming():
    maxNum = 0
    dp = [[0] * m for _ in range(n)]  # dp[i][j]는 i, j까지 이동했을 때 얻을 수 있는 가장 많은 금광값
    dp[0][0] = array[0][0]
    dp[1][0] = array[1][0]
    dp[2][0] = array[2][0]

    for i in range(1, m):  # 첫번째 열부터 비교
        for j in range(n):  # 첫번째 행부터 비교
            if j == 0:  # 가장 첫번째 행에 있다면 오른쪽과 오른쪽 아래 비교
                dp[j][i] = max(dp[j][i - 1] + array[j][i], dp[j + 1][i - 1] + array[j][i])
            elif j == n - 1:  # 가장 마지막 행에 있다면 오른쪽과 오른쪽 위 비교
                dp[j][i] = max(dp[j - 1][i - 1] + array[j][i], dp[j][i - 1] + array[j][i])
            else:  # 중간행에 있다면 오른쪽, 오른쪽 아래, 오른쪽 위 비교
                dp[j][i] = max(dp[j - 1][i - 1] + array[j][i], dp[j][i - 1] + array[j][i], dp[j + 1][i - 1] + array[j][i])

    # 가장 큰 값 추출
    for item in dp:
        for num in item:
            if num >= maxNum:
                maxNum = num
    return maxNum


T = int(sys.stdin.readline().strip())
for _ in range(T):
    n, m = map(int, sys.stdin.readline().split())
    data = list(map(int, sys.stdin.readline().split()))
    idx = 0
    array = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            array[i][j] = data[idx]
            idx += 1
    result = dynamicProgramming()
    print(result)

나무 자르기

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력1

4 7
20 15 10 17

예제 출력1

15

예제 입력1

5 20
4 42 40 26 46

예제 출력1

36

풀이방식

상근이라는 친구는 환경을 사랑하기 때문에 나무 자를 높이를 최대한 높이 설정해서, 적어도 M미터 만큼 가져가고 싶어한다. 즉 나무 자를 높이를 제일 높게 설정하고 난 뒤, M미터 이상 가져갈 수 있을 때가 정답 포인트이다. 이 문제는 순차 탐색으로 절대 안된다. 시간제한이 1초인데 나타날 수 있는 나무의 길이는 2,000,000,000이다. 약 1억번의 연산이 1초이니, O(N)이 아닌 O(logN)을 이용해서 풀어야 한다.

해당 문제는 길이를 기준으로 이분탐색을 진행해야 했다. start(0)와 end(가장 큰 나무의 높이)를 통해 나오는 mid값을 통해 자른 나무의 총 길이가 M보다 큰 경우와 작은 경우와 같은 경우에 따라 알고리즘을 설계하면 된다.

알고리즘

start와 end를 통해 구하는 mid값은 아래와 같다.

mid = (start + end) // 2

• 자른 나무의 총 길이가 M보다 큰 경우
  • 해당 값이 정답이 될 수 있으므로 따로 저장해둔다.
  • 더 높이 잘라도 되는지 체크해야하므로 start의 위치를 mid + 1로 변경한다.
• 자른 나무의 총 길이가 M보다 작은 경우
  • 더 낮게 잘라야 하므로 end의 위치를 mid - 1로 변경한다.
• 자른 나무의 총 길이가 M과 같은 경우
  • 정답이므로 따로 저장한다.

코드

import sys

def binarySearch(start, end):
    global result

    # 탈출 조건
    if start > end:
        return

    mid = (start + end) // 2  # 중간값 설정
    total = 0  # 잘린 나무의 총 길이 계산
    for item in array:
        if item >= mid:
            total += item - mid


    if total == M:  # 잘린 나무길이가 M과 정확히 일치하는 경우
        result = mid
    elif total > M:  # 잘린 나무길이가 M보다 큰 경우
        result = mid  # result에 해당 mid 값 저장. 적어도 M미터 얻어야 하기 때문
        binarySearch(mid + 1, end)  # start의 위치를 변경해줌
    else:  # 잘린 나무의 길이가 M보다 작은 경우
        binarySearch(start, mid - 1)  # end의 위치를 변경해줌

N, M = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
result = max(array)
binarySearch(0, max(array))  # 0과 가장 긴 길이의 나무를 start와 end로 설정
print(result)

문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1, 1, 2, 2, 2, 2, 3]이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력조건

• 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 <= N <= 1,000,000), (-10^9 <= x <= 10^9)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9 <= 각 원소의 값 <= 10^9)

출력조건

• 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

입력 예시1

7 2
1 1 2 2 2 2 3

출력 예시1

4

입력 예시2

7 4
1 1 2 2 2 2 3

출력 예시2

-1

풀이 방식

해당 문제는 조건에서부터 O(logN) 알고리즘을 설계해서 풀어야 '시간초과' 판정이 나지 않는다 쓰여있습니다. O(N)의 시간복잡도를 갖는 순차탐색을 사용하지 않고 왜 O(logN)의 시간복잡도를 갖는 이분탐색을 써야할까 생각을 했다. 약 1억번의 연산을 하는 것이 1초로 알고있는데, 해당 문제는 시간 제한이 1초이고, N이 1,000,000이기 때문에 괜찮지 않을까 했다. 그러나 문제에서 O(logN)의 시간복잡도로 풀이를 원하니 이분탐색을 진행하였다. 이 문제는 우선 2번의 이분탐색을 진행해야했다.

x의 값을 갖는 원소에서 가장 작은 index를 찾는 이분탐색과 가장 큰 index를 찾는 이분탐색을 해야했다. 자세한 것은 아래 알고리즘에서 더 설명하겠다.

알고리즘

start와 end를 통해 구하는 mid값은 아래와 같다.

mid = (start + end) // 2

위를 토대로 2번의 이분탐색을 진행하면 된다.

• 가장 작은 index를 찾는 이분탐색
  • array[mid]값이 x보다 크다면 end 값을 더 낮게 변경
  • array[mid]값과 x가 같다면 end 값을 더 낮게 변경해서 같은 원소 있는지 체크
  • array[mid]값이 x보다 작다면 start 값을 더 크게 변경
• 가장 큰 index를 찾는 이분탐색
  • array[mid]값이 x보다 크다면 end 값을 더 낮게 변경
  • array[mid]값과 x가 같다면 start 값을 더 크게 변경해서 같은 원소 있는지 체크
  • array[mid]값이 x보다 작다면 start 값을 더 크게 변경

코드

import sys

# 가장 첫번째 x 위치 찾는 함수
def leftBinarySearch(start, end):
  global minIdx

  # 탈출 조건
  if start > end:
    return

  mid = (start + end) // 2  # mid 값 설정

  if array[mid] > x:  # array[mid]값이 x보다 크다면 end 값을 더 낮게 변경
    leftBinarySearch(start, mid - 1)
  elif array[mid] == x:  # array[mid]값과 x가 같다면 end 값을 더 낮게 변경해서 같은 원소 있는지 체크
    minIdx = mid  # minIdx 최신화
    leftBinarySearch(start, mid - 1)
  else:  # array[mid]값이 x보다 작다면 start 값을 더 크게 변경
    leftBinarySearch(mid + 1, end)

# 가장 마지막 x 위치 찾는 함수
def rightBinarySearch(start, end):
  global maxIdx

  # 탈출 조건
  if start > end:
    return

  mid = (start + end) // 2  # mid 값 설정

  if array[mid] > x:  # array[mid]값이 x보다 크다면 end 값을 더 낮게 변경
    rightBinarySearch(start, mid - 1)
  elif array[mid] == x:  # array[mid]값과 x가 같다면 start 값을 더 크게 변경해서 같은 원소 있는지 체크
    maxIdx = mid
    rightBinarySearch(mid + 1, end)
  else:  # array[mid]값이 x보다 작다면 start 값을 더 크게 변경
    rightBinarySearch(mid + 1, end)

N, x = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
minIdx = N  # 가장 첫번째 x 위치
maxIdx = -1  # 가장 마지막 x 위치

leftBinarySearch(0, N - 1)  # 가장 첫번째 x 위치 찾는 함수
rightBinarySearch(0, N - 1)  # 가장 마지막 x 위치 찾는 함수

if maxIdx == -1 and minIdx == N:  # x인 원소가 존재하지 않았다면 -1 출력
  print(-1)
else:
  print(maxIdx - minIdx + 1)

공유기 설치

입력조건

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력 조건

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이 방식

이 집의 좌표가 최대 10억까지이다. 그래서 이진탐색을 통해서 '가장 인접한 두 공유기 사이의 거리'를 조절해가며, 매 순간 실제로 공유기를 설치하여 C보다 많은 개수로 공유기를 설치할 수 있는지 체크하며 문제를 풀 수 있다. 여기서 '가장 인접한 두 공유기 사이의 거리'의 최대값을 찾아야 하므로, C보다 많은 개수로 공유기를 설치할 수 있다면 start값을 증가시키면서, 더 큰 값도 가능한지 체크를 해야한다. 물론 반대인 경우는 end값을 감소시키면서 찾아야 한다. 그래서 아래와 같은 소스코드가 나왔다.

코드

import sys

N, C = map(int, sys.stdin.readline().split())
array = []
for _ in range(N):
    array.append(int(sys.stdin.readline().strip()))

array.sort()

start = 1  # 최소 거리
end = array[-1] - array[0]  # 최대 거리
result = 0  # mid값 저장하는 변수


if C == 2:  # 공유기 2대 설치 가능하면 처음과 끝 원소 차이 result에 저장
    result = array[-1] - array[0]

else:
    while start <= end:  # 이분탐색 시작
        mid = (start + end) // 2  # 간격 계산
        value = array[0]  # 맨 처음 원소에 공유기 설치
        count = 1  # 공유기 설치 가능한 위치 개수
        for i in range(1, N):  # 처음부터 끝까지 분석
            if array[i] >= value + mid:  # 공유기를 설치할 수 있는 간격인지 체크
                value = array[i]  # 공유기 설치 위치 변경
                count += 1  # 공유기 설치 가능한 위치 개수 추가

        if count >= C:  # 공유기를 C와 같거나 더 크게 설치할 수 있는 경우
            result = mid  # 우선 result에 저장
            start = mid + 1  # start를 mid + 1로 변경해서 더 높은 수의 간격이 가능한지 체크
        else:  # 공유기를 C보다 설치를 못하는 경우
            end = mid - 1  # end를 mid - 1로 변경해서 더 낮은 수의 간격이 가능한지 체크

print(result)

N과 M(1)

입력

첫째 줄에 자연수 N과 M이 주어진다. N과 M은 1이상 8이하

출력

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다. 중복되는 수열은 여러번 출력하면 안되고, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

해결방법

이 문제는 2가지의 방법으로 풀 수 있다. 순열을 이용해서 푸는 방법과 백트래킹을 이용해서 푸는 방법이다. 순열을 콤비네이션과 다르게 순서에 상관있게 나타낼 수 있다. 그래서 N개중 M개의 숫자를 고르면 된다. 백트래킹을 이용해서 모든 경우의 수에 대해서 재귀적으로 탐색하면 된다.

코드

우선 순열을 이용해서 푸는 것은 아래와 같다.

import sys
from itertools import permutations

N, M = map(int, sys.stdin.readline().split())
array = [i + 1 for i in range(N)]  # 1 ~ N까지의 숫자를 가진 배
permu = list(permutations(array, M))  # M개 만큼 순열함수 사용
for item in permu:
    for num in item:
        print(num, end=' ')
    print()

백트래킹을 이용해서 푸는 것은 아래와 같다.

import sys

def backTracking(numList):  # 백트래킹 함수
    if len(numList) == M:  # 길이가 M과 같다면 탈출
        array.append(numList)  # 정답 배열에 삽입
        return
    else:
        for i in range(1, N + 1):
            if i not in numList:
                backTracking(numList + [i])  # 리스트 끝 요소에 붙이기


N, M = map(int, sys.stdin.readline().split())
array = []
for i in range(1, N + 1):  # 1 ~ N까지의 숫자 체크
    backTracking([i])

for item in array:
    for num in item:
        print(num, end = ' ')
    print()

<문제> 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 이걸 처리 안 해줘서 시간을 허비했다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

<입력 조건>

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다.(1<=N<=1,000,000, 1<=M<=2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

<출력 조건>

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

<입력 예시> 4 6 19 15 10 17

<출력 예시> 15

확인해야할 점

떡의 개수는 최대 1,000,000개, 요청한 떡의 길이 2,000,000,000 그리고 떡의 개별 높이는 1,000,000,000이다. 10억의 수를 탐색하기 위해서는 이분탐색을 사용해야한다.

풀이 방법

이분 탐색을 이용하는데, 인덱스를 이용하지 말고 값을 이용하자. 이분 탐색을 진행하기 위해서는 start, end를 정해야 한다. 인덱스를 사용하지 않고 값을 사용하니 start는 떡의 길이의 최소값인 0이 되고, end는 떡 배열의 최대값을 이용하면 된다. 그런 다음 이분 탐색을 진행하는데, start와 end를 통해 자를 지점인 mid를 구할 수 있다. mid값을 이용해서 떡을 자르고 M이 mid 절단 위치를 통해 자른 떡의 총길이보다 크면 end를 mid - 1로 설정하고, 작거나 같으면 start를 mid + 1로 설정해서 탐색한다.

소스코드

import sys

def binarySearch(start, end):
    result = 0  # 떡의 절단 길이 정하는 변수
    while start <= end:  # start가 end보다 작거나 같을 때까지
        total = 0  # 떡의 자른길이 변수
        mid = (start + end) // 2  # 중간값 저장하는 변수
        for item in array:
            if item > mid:  # item이 mid보다 크면 짤림
                total += item - mid  # 차이값 저장
        if total < M:  # 자른 떡의 총합이 M보다 작은 경우
            end = mid - 1  # 떡의 절단 마지막 위치를 mid 앞으로 위치 조정
        else:  # 자른 떡의 총합이 M보다 작거나 같은 경우
            result = mid  # 떡의 절단 길이 최신화
            start = mid + 1  # 떡의 절단 시작 위치를 mid 뒤로 위치 조정
    return result


N, M = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))

print(binarySearch(0, max(array)))  # 떡의 첫번째 길이부터 최대 길이까지 전달

import sys
from collections import deque

def checkBorder(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    return True


def bfs(x, y, index):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    united = []  # 연합나라 좌표 저장하는 배열
    united.append((x, y))  # 좌표 저장
    check[x][y] = index  # 연합팀 종류 기록
    summary = array[x][y]  # 추후에 연합한 나라들의 인구수 합이 저장되는 변수
    count = 1  # 연합 나라수
    queue = deque()
    queue.append((x, y))  # 큐 삽입

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            na = a + dx[i]
            nb = b + dy[i]

            if checkBorder(na, nb):
                if check[na][nb] == -1:  # 연합이 되지 않은 나라인 경우
                    if L <= abs(array[na][nb] - array[a][b]) <= R:  # 두 나라 사이의 인구수가 L과 R사이에 있는 경우
                        queue.append((na, nb))  # 큐 삽입
                        check[na][nb] = index  # 연합 기록
                        summary += array[na][nb]  # 연합한 나라의 인구수 추가
                        count += 1  # 연합한 나라수 추가
                        united.append((na, nb))  # 연합 나라 좌표 저장

    # 인구수 재배치
    for i, j in united:
        array[i][j] = summary // count

N, L, R = map(int, sys.stdin.readline().split())
array = []
for i in range(N):
    array.append(list(map(int, sys.stdin.readline().split())))

totalCount = 0  # 전체 이동 횟수
while True:
    check = [[-1] * N for _ in range(N)]  # 연합 위치를 기록하는 배열
    index = 0  # 연합의 팀 종류를 나타내는 index
    # 전체 탐색
    for i in range(N):
        for j in range(N):
            if check[i][j] == -1:  # 연합이 되지 않은 곳이면 bfs 수행
                bfs(i, j, index)
                index += 1  # 연합팀 종류 증가
    if index == N * N:  # 모든 나라들이 연합을 해서 인구이동을 마쳤을 때
        break
    totalCount += 1  # 전체 이동횟수 증가

print(totalCount)

이 문제는 학생들이 선생님에게 걸리지 않게 벽을 잘 설치하는 것이다. 벽은 3개 설치할 수 있는데, 걸리지 않는 경우가 있다면 YES를 출력하면 된다. 선생님이 학생을 발견하는 경우는 선생님의 위치는 그대로 있고 상, 하, 좌, 우 방향으로 쭉 볼 수 있다. 우선 벽을 설치할 수 있는 곳은 선생님, 학생이 아닌 위치이다. 그래서 벽을 설치할 수 있는 좌표를 따로 저장을 해준 다음, 여기서 3개를 골라서 모든 경우의 수에 대해서 테스트를 해봐야한다. 순서를 고려하지 않고 3개의 좌표를 뽑는 것이므로 콤비네이션을 사용해서 모든 후보들에 대해서 조사를 하면 된다. 그런 다음 4방향에 대해서 체크를 해주면 끝이다. 아래와 같이 코드를 설계했다.

import sys
import copy
from itertools import combinations

# 경계값 체크
def checkBorder(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    return True


# 학생을 마주칠 수 있는지 체크하는 함수
def solution(x, y, check):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0 ,0]

    for i in range(4):
        nx, ny = x, y
        while True:
            nx += dx[i]
            ny += dy[i]

            if checkBorder(nx, ny):  # 경계선 체크해서 알맞다면
                if check[nx][ny] == 'S':  # 학생인 경우 False
                    return False
                elif check[nx][ny] == 'O':  # 장애물인 경우 break해서 새로운 방향 탐색
                    break
                elif check[nx][ny] == 'T':  # 선생님인 경우 break해서 새로운 방향 탐색
                    break
            else:  # 경계선 체크해서 알맞지 않는다면
                break
    return True


N = int(sys.stdin.readline().strip())
array = []
for i in range(N):
    array.append(list(map(str, sys.stdin.readline().split())))
none = []
# X의 좌표들 리스트에 저장
for i in range(N):
    for j in range(N):
        if array[i][j] == 'X':
            none.append((i, j))

# 콤비네이션을 통해 3개의 좌표 조합 리스트 생성
candidates = list(combinations(none, 3))

# 후보들에 대해서 반복문 수행
for candidate in candidates:
    temp = copy.deepcopy(array)  # 기존 배열을 깊은 복사를 통해서 저장
    for item in candidate:  # 장애물 설치
        temp[item[0]][item[1]] = 'O'
    answer = True  # flag 배열 조사할 때 쓰이는 값
    flag = []  # 모든 선생님들에 있어서 마주치지 않는지 체크
    for i in range(N):
        for j in range(N):
            if temp[i][j] == 'T':  # 선생님인 경우 함수 수행후 반환값 flag 배열에 저장
                flag.append(solution(i, j, temp))

    # flag 배열중 False가 있다면 정답 아님
    for i in range(len(flag)):
        if flag[i] != True:
            answer = False
            break
    # flag 배열 모두 True이면 탈출
    if answer:
        break

# 정답에 따라서 노출 변경
if answer:
    print('YES')
else:
    print('NO')