분류 전체보기 69

[삼성 SW 역테 - 2022 하반기 1/2] - 코드트리 빵

문제: 삼성 SW 역량테스트 - 2022 하반기 1번문제 출처: 코드트리 - 코드트리 빵 제한 격자 크기 n: 2 ~ 15 사람 수 m: 1 ~ min(n^2, 30) 베이스 캠프 수: m ~ n^2-m 유형 Goal: 사람들이 모두 편의점에 도착하는 시간 1. 1 ~ m번 사람은 출발시간 1 ~ m분에 각자의 베이스캠프에서 출발하여 편의점으로 이동한다. start: 각자의 베이스캠프 end: 각자의 목표 편의점 출발시간 이전엔 격자 밖에 나와있다. 목표로 하는 편의점은 모두 다르다. 2. 진행 순서 격자 내 사람은 목표 편의점으로 최단거리로 1칸 움직인다. => BFS 여러 경우라면 ("위", "왼", "오", "아래")의 순서로 우선순위를 갖는다. 편의점에 도착 시, 이때부터 다른 사람들은 해당 편의..

[BOJ 16401] 과자 나눠주기

시간복잡도 시간제한: 1초, 메모리: 128MB 조카 수 M (1 ~ 1,000,000) 과자 수 N (1 ~ 1,000,000) 과자의 길이 L (1 ~ 1,000,000,000) 가능한 시간복잡도: O( log scale * M or N) 유형 분석 Goal: 조카 1명에게 줄 수 있는 막대과자의 최대길이 조카수: 4 과자수: 3 과자N개의 길이: [10 10 15] 과자N개의 길이에 대해, 특정 x길이로 나눈 몫들의 합을 count라 하자. count < 조카수라면, 모든 조카에게 나눠줘야한다는 조건을 만족하지 못하고 무조건 더 작게 잘라야 한다. (※ 모든 조카에게 나누어줘야하기 때문) 아래의 그림을 살펴보면 이해가 될 것이다. mid 값 이상의 값은 모두 조건을 만족하지 못하는 F A L S E..

[BOJ 6236] 용돈관리

리뷰 사이사이 생략된 말들이 조금 있어서 문제 해석이 굉장히 어려웠던 문제이다. 남은 금액: 인출한 금액 - 하루사용금액 하루사용 금액 100 400 300 100 500 101 400 남은금액 500(인출) 400 0 500(인출) -> 200 100 500(인출) -> 0 500(인출) -> 399 500(인출) -> 100 총인출횟수 1 1 1 2 2 3 4 5 조건A: "남은 금액이 그날 사용할 금액보다 많아도 다시 인출가능하다" 조건A로 의해, 인출금액이 x일 때 총 인출 횟수가 M이하이면 결국 정확히 M번 인출해야하는 조건을 성립하게 된다. 인출금액의 범위: [하루 사용할 금액들의 max값 ~ 하루 사용할 금액들의 sum값] 이기 때문이다. max값부터 시작하는이유: 인출금액이 max값보다 적..

[백준 19583] 싸이버 개강 총회 -구현, 문자열, HashSet

https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net [설계] 1. (00:00 ~ S) in HashSet에 입장체크를 한다. 2. (E ~ Q) out HashSet에 퇴장체크를 한다. 3. 입장한 사람들에 대해 퇴장했는지 확인한다. 시간복잡도: O(채팅기록) = O(100,000) ※주의: (E ~ Q)입력에 대해 입장체크 in의 존재여부로 바로 확인하면 안된다. (채팅 중복이 있기 때문) [알게된 내용] ..

알고리즘/구현 2023.02.07

[백준 2206, 14442] 벽 부수고 이동하기 1, 2

문제 리뷰 0-1 BFS의 정의에 대해 다시 한번 생각하게 된 문제. 0-1 BFS에서 최소거리를 생각할 때, "상태"를 고려해야함을 알게 된 문제. 시간 복잡도 시간제한: 2초, 메모리: 192MB N x M 격자 (N,M: 1,000) O (200 x N^2) 까지 가능 유형 (1,1) → (N,M) 최단 경로 최단 거리 구하기 0-1 BFS ( v ) 문제의 조건에 따라, 가중치 (weight): 한 칸으로 모두 동일하므로 가능 다익스트라 플로이드-워셜 벨만 포드 0-1 BFS "상태" 고려하기 설계에 들어가기 앞서, 0-1BFS 최단거리에 대해 다시 한번 생각해보자. 1. BFS는 "동시에" 퍼져나가는 구조이다. 각 이동은 각각의 "상태"를 가지고 있다고 생각할 수 있다. (1,1) → (1,2)..

DFS로 조합구하기

Remember 해당 포스팅은 https://www.acmicpc.net/problem/17471 문제를 풀며, 조합을 구하는 과정에 시간 소요가 많이 되어 다시 한번 dfs로 조합을 구하는 방법에 대해 정리하고자 한 글이다. 이 외의 문제들 중에서도, 조합 + @를 요구하는 문제가 빈번히 나오기 때문에 조합을 구하는 구현부분에서 시간이 막히면 안되고 이를 개선하고자 글을 작성하고자 한다. dfs 설계 dfs 재귀 탐색은 기본적으로 트리 자료구조를 재귀적으로 방문하는 논리적인 구조를 갖고 있기 때문에 설계 단계에서 가상의 트리 (State-Space Tree. 이하 SST)를 작성하여 접근한다면, 구현 실수를 미연에 방지할 수 있다. SST 설계 ex) [1, 2, 3, 4]의 nCr 조합을 구하시오. ..

알고리즘 2022.12.30

[백준10026] 적록색 약 - 완전탐색, 그래프탐색 (dfs, bfs), 그래프탐색 심화 정리

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 시간 복잡도 N x N 칸 (N: 100) 중복 없이 방문: O(N^2) 문제 유형 완전 탐색 인접 4방향 그래프 탐색 (dfs, bfs) 설계 dfs, bfs 그래프 탐색의 난이도가 올라갈 수록 "갈 수 있는가?" 조건을 정확히 파악하여 설계하는 것이 중요하다. (dfs, bfs 설계에 대한 포스팅은 이전 글을 참조) 해당 문제의 경우 색약인 사람과 아닌 사람의 "갈 수 ..

Union-Find (Disjoint-Set)

Union-Find (Disjoin-Set) 집합들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 시간복잡도: O(log V) (경로 압축 시) Union-Find 설계 1. 서로소 집합 초기화 자신의 부모가 자기자신을 가리키도록 초기화 for (i: 1 ~ N) parent[i] = i 2. Find 연산: find (a) 주어진 원소가 속한 집합의 대표번호 (루트) 반환 경로 압축 진행 X: O( V ), (가역적) // O(V) find (a) if parent[a] == a → return a else return find(parent[a]) 경로 압축 진행 O: O( log V ), (비가역적) // O(log V) find (a) if parent[a] == a → retu..

[백준11724] 연결 요소의 개수 - 완전탐색(dfs,bfs), Union-Find, 그래프 표현(2차원배열, 연결리스트)

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제분석 시간복잡도 노드개수 V (1000개) 엣지개수 E ( V^2 ) 무방향 그래프, 연결요소 파악 1) 그래프 표현: 2차원 배열 노드 한개와 연결된 노드를 순회하는 비용: O( V ) → 완전탐색 비용: O( V ^ 2 ) (∵노드 개수 V개) 2) 그래프 표현: 연결리스트 배열 노드 한개와 연결된 노드를 순회하는 비용: ..

[백준2667] 단지번호붙이기 - 완전탐색, 그래프탐색, dfs, bfs

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 분석 시간 복잡도 N x N 지도 (N = 25) 영역 탐색 (그래프 탐색) 중복방문 X O( N ^ 2) 문제 유형 그래프 탐색 시간 복잡도 상, 완전탐색 (dfs, bfs) 가능 설계 dfs와 bfs는 기본적으로 "탐색" 알고리즘이다. 따라서, 연결된 곳 (순회할 수 있는 곳)이 어디있는지 파악 연결된 곳으로 방문할 수 있는지 파악 하는 것이 중요하다. 해당 문제의 경우, 연결된 곳은..