이제 곧 싸피데이!!! 싸피데이를 즐기기 전 숨바꼭질3 문제를 풀고 공부 기록 시작한다 ㅠ 1. 출처 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 왜이리 어려운 것이냐?... 처음 이 문제를 보고, 어떻게 문제를 풀어야할지 감이 잡히지 않았다... 그래서 결국 구글링을 통해 다른 사람들의 코드를 보며 어떻게 문제를 짜야할지 봤던 문제.. https://www.acmicpc.net/board/view/115423 글 읽기 - dp 문제가 아닌지, 다익스트라 문제인지 어떻게 판..
오늘 수업 끝나기 1시간 전에 선택한 문제 프림으로 풀라다가 생각안나서 다익스트라로 풀었는데, 민성이 오빠의 이해할 수 없다는 표정과 호진이 오빠의 웃음소리가 선명하다. 시무룩 MST 문제를 풀기 위해 내가 선택할 수 있는 알고리즘은 프림과 크루스칼 둘 중 하나였는데, 간지나 보인다고 크루스칼로 풀라는 오빠들의 말을 뒤로하고, 프림으로 풀 것이다. +23.04.16 추가 시험공부하면서 크루스칼로도 풀어보았다. 1. 문제 출처 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 설계 모든 노드를 최소 비용으로 연결해야 하기 때문에 MST 문제이고, 크루스칼 또는 프림으로 풀어야 한다. (그 외 더 ..
BFS DFS가 좀 익숙해졌으니 언젠가 태영이 오빠가 추천해준 '불'이라는 문제를 풀어보겠다. 불! 이라는 문제도 있는 거 같은데, 이 문제가 더 까다로운 모양이다. 1. 문제출처 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 갖은 고난을 맞이하여 겨우 풀어 낸 문제 ... Let's GO! 2. 설계 1) 실패한 설계 그렇다... 처음에는 각각 깊이를 파고들어 1 경로씩 탐색하고자 DFS로 접근했었다... 근데 문제가 있었으니... 바로 배열을 주고 받을 때 같은 시간 대 별로 같은 배열을 공유하지 못한다는 점이다. ..
아직도 DFS / BFS 헷갈리는 나 주말을 맞이하여 기초문제를 풀고 왔다! 1. 문제출처 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 설계 1) DFS DFS는 시스템 스택을 쌓아가며 깊이 우선으로 노드를 방문해 출력하는 형식이다. 위 링크의 1번 예제를 함께보자 4 5 1 1 2 1 3 1 4 2 4 3 4 만약 1번부터 시작한다면 1번 인접 노드는 2,3,4이고, 이 중 작은 것 먼저 선택을 한다. 다음은 2번노드가 시작되고, 2번 인접 노드는 1,4인데, ..
오늘은 나의 실패썰과 다른 분의 좋은 코드를 보며 공부한 나의 일기라고 할 수 있다. 나는 처음에 부분집합으로 해당 문제를 풀다가 '메모리 초과'가 떴었다. 그래서 내가 아직 풀기에는 어려운 문제라고 판단하여 다른 분의 코드를 보았다. 내가 참고한 블로그는 아래와 같다. [백준-2668]-[DFS]-숫자고르기 문제링크 : https://www.acmicpc.net/problem/2668 이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방 pangsblog.tistory.com 1. 문제출처 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1..
오늘은 자바 파일 입출력을 이해하는 시간을 가져야해서 조금 쉬운 문제로 가져왔다. 1. 5585번 거스름돈 - 문제 해석 (생각의 흐름) 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 가장 적게 거스름돈을 줘야하기 때문에 500엔, 100엔, 50엔, 10엔, 5엔, 1엔 순으로 큰 돈부터 줄 수 있는 수량을 계산해서 거슬러줘야한다. 때문에 나눗셈으로 거슬러줘야하는 수량을 계산하고, 나머지 연산으로 나눠주고 난 후의 돈을 계산한다. 2. 자바 코드 import java.util.Scan..
1. 그리디 알고리즘이란? 탐욕스런 알고리즘이다. 미래를 생각하지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 것이다. 때문에 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다. 2. 그리디 알고리즘이 최적의 답을 갖는 문제는? 1) 문제의 일부분에서 전체의 해답을 찾을 수 있는 경우 2) 다이나믹 프로그래밍처럼 모든 부분을 고려하는 것이 아닌 탐욕적 선택만 하더라도 최적인 답을 찾을 수 있는 경우 예를 들면 거스름돈을 가장 적게 거슬러주는 문제가 있다. 그리디 알고리즘 참고 문서 : https://seungjuitmemo.tistory.com/23 알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자! 그리디 알고리즘이란(Greedy Algorithm)이란? ..
