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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

문제이해

직사각형 모양의 연구소가 있고, 연구소에 새로운 벽 3개를 설치하였을 때 바이러스가 퍼지지 않는 안전한 지역의 최대 갯수를 구하는 문제 였습니다. 중요한 점은 꼭 새로운 벽 3개는 필수적으로 설치를 해야한다는 점입니다.

단순히 모든 경우에 있어서 3개의 빈공간을 선택하여 벽을 설치하고, 바이스의 위치에서 bfs를 돈다고 했을 때 시간초과가 날까 걱정했지만 입출력 조건을 보고 가능하다 생각하게 되었습니다.

직사각형의 최대 크기는 8x8 = 64 였으며 벽 3개를 고르는 모든 경우의 수 64C3 = 41664 이며, 매번 모든 공간을 탐색한다고 하였을 때 최대 41664 x 64 = 2666496 으로 충분히 시간내에 가능하였습니다. (사실 크게 계산을 안해봐도 제한이 8이라는 것을 보았을 때 시간 제한은 걸리지 않을 것 같았습니다.)

 

입출력 조건

시간 제한은 2초, 직사각형의 최대 크기는 64 였고, 위의 식대로 시간초과가 나지는 않을 듯 하였습니다.

 

풀이

위 방식대로 문제를 해결하였으며 자세한 사항은 코드 내 주석을 참고해 주세요.

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 2151 거울설치  (1) 2024.03.24
[BOJ C++] 16918 봄버맨  (0) 2022.08.01
[BOJ C++] 1922 네트워크 연결  (0) 2022.07.28
[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28

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

 

2151번: 거울 설치

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은

www.acmicpc.net

 

문제이해

사실 문제를 이해하기가 가장 어려웠습니다. 하여 다른 분들의 풀이를 보고서 문제를 이해할 수 있었습니다. 하나하나 차근차근 보도록 하겠습니다.

 

1. 거울을 설치하면 45도 기울어진 상태로 설치하게 됩니다 -> 이는 결국 빛이 들어오는 방향의 90도로 빛이 꺾인다는 것을 의미합니다. 그렇기에 빛은 거울을 만나면 들어오는 방향에서 90도로 꺾이는 두가지 방향으로 진행하게 됩니다. (예를 들어 북쪽에서 빛이 남쪽으로 향하다가 거울을 만나면 동쪽 혹은 서쪽으로 꺾이게 됩니다)

 

2. 시작할 당시 빛의 진행 방향을 알 수 없기 때문에 모든 방향으로 진행됨을 고려해 주어야 합니다.

 

3. 같은 지점으로 빛이 도착할 지라도, 어떠한 방향에서 들어왔는지에 따라 모두 다른 경우이기 때문에 이를 모두 체크해 주어야 합니다. 예를 들어 빛이 [3,3]에 도착하였을 경우 북쪽으로 부터 들어온 빛인지, 동쪽에서 들어온 빛인지에 따라 모두 다른 경우가 됩니다. 그렇기에 visit 배열 같은 경우 3차원 배열로 생각하는 것이 편한 방법이였습니다. (예를 들어 visit[A][B][C]는 [A,B]좌표에서 C방향으로 빛이 진행할 때 설치한 거울의 갯수가 되도록 하였습니다)

 

이제 문제를 풀어보겠습니다.

 

입출력 조건

시간 제한은 2초, 집의 최대 크기는 50x50 이였기에 4방향을 모두 탐색하여 50x50x4가 되어도 시간을 초과할 일이 없었습니다.

 

풀이

 위 문제 이해를 바탕으로 BFS를 이용해 문제를 해결하였으며 자세한 세부사항들은 코드에 주석을 달아 놨습니다.

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 14502 연구소  (0) 2024.03.26
[BOJ C++] 16918 봄버맨  (0) 2022.08.01
[BOJ C++] 1922 네트워크 연결  (0) 2022.07.28
[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28

Nginx 설치 및 SSL 인증서 발급과 Spring Boot에 맞게 설정하기

 

### apt 패키지 업데이트
$ sudo apt update

### letsencrypt 설치
$ sudo apt-get install letsencrypt -y

### 업데이트
$ sudo apt update
$ sudo apt upgrade -y

### ssl 인증서 제공하는 certbot 설치 + nginx도 함께 설치 됨
$ sudo apt install certbot python3-certbot-nginx

### nginx 실행
$ sudo service nginx start

### SSL 인증서 발급, 나의도메인주소ex)domain.shop
### 첫 번째로 메일 입력
### 동의여부 선택사항 2번 나옴, 약관동의는 동의하시고 이메일 공유는 its up to you
### 1,2	번 선택사항에서는 2번 선택
$ sudo certbot --nginx -d 나의도메인주소

### nginx 폴더로 이동
$ cd /etc/nginx

### 해당 폴더들 권한 추가
$ sudo chmod 777 ./sites-available
$ sudo chmod 777 ./sites-enabled

### 해당 폴더로 이동
$ cd /etc/nginx/sites-available

### 새로운 conf 생성, 이름은 상관없음
$ sudo vi ./test.conf

test.conf에 아래 내용 추가

server {
  listen 80; #80포트로 받을 때
  server_name my-domain.shop; #도메인주소
  return 301 https://my-domain.shop$request_uri;
}

server {
  listen 443 ssl http2;
  server_name my-domain.shop;

  # ssl 인증서 적용하기
  ssl_certificate /etc/letsencrypt/live/my-domain/fullchain.pem;
  ssl_certificate_key /etc/letsencrypt/live/my-domain/privkey.pem;

  location / { # location 이후 특정 url을 처리하는 방법을 정의(여기서는 / -> 즉, 모든 request)
    proxy_pass http://localhost:8000; # Request에 대해 어디로 리다이렉트하는지 작성. 8000 -> 자신의 springboot app이사용하는 포트
    proxy_set_header Host $http_host;
    proxy_set_header X-Real-IP $remote_addr;
    proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
    proxy_set_header X-Forwarded-Proto $scheme;
  }
}

server {
    if ($host = my-domain.shop) {
        return 301 https://$host$request_uri;
    } # managed by Certbot


  listen 80;
  server_name smy-domain.shop;
    return 404; # managed by Certbot

}

- 80포트로 받았을 경우 redirect 시켜줌

- 443으로 받았을 경우 http://localhost:port로 redirect 시켜줌, 여기서 port는 spring boot에서 사용하는 port번호를 이용!

 

이후,

### sites-available의 test.conf를 sites-enabled에 복사
$ sudo ln -s /etc/nginx/sites-available/test.conf /etc/nginx/sites-enabled

### 해당 폴더로 이동
$ cd /etc/nginx/sites-enabled

### 문제없는지 테스트
$ sudo nginx -t

### default 파일 삭제
$ sudo rm default

### 재시작
$ sudo service nginx restart

위와 같이 함으로써 HTTP, HTTPS로 request가 들어올 시 spring boot로 redirect가 가능 함

'Develop > Server' 카테고리의 다른 글

[에러] Enable to lacate package  (0) 2022.05.22
가비아 도메인 설정과 HTTPS 설정  (0) 2022.05.20
Docker를 이용한 서버 배포  (0) 2022.05.20
RDS 생성 및 외부 접속 연결  (0) 2022.05.18
EC2 인스턴스 및 고정 IP 설정  (0) 2022.05.11

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

 

16918번: 봄버맨

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

www.acmicpc.net

 

 

문제 이해

RxC 크기의 격자가 주어지고 봄버맨은 그 위에 살고 있습니다. 봄버맨이 폭탄을 설치하고 폭탄은 3초후에 폭발하며 매초 빈칸은 폭탄이 설치 됩니다. 폭탄은 연쇄 폭발을 일으키지 않으며 최초 1초는 아무일도 일어나지 않습니다. 이때 N초만큼 시간이 흐른후의 격자판의 모습을 구하는 문제였습니다.

 

 

입출력 조건

R,C,N 은 모두 200이 최대였으며 시간초 제한은 2초였습니다.

 

 

풀이

R,C,N이 모두 200이 최대 였기에 완탐을 돌려도 200x200x200 이면 800만 정도이기에 충분하다 생각하여 순전히 구현으로 문제를 해결하였습니다.

 

 

에러 및 느낀 점

0과 O가 구분이 잘 안갑니다...

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16918_%EB%B4%84%EB%B2%84%EB%A7%A8.cpp

 

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

This is a repository for additional problem solving in Baekjun. - GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

github.com

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 14502 연구소  (0) 2024.03.26
[BOJ C++] 2151 거울설치  (1) 2024.03.24
[BOJ C++] 1922 네트워크 연결  (0) 2022.07.28
[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28

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

 

1922번: 네트워크 연결

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

www.acmicpc.net

 

 

문제 이해

그래프가 주어지고 해당 그래프에서 모든 정점을 연결하면서 가중치의 합이 가장 작은 그래프의 가중치의 합을 구하는 문제였습니다.

 

 

입출력 조건

시간초 제한은 2초였으며 최대 정점의 갯수는 1,000개 였습니다.

 

 

풀이

당연히 MST 문제라고 생각을 하였고 실제로 그렇게 구현했습니다.

기본적인 MST 문제였습니다.

 

 

에러 및 느낀 점

.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1922_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20%EC%97%B0%EA%B2%B0.cpp

 

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

This is a repository for additional problem solving in Baekjun. - GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

github.com

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 2151 거울설치  (1) 2024.03.24
[BOJ C++] 16918 봄버맨  (0) 2022.08.01
[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28
[BOJ C++] 16964 DFS 스페셜 저지  (0) 2022.07.28

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

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

문제 이해

친구 관계의 수 F가 주어지고 F줄 만큼 친구 관계가 주어질 때, 해당 친구관계가 주어질 때 마다 연결되어 있는 친구 관계의 수를 출력하는 문제였습니다.

 

 

입출력 조건

시간초 제한은 3초였으며 최대 친구관계의 수는 100,000개 였습니다. 이에 따라 나올 수 있는 최대 인원의 수는 200,000이라는 것을 알 수 있습니다.

 

 

풀이

일반적인 유니온 파인드에  부모 배열과 함께 친구의 수를 저장하는 배열을 같이 두면 되겠다고 생각했습니다.

매번 들어올 때마다 두 친구를 유니온 해주고, 유니온 할때 한쪽의 친구 수를 0으로 만들고 다른쪽으로 합쳐줬습니다.

또 문자열로 입력이 들어왔기에 map을 이용하여 번호를 부여해 주었습니다.

 

 

에러 및 느낀 점

처음에 친구관계가 최대 100,000개라 해서 배열을 100,000까지만 잡고 했다가 Out of Bounds가 떴었습니다ㅠ

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/4195_%EC%B9%9C%EA%B5%AC%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.cpp

 

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

This is a repository for additional problem solving in Baekjun. - GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

github.com

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 16918 봄버맨  (0) 2022.08.01
[BOJ C++] 1922 네트워크 연결  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28
[BOJ C++] 16964 DFS 스페셜 저지  (0) 2022.07.28
[BOJ C++] 1647 도시 분할 계획  (0) 2022.07.28

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

 

16940번: BFS 스페셜 저지

올바른 순서는 1, 2, 3, 4와  1, 3, 2, 4가 있다.

www.acmicpc.net

 

 

문제 이해

양방향 그래프가 하나 주어지고 해당 그래프의 정점 1에서 부터 BFS를 수행하였을 때 예상했던 순서로 정점이 출력이 되는지를 묻는 문제였습니다.

 

 

입출력 조건

시간제한은 2초에 정점은 100,000개 까지였습니다.

 

 

풀이

앞서 풀었던 DFS 스페셜 저지 문제와 똑같은 문제에 dfs -> bfs로 바뀐 문제였기에 앞의 문제 풀이 링크를 참고해 주시면 감사하겠습니다.

https://tory-do.tistory.com/57

 

[BOJ C++] 16964 DFS 스페셜 저지

https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문..

tory-do.tistory.com

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16940_BFS%20%EC%8A%A4%ED%8E%98%EC%85%9C%20%EC%A0%80%EC%A7%80.cpp

 

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

This is a repository for additional problem solving in Baekjun. - GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

github.com

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 1922 네트워크 연결  (0) 2022.07.28
[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16964 DFS 스페셜 저지  (0) 2022.07.28
[BOJ C++] 1647 도시 분할 계획  (0) 2022.07.28
[BOJ C++] 3020 개똥벌레  (0) 2022.07.25

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

 

16964번: DFS 스페셜 저지

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루

www.acmicpc.net

 

 

문제 이해

양방향 그래프가 하나 주어지고 해당 그래프의 정점 1에서 부터 DFS를 수행하였을 때 예상했던 순서로 정점이 출력이 되는지를 묻는 문제였습니다.

 

 

입출력 조건

시간제한은 2초에 정점은 100,000개 까지였습니다.

 

 

풀이

이게 뭔 문제인가 싶었습니다.. 그냥 DFS를 구현했고 돌려서 비교하면 되는거 아닌가..해서 했더니 아니나 다를까 그렇게 쉬운문제는 아니였습니다.

간선들 사이에 우선순위가 정해져 있지 않았기 때문에 여러가지의 답이 나올 수 있는 상황이였습니다.

그래서 예상 순서를 받았을 때 이를 배열에 따로 저장하고 이들이 나온 순서를 또 배열로 저장하여 앞서 나온 순서들이 먼저 DFS에 들어갈 수 있도록 정렬해 주었습니다.

그리고 제출했더니..100퍼센트에서 틀렸습니다가 떴습니다..아무리 봐도 맞는거 같은데 뭐지뭐지 하다가 

해당 줄을 계속 보다보니 이게 시작정점이 1이여야만 한다는 건가..? 라는 생각이 들었습니다.

그래서 1이 아닌경우는 그냥 0을 출력하고 끝내는 코드로 수정 후 제출해 보니 맞았습니다가 떴습니다..

어이 없었슴다ㅜ

 

 

에러 및 느낀 점

문제 설명이 조금 더 정확히 있었으면 어땠을까 하는 생각이 들었습니다ㅠ

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16964_DFS%20%EC%8A%A4%ED%8E%98%EC%85%9C%20%EC%A0%80%EC%A7%80.cpp

 

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

This is a repository for additional problem solving in Baekjun. - GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.

github.com

 

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ C++] 4195 친구 네트워크  (0) 2022.07.28
[BOJ C++] 16940 BFS 스페셜 저지  (0) 2022.07.28
[BOJ C++] 1647 도시 분할 계획  (0) 2022.07.28
[BOJ C++] 3020 개똥벌레  (0) 2022.07.25
[BOJ C++] 1803 무술 연습  (1) 2022.07.25

+ Recent posts