알고리즘66 [BOJ] 14501. 퇴사 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 돈미새 백준이.. 주요 아이디어 풀 때마다 항상 느끼지만 DP 문제는 정말 아이디어가 중요한 것 같다.. 앞에서 (i=1) 부터 접근하지 말고, 맨 끝 날짜부터 접근해보자 매 상담에 대해 현재 상담일자의 이윤 + 현재 상담을 마친 일자로부터의 최대 이윤 계산 즉 dp[i] = i번째 날 ~ n번째 날까지 낼 수 있는 최대 이익이다 예제 살펴보기 더보기 7일차에는 상담이 불가하다 상담 소요 일자 + 현재 일자 = 2 + 7 > n 이기 때문이다 dp[7] = 0, max_value = 0 6일차에도 상담이 불가능하다 상담 소요 일.. 2024. 4. 6. [BOJ] 14502. 연구소 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 주요 아이디어 굉장히 기초적인 BFS 문제이다. 기본적인 아이디어는 다음과 같다 빈 칸 중 벽을 세울 칸 3개의 좌표를 조합으로 뽑아낸다. 문제 조건 중 "무조건 3개의 벽"을 세우라고 했기 때문에 별다른 예외처리는 안해도 된다 조합 순회를 돌면서 벽을 세우고, 해당 벽을 세웠을 때 바이러스가 전파된 경우를 확인한다 바이러스 전파는 bfs 방식으로 체크한다 원본이 바뀌는 것을 막기 위해 bfs 진행 시마.. 2024. 4. 6. [프로그래머스] 사칙연산 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 너무 어렵다 ㅠㅠㅠ.. 주요 아이디어 DP 형식으로 풀어야 한다 (그리디로는 최적값을 보장하지 않는다) 괄호를 어디 치느냐에 따라서 연산 결과가 달라지기 때문에, 각 경우를 모두 dp 배열에 저장해두어야 한다. -> 각 구간별 연산의 최대값을 저장해두자 이 때!! 또 한 가지 중요한 것이 있다. 바로 '뺄셈'의 존재! 연산 기호가 덧셈일 때는 '연산자 위치 이전 최대값' + '연산자 위치 이후.. 2024. 4. 5. [프로그래머스] 퍼즐조각 채우기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주요 아이디어 처음에는 좌 -> 우, 상 -> 하 방향으로 board 판을 이동하면서 계속 탐색해나가는 과정을 생각했으나 풀이 과정이 복잡해져서 중간에 포기했다. 핵심 아이디어는 빈칸의 좌표 & 블록의 좌표를 dfs로 구하고 해당 좌표를 (0, 0) 위치로 이동시키는 것이다. 이렇게 하면 비교하기도 편해지고, 단, 주의할 점은 블록 회전이 가능하다는 것! -> 즉 회전 횟수 4번의 경우에 대.. 2024. 4. 2. [BOJ] 1260. DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 주요 아이디어 기본적인 DFS, BFS 구현 문제 따로 저장하지 말고 방문할 때마다 방문 처리로 출력을 진행해주자 문제에 명시되어 있진 않으나 예시를 보고 노드가 오름차순 정렬임을 유추할 수 있음 코드 구현 (Python 3) 더보기 def dfs(graph, v, visited): visited.append(v) print(v, end=' ') # 인접.. 2024. 4. 1. [알고리즘] 01. DFS & BFS 사담 공간 내가 제일 어려워하는 파트... 코테 전까지 문제도 많이 풀어봐야겠다 포스팅 순서는 그냥 코테 자주 출제되고 내가 잘 못푸는 순서대로.. 키워드 #DFS #BFS #최단경로 1. DFS (Depth-First Search) 깊은 부분을 우선적으로 탐색하는 알고리즘 좀 더 자세히 풀어서 설명하면, 정점 v의 모든 간선이 조사된 후 v를 발견하게 해준 정점으로부터 나오는 간선을 조사하기 위해 뒤로 되돌아간다. 발견되지 않은 정점이 하나라도 남아 있으면 그 중 하나를 새 출발점으로 선택하고, 해당 출발점으로부터의 검색을 모든 정점을 방문하기 전까지 반복한다. 즉, 시작 지점으로부터 가장 멀리 있는 노드부터 탐색하게 된다. 동작 과정 탐색 시작 노드를 스택에 삽입 후 방문 처리 스택의 최상단 노드에 .. 2023. 9. 11. 이전 1 ··· 5 6 7 8 9 10 11 다음
