알고리즘

https://www.acmicpc.net/problem/19242007년 1월 1일이 월요일일 때,2007년 x월 y일은 무슨요일인가365일 -> 완전탐색1월 1일 -> x월 y일 날짜차이 : kk % 7 요일month를 체크할 때 리스트가 아닌 집합을 사용

2108번: 통계학1\. 산술평균 : N개 합 / N2\. 중앙값 : N개 수 오름차순 시 중앙위치 값3\. 최빈값 :가장 많이 출현하는 값4\. 범위 :최댓값 -최솟값입력1\. 1 <= N <= 5000002\. N은 홀수3\. 정수 절대값 <=

2839번: 설탕 배달설탕 N kg을 배달하고자 한다.3kg, 5kg 봉지를 이용해서 배달한다.최소 봉지 개수 구하기불가능한 경우 -1 출력그리디3, 5는 배수관계가 아니다.3만 가능한 경우의 수를 구한다.→ 3, 6, 9, 125로 최대한 뺀 후 3, 6, 9, 12

1260번: DFS와 BFS여러 간선 정보를 통해 그래프가 주어진다.이때 DFS와 BFS 알고리즘을 통해 그래프를 탐색한다정점 번호가 작은 것을 우선 방문한다.DFSBFSBFS 탐색을 위해서는 queue 자료구조가 필요하다. 이때 queue 자료구조를 위해서 세 가지

2178번: 미로 탐색1 : 이동가능 칸0 : 이동불가능 칸(1, 1)에서 (n, m)으로 이동할 때 이동한 최소 칸 수를 구하라BFS인접칸으로 이동할 때 이동한 칸 수 저장

2667번: 단지번호붙이기인접한 집들의 단지 구성하기인접 : 상하좌우 (대각선 포함안함)각 단지의 집 수를 오름차순 출력하기1 : 집0 : 집 없는 곳dfs로 단지파악하기집일 경우 count + 1위 코드에 경우에 data는 mutable object인 list이기 때

2606번: 바이러스인접 바이러스가 모두 감염1번 정점이 바이러스일 때 감염되는 컴퓨터(정점) 수dfs그래프 탐색 후 방문한 정점 개수 - 1 출력1번 컴퓨터를 통해 감염된 컴퓨터 수이므로 1번 컴퓨터 제외

7576번: 토마토문제익은 토마토에 인접한 토마토도 하루 뒤 익는다.인접 : 상하좌우혼자 익는 경우는 없다.보관된 토마토가 모두 익는 최소 일 수입력 조건m : 가로 칸 수 (열), n : 세로 칸 수 (행)2 ≤ m, n ≤ 10001 : 익은 토마토0 : 안 익은

1697번: 숨바꼭질수빈 N(0 ≤ N ≤ 100000)에서 동생 K(0 ≤ K ≤ 100000)까지 이동현재 위치를 X라 할 때,걸으면 1초 후 X - 1 또는 X + 1로 이동순간이동을 하면 1초 후 2 \* X로 이동동생까지 이동하는데 가장 빠른 시간BFSX

1012번: 유기농 배추지렁이는 인접 배추로 이동 가능 → 인접한 배추에는 1마리만 있으면 된다.인접 : 상하좌우필요한 지렁이 최소 수0 : 배추 없는 땅1 : 배추DFS인접한 배추들의 구역 수를 구한다.sys.setrecursionlimit(10000)을 하는 이유가

11724번: 연결 요소의 개수정점 개수 N, 간선 개수 M연결 요소의 개수를 구하라그래프 탐색을 하면서 각 정점 방문 처리방문하지 않은 노드를 탐색할 때 마다 연결요소 + 1sys.stdin.readline을 쓰는 이유입력 연산을 빠르게 할 수 있다.

출처. 이것이 취업을 위한 코딩테스트다 \[나동빈]DFS는 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 보기 전에 그래프(Graph)의 기본 구조를 알아보자.그래프는 정점(node, vertex)과 간선(Edge)으로 표현된다

출처. 이것이 코딩테스트다 \[나동빈]그리디(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 국내에서는 탐욕법이라고도 한다. 이름처럼 단순하게 탐욕적으로 문제를 푸는 알고리즘이다. 그렇다면 탐욕적으로 푼다는 것이 무슨 말일까?현재 상황에서 지금 당장 좋

2667번: 단지번호붙이기정사각형 지도1 : 집이 있는 곳0 : 집이 없는 곳인접한 집끼리 단지 구성인접 : 상하좌우단지수 출력 후, 각 단지에 속하는 집 수를 오름차순으로 출력DFS 탐색으로 단지 구성단지에서 집마다 count + 1오름차순은 계수정렬로 구현공백없는

출처. 이것이 취업을 위한 코딩테스트다 \[나동빈]BFS는 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색한다면 BFS는 그 반대다. BFS의 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 큐에 넣

2178번: 미로 탐색1 : 이동가능 칸0 : 이동불가능 칸(1, 1)에서 (n, m)으로 이동할 때 이동한 최소 칸 수를 구하라BFS인접칸으로 이동할 때 이동한 칸 수 저장이전에 방문한 칸에 저장된 이동 수 + 1

출처. 2차원 누적합, 부분합 구하기2차원배열에서 부분 배열의 합을 구하는 방법을 알아보자. 이중 for를 이용해서 구할 수 있지만 시간복잡도가 O(n^2)이 되기 때문에 더 효율적인 방법을 찾아보자.다음과 같은 배열이 있다고 가정하자.위 배열에서 연속된 구간의 합,