[BOJ] 백준 5014 스타트링크 / BFS

💭 문제 이해 강호가 엘리베이터를 타고 S층에서 G층으로 가기 위한 최소 이동 횟수를 구하는 문제이다. 이 문제의 특징은 한 번에 하나의 버튼만 눌러 Up 또는 Down 크기만큼만 이동할 수 있다. 너비 우선 탐색을 수행하여 문제를 풀면 목적지까지 최소 횟수로 이동하게 할 수 있다. visited 배열을 대신하여 cnt 배열을 사용했다. cnt 배열은 기본값이 -1로 초기화되어있고, 출발선은 0으로 설정을 한다. Up 또는 Down 선택을 큐에 넣을 때마다 cnt 배열에 그 위치값을 이전 위치 값 +1로 설정한다. 최종 목적지인 g까지 도착하는 최소 이동 횟수가 cnt[g]에 구해지게 된다. 구현 언어: Python from collections import deque def solve(): global..

→2021.01.13

[BOJ] 백준 13549 숨바꼭질 3 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 좌우로 이동하는 두 가지의 선택은 동시에 1초 씩 증가하지만 이 문제는 다른 숨바꼭질 문제와 다르게 *2로 이동하는 선택은 시간이 증가하지 않는다는 특징이 있다. 너비 우선 탐색을 선택했다. 구현 언어: Python from collections import deque def solve(): global n, k, sec queue = deque() # 시작점 세팅 queue.append(n) sec[n] = 0 while queue: now = queue.popleft() # 순간이동: 시간 증가 안함 if 0

→2021.01.12

[BOJ] 백준 13913 숨바꼭질 4 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 가장 빠른 시간을 구하고 경로를 출력해야한다. 현재 위치 바로 직전 번호를 따로 저장해두고, 역추적하며 문자열로 저장해 출력했다. 구현 언어: Python from collections import deque def solve(): global n, k, sec, route queue = deque() # 시작점 세팅 queue.append(n) sec[n] = 0 route[n] = n while queue: now = queue.popleft() for next in (now - 1, now + 1, now * 2)..

→2021.01.12

[BOJ] 백준 12851 숨바꼭질 2 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 가장 빠른 시간으로 찾아가는 방법이 총 몇 가지인지도 구해야 하는 것이 포인트이다. 현재 경로까지의 cnt가 다음 경로에도 합산이 되므로 마치 부분적으로 dp 문제와 같은 느낌이 들었다. 구현 언어: Python from collections import deque def solve(): global n, k, sec, cnt queue = deque() queue.append(n) # 시작점을 먼저 담는다. sec[n] = 0 cnt[n] = 1 while queue: now = queue.popleft() for n..

→2021.01.12

[CS] 네트워크 공부 자료들 📒 (updating..)

CS 과목 중 네트워크 기본 지식을 다지기 위해 공부한 자료들을 정리한다!🌈 Edwith CS50 인터넷과 네트워크 [해외명강] 컴퓨터 과학 교양 강좌: CS50 강좌소개 : edwith - 커넥트재단 www.edwith.org 하버드 컴퓨터공학과 David J. Malan 교수님이 진행하는 CS50 강의 영상이다. TCP/IP, DHCP, DNS, HTTP 등의 기본적인 내용을 폭넓게 다루어주시는데 그냥 대박이다... 특히 라우터 부분을 설명하실 때, 라우터를 학생들로 비교하며 사진조각을 전달하며 설명하시는 부분이 있는데 그냥 감동 그 자체였음...😭 영상 자체도 짧게 짧게 잘려있어서 부담없이 정말 재미있게 본 강의이다!

→2021.01.12

[BOJ] 백준 1697 숨바꼭질 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 주의해야할 점이 있었다. 1. (현재 위치, 거기까지 걸린 초) 를 튜플로 큐에 저장해서 사용 각 선택지가 이동하는 방법에 따라 시간이 다르므로, 이동하는 것에 따라 걸린 시간을 같이 보관했다. 2. 방문 체크가 필수이다. 방문했던 지점을 다시 밟는 것은 의미없는 것이다. 실컷 이동하다가 다시 같은 지점을 밟는 것은 결코 최소 거리가 될 수 없다. (+ 시간 초과 100%...) 구현 언어: Python from collections import deque from sys import stdin def solve(): ..

→2021.01.07

[BOJ] 백준 7569 토마토 / BFS

💭 문제 이해 역시 탐색문제로 BFS를 이용하여 풀어야 한다. 여섯 방향으로 동시에 진행하므로 너비 우선 탐색이 맞다고 판단하였다. 다른 문제와 차이점이라면 3차원 리스트를 이용하여야 한다는 점인데, arr[깊이][가로][세로] 인 것을 유의하여야 하는 문제이다. 구현 언어: Python import sys from collections import deque # 3차원 리스트는 arr[깊이][가로][세로]로 구성 # col, rol, height m, n, h = map(int, sys.stdin.readline().rstrip().split()) warehouse = [[list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] ..

→2021.01.05

[BOJ] 백준 2644 촌수계산 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. 입력으로 주어진 연결 관계를 2차원 리스트로 양 쪽 모두에 저장한다. visited 리스트에는 출발점에서 해당 번호의 노드까지 이동하는 거리(촌수)를 저장한다. visited의 도착점 위치 값이 0이면 가족 관계가 전혀 없다는 뜻이므로 -1을 출력하고, 값이 존재한다면 그 촌 수를 출력한다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) man1, man2 = map(int, stdin.readline().rstrip().split()) m = int(stdin.readline().rs..

→2021.01.05

[BOJ] 백준 2667 단지번호붙이기 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. N의 크기가 최대 25로 매우 작다. 그러므로 n2의 방법으로 모든 공간을 탐색하며 집이 있는 공간인 1을 발견하면 그 지점에서 탐색을 시작한다. 탐색을 마치고 구해진 크기(단지 크기)를 리스트에 append한다. 모든 연산이 마치면 리스트에는 단지들의 크기가 저장된다. 리스트의 길이가 단지 수가 되고, 리스트를 오름차순 정렬하여 원소들을 출력하는 것으로 마친다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) square = [list(map(int, list(stdin.readline..

→2021.01.04

[java-live-study] 🌈 5주차 과제: 클래스

백기선 님이 유튭에서 진행하는 JAVA Live-study 과정을 기록한다. 매 주 이슈에 올라온 질문들에 대해 공부하고 답을 남기고, 이슈에 링크를 공유하는 방식으로 진행된다. 추후 백기선 님의 유튜브 라이브를 통해 피드백을 받게 된다. 조금 늦더라도 과제를 수행하면 출석 인정을 해주시기로 했다!(늦더라도 꼭 공부하는게 중요!) 즉, Java 공부를 기록하는 과정이다 🌱 📌 목표 자바의 Class에 대해 학습하세요. 📌 학습할 것 (필수) 클래스 정의하는 방법 객체 만드는 방법 (new 키워드 이해하기) 메소드 정의하는 방법 생성자 정의하는 방법 this 키워드 이해하기 You can not write Java code without defining a class. 1. 구조체 vs 클래스 [Java에..

→2021.01.04