모눈종이에 사각사각

이번 포스팅에서는 0-1 BFS 알고리즘에 대해 알아보고자 한다. 백준 13549 숨바꼭질3 문제를 풀 때 0-1 BFS 알고리즘이 있다는 사실을 알게 되었다. 0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 푸는 것이다. 가중치가 0과 1만 있을 때는 최단거리를 찾을 경우에 다익스트라가 가장 좋은 선택이 아니다. 다익스트라 알고리즘의 시간 복잡도는 \(O(ElogE)\) 혹은 \(O(ElogV)\)인 반면, 0-1 BFS를 사용하면 \(O(V+E)\)의 상수시간으로 문제를 해결할 수 있다. 🍀 0-1 BFS의 동작 과정 deque를 활용해서 진행한다. 1. deque에서 popleft()로 현재 노드를 꺼낸다. 2. 연결된 인접 노드를 살펴본다. 3...

🍎 [백준 13549] 숨바꼭질3 문제링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⚾ 코드 from collections import deque N, K = map(int, input().split()) # N: 언니, K:동생 INF = int(1e9) second = [INF]*(max(N, K)*2) # 언니와 동생중 큰 값의 두 배 길이의 second 리스트 생성 def check_range(n..

🍎 [백준 11265] 끝나지 않는 파티 문제링크 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net ⚾ 코드 # 11265 끝나지 않는 파티 import sys input = sys.stdin.readline N, M = map(int, input().split()) # N: 파티장의 크기, M: 서비스를 요청한 손님의 수 graph = [list(map(int, input().split())) for _ in..

🍀 SpringBoot 백그라운드에서 실행 - nohup 항상 컴퓨터를 켜두고 서버를 실행시킨다면 상관없지만, 터미널을 끄고 켤 때마다 다시 빌드를 하고 서버를 실행시키는 것은 꽤나 불편한 일이다. nohup 명령어를 사용한다면, 프로그램을 백그라운드에서 실행시킬 수 있다. 먼저 빌드클린을 한 후 빌드를 한다. ./gradlew clean build 만약 여기서 권한 오류가 난다면 상위 디렉토리로 이동해서 권한을 부여한다. 그리고 다시 원래 디렉토리로 이동한다. cd .. chmod -R 777 [디렉토리 이름] cd [디렉토리 이름] 지금까지는 다음과 같은 명령어를 통해 포어 그라운드에서 실행시켰다. java -jar build/libs/[프로젝트 이름]-0.0.1-SNAPSHOT.jar 🥦 백그라운드..

🍀 EC2 서버 시간 맞추기 프로젝트 진행 중에, 주문 시간은 현재 시간으로 입력되도록 맞춰놨다. 로컬에서는 잘 입력되던 것이, EC2 서버에 올려 실행해보니 시간이 9시간 느린 것이다! 알고보니 EC2 서버 시간은 한국 시간이 아니기 때문에 맞춰줘야 한다고 한다. 1. 현재 시간 확인 date date 명령어를 치면 현재 시간을 확인할 수 있다. 지금 시각과 다르다면 시간대가 다르게 설정되어 있는 것이기 때문에 바꿔주어야 한다. 2. timezone 확인 more /etc/timezone 위의 명령어는 현재 설정된 timezone의 상태를 확인하는 것이다. 잘 설정되어 있다면 Asia/Seoul로 뜨고 아니라면 Etc/UTC라고 되어있을 것이다. 3. timezone 변경 TimeZone을 변경하기 위..

🍎 [백준 18405] 경쟁적 전염 문제링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net ⚾ 코드 from collections import deque N, K = map(int, input().split()) graph = [[0]*(N+1)] # 1부터 시작하게 하기 위해서 virus_location = [] for i in range(1, N+1): graph.append([0]+list(map(int, ..

🌰 천 단위 콤마 찍기 - FORMAT 금액을 표시할 때 '15,000원' 등 천단위로 콤마를 찍는다. MySQL에서는 숫자 값에 대한 포맷을 제공하는 함수인 FORMAT 함수가 있다. 사용 방법은 다음과 같다. FORMAT(칼럼 및 데이터, 소수점 이하 표시될 자릿수) return 값 : String 예시를 들어보도록 하자 SELECT FORMAT(deliveryFee,0) AS fee FROM DeliveryFee D WHERE D.status='Y'; 위는 DeliveryFee(배달비) 테이블에서 상태값이 Y인 배달비를 SELECT 하는 쿼리문이다. FORAMT 함수의 두 번째 파라미터에 0을 넣어주면 소수점 이하 자리는 나오지 않는다. 만약 두 번째 파라미터를 1과 2로 넣어주면 각각 소수점 첫째..

🌻 여러 개의 repository에 push하기 한 개의 프로젝트를 여러 개의 repository에 push 하기 위해서는 다음과 같은 과정을 거쳐야 한다. 1. 원격 저장소 추가 git remote add [원격 저장소 이름] [repository 주소] # 예시 git remote add origin2 https://github.com/~~~ 2. 새로 연결한 원격 저장소에 push git push -u [새로운 원격 저장소 이름] main # 예시 git push -u origin main 참고사이트 https://twofootdog.tistory.com/42

🌻 Github에 올라간 파일 삭제하기 프로젝트를 하면서 github에 private로 repository를 만들어서 계속 push하고 있었다. 그러다가 프로젝트를 public으로 바꾸려고 gitignore을 설정하려고 하니, 이미 올라간 파일이 있어서 적용되지 않았다. 이를 위해서는 이미 원격 저장소에 올라간 파일을 삭제해야 한다. git rm --cached -r [폴더명 | 파일명] # 예시 - 파일 삭제 git rm --cached -r .idea/test.txt # 예시 - 폴더 및 하위 파일 모두 삭제 git rm --cached -r .idea/ 그다음 commit과 push까지 진행해주어야 완료된다. 참고사이트 https://bskyvision.com/990

🍎 [백준 1707] 이분 그래프 문제링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⚾ 코드 (PyPy3 제출) from collections import deque K = int(input()) def bfs(graph, i): q = deque() q.append(i) while q: now = q.popleft() for node in graph[now]: if visited[node] == visited[now]: return F..