Learn From Failure

/* 1. 문제 분석     1) M * N 크기의 보드 내용을 입력받는다.     2) 보드에서 8*8 크기로 잘라내어 체스판을 만들건데, W와 B가 번갈아서 칠해져 있어야 한다.     3) 잘라낸 뒤 몇 개의 정사각형을 다시 칠하는 방식으로 체스판을 만든다면,         칠해야 하는 정사각형의 최소 개수는? 2. 제약 조건     1) 8 3. 의사결정     1) 첫줄에서 N과 M을 받는다. 보드 리스트를 만들어놓는다. 최소값 비교하기 위해서 일단 최대숫자 넣어놓기    2) N개의 줄에 걸쳐 보드 내용을 받아서 보드 리스트에 넣는다. = 이중리스트 만들기     3) 보드 리스트의 0,0부터 완전탐색을 하면서 8*8크기만큼 확인해서 몇개를 바꿔야하는지 카운트한다.    - (0,0)이 W라면..

Algorithm 2025. 2. 4. 10:57

1. 문제 분석     1) 테스트케이스 T에 대해, 첫째 줄에 V E 가 주어지고 둘째줄부터 E개 줄에 걸쳐 u v가 주어짐     2) 여러개의 테스트케이스가 있다.     3) 해당 그래프가 이분 그래프이면 YES, 아니면 NO를 출력한다.     4) 이분그래프인지 아는 법         - 이분그래프 : 그래프의 모든 정점이 두 그룹으로 나눠지고, 서로 다른 그룹의 정점이 연결되어있음             = 인접한 정점끼리 칠하면 서로 다른색으로 칠해져야 함             = 인접한 정점끼리 나누면 딱 두개로 나눠져야 함             = 빨간색은 파란색이랑만 인접해야 하고.. 파랑은 빨강이랑만 인접해야 한다.         - BFS, DFS를 사용해서 구할 수 있다.     ..

Algorithm 2025. 1. 24. 01:36

1. 문제 분석     1) 크기가 N*N인 정사각형 모양의 지도에서 단지의 수와 각 단지 안의 집 수를 구한다.     2) 집이 있는 곳은 1, 집이 없는 곳은 0     3) 상하좌우로 집이 붙어있다면 같은 단지. 대각선은 x 2. 제약 조건     1) 5 3. 의사결정     1) N을 입력받고, N만큼 이중 배열을 초기화한 뒤 데이터를 입력받는다.     2) 0,0 부터 차례대로 돌다가 집을 발견하면     3) dfs 수행한다. 이번엔 스택 써보기! 방문처리는 0으로 바꾸기     4) dfs 수행하면서 집의 개수를 세어서 배열에 저장한다.     5) 모두 끝났으면 단지 개수 +1 4. 문제풀이     1) dfs 탐색할때 조건 : 방문하지 않은 집인경우 && 배열 범위 안에 있는 경우 ..

Algorithm 2025. 1. 23. 10:25

1. 문제 분석     1) 첫째줄에서 정점 개수 N, 간선 개수 M, 시작 번호 V가 주어진다.     2) M개의 줄에 걸쳐서 연결되는 두 정점의 번호가 주어진다.     3) 첫째 줄에 DFS 수행한 결과 출력 - 방문된 점 순서대로 출력     4) 둘째줄에 BFS. 2. 제약 조건     1) 1     2) 1     3) 방문할 수 있는 정점이 여러개인 경우 작은 정점부터 방문한다. 3. 의사결정     1) N, M, V를 받는다.     2) N, N 크기의 불형 이차원 배열을 만들고 (a, b), (b, a)를 true로 바꾼다.     3) dfs 함수를 만들고 호출한다. 더이상 방문할 점이 없는 경우 종료 -> 순서 출력한다.     4) bfs 함수 만들고 똑같이 출력 4. 문제풀..

Algorithm 2025. 1. 20. 23:09

1. 문제 분석     1) N개의 용액이 주어지고, 두 개의 용액을 혼합했을 때 특성값이 0에 가장 가까운 조합을 찾는다.     2) 산성 용액(양수)과 알칼리성 용액(음수)이 섞일 수도 있고, 같은 종류의 용액끼리 섞일 수도 있다.     3) 결과는 오름차순으로 출력해야 한다. 2. 제약 조건     1) 2 ≤ N ≤ 100,000 (최대 10만 개의 용액)     2) 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하.     3) 시간 복잡도는 O(N log N) 이하로 해결해야 함. 3. 의사결정     1) 용액을 오름차순으로 정렬한다.     2) 투 포인터 알고리즘을 사용하여 최적의 두 용액을 찾는다.     3) 왼쪽 포인터(left)는 리스트의 처음부터..

Algorithm 2025. 1. 17. 23:34

1. 문제 분석     1) N개의 강의를 M개의 블루레이에 나눠 담는다.     2) 강의 순서는 유지되어야 하며, 연속된 강의를 하나의 블루레이에 넣어야 한다.     3) 모든 블루레이의 크기가 같아야 하며, 크기를 최소로 해야 한다. 2. 제약 조건     1 ≤ N ≤ 100,000     1 ≤ M ≤ N     각 강의 길이는 10,000 이하 3. 의사결정     1) 블루레이 크기의 최솟값을 이진 탐색으로 찾는다.     2) 최소 크기는 가장 긴 강의(최소 블루레이 크기)부터 시작한다.     3) 최대 크기는 모든 강의를 하나의 블루레이에 담는 경우(총 길이)로 설정한다.     4) 중간값(mid)을 블루레이 크기로 설정하고, 해당 크기로 블루레이를 M개 이하로 나눌 수 있는지 확인..

Algorithm 2025. 1. 17. 00:07

1. 문제 분석     1) 랜선을 잘라 N개의 같은 길이의 랜선을 만들어야 한다.     2) 주어진 K개의 랜선 길이를 기반으로, N개의 랜선을 만들 수 있는 최대 길이를 구한다.     3) 이진 탐색을 사용해 최대 길이를 효율적으로 찾는다. 2. 제약 조건     1 ≤ K ≤ 10,000     1 ≤ N ≤ 1,000,000     각 랜선의 길이는 2^31 - 1 이하의 자연수     항상 K ≤ N 3. 의사결정     1) 이진 탐색을 사용하여 랜선 길이의 최댓값을 찾는다.     2) 주어진 길이로 랜선을 잘랐을 때 N개 이상이 되는지 확인한다.     3) 조건을 만족하는 최대 길이를 업데이트한다. 4. 문제 해결     1) 랜선의 길이를 기준으로 이진 탐색 범위를 설정한다.    ..

Algorithm 2025. 1. 15. 09:09

1. 문제 분석 1) 테스트케이스 T 2) 각 테스트케이스에서 수첩1에 있는 N개의 정수와 수첩2에 있는 M개의 정수가 주어진다. 3) 수첩2의 각 정수에 대해 수첩1에 포함되어 있는지 확인하여, 포함되어 있으면 1, 없으면 0을 출력한다.2. 제약 조건 1 ≤ N, M ≤ 1,000,000 모든 정수는 int 범위 시간 복잡도를 고려해야 한다.3. 의사결정 1) 수첩1의 모든 정수를 HashSet에 저장한다. 2) 수첩2의 각 정수에 대해 HashSet에 포함되어 있는지 확인한다. 3) HashSet은 탐색 속도가 O(1)이므로 대량의 데이터를 처리하기에 적합하다.4. 문제 해결 1) HashSet을 사용하여 수첩1의 정수들을 저장한다. 2) ..

Algorithm 2025. 1. 14. 01:12