선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 그래프 구성 요소 정점(Vertex) : 데이터 간선(Edge) : 정점들을 연결하는데 사용 가중치 그래프 : 각 간선에 가중치(중요도, 거리등)가 있는 그래프 방향 그래프 : 정점간의 방향이 있는 그래프 DFS 깊이 우선 탐색 Depth First Search 막다른 길(더이상 연결된 간선이 없을 때 까지)이 나올 때까지 정점을 계속 방문 하는 그래프 끝까지 갔다가 다시 시작 정점으로 돌아오는 부분은 재귀함수로 구현할 수 있다. 그래프의 전체적인 모양을 파악하기 쉽다. void Dfs(int here) { // 방문 visited[here] = true;..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 과정 맨 처음 문제를 보고 너무 쉽다고 생각했다. 그냥 수열 받을 때 마다 최대값 저장해서 비교하면 되는거 아닌가? 해서 나온 코드.. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N = 0; // 수열의 크기 ve..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 과정 일단.. 문제가 너---무 단순해서 뭘 원하는지 파악하기에 당황했다. 단순히 A를 B만큼 곱하고, C로 나눈 후 나머지를 구하는건데, A를 B만큼 곱하는 과정에서 뻔하게 A를 B만큼 for문으로 곱하면 100000% 시간초과에 걸릴 것 같고.. C로 나누는 거에 뭐가 있나? 싶기도 하고.. 일단, 시간 초과 관련해서는 아래와 같은 코드를 작성해줌으로서 조금 완화된다는 것을 알고 있다. ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 거듭제곱에 대한 또다..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 과정 음.. 그니까 내집 기준 앞번호, 뒷번호랑 집의 색까리 같으면 안된다. 그리고 색칠하는 비용이 모두 다르고, 최소값을 구하라고 하니까, DP와 min을 사용해서 코드를 짜볼것이다. 고민을 가장 많이 한 부분은 단순 최소값만 생각할게 아니라, 색의 종류도 함께 고민을 해야한다는 점이었다. key:value로 넣을 것인지, 아니면 그냥 RGB순서로 인덱스로 구분할 것인지 고민했다. : 이 부분은 코드를 짜다보니, 어차피 DP라는 특성상 현..

문제 min함수에 대해 오류가 발생했다. 과정 처음에는 #include 을 빼먹었길래 이거때문인줄 알고 추가했는데, 해결되지 않았다. 그래서 오류내용을 다시보니;; gcc-11.1.0/include/c++/11.1.0/bits/stl_algobase.h: In instantiation of ‘constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare) [with _Tp = int; _Compare = int]’: 라고 한다. 즉, min() 자체에는 2개 인자만 받을 수 있다는 것. 근데 분명 내 기억속에 min에 3개 이상을 받았던거 같은데 이상했다. 그래서 검색해보니, min(a, min(b, c)) 이렇게 작성하던가, min({a, b, c}) ..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 과정 원하는 채널에 가장 가까운 번호(W) 찾기 → 100에서 W 까지 버튼 수 체크 → (W - 원하는 채널) 해서 +,-수 체크 이런식으로 계획했다. 원하는 채널에 가장 가까운 번호를 어떻게 찾는지가 가장 처음으로 고민한 주제이다. 원래는 원하는 채널 번호 기준 가장 가까운 채널번호를 구해서 +, -수만 더 추가하려고 했는데, 생각해보니 100부터 시작이니까 가장 가까운 채널번호가 가장 적게 버튼을 누른다는 보장도 없고, 버튼이 죄다 고장났..

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 과정 이미 문제에서 그래프라고 보여주기 때문에 DFS냐 BFS냐 만 고르면 되는데 이건 DFS가 맞다 싶어서 바로 DFS로 접근했다. 2606문제와 살짝 다른점은, 간선으로 연결된 정점 뭉치들의 개수를 알고 싶기 때문에, 연결될 때마다 answer을 추가하는게 아닌, DFS를 입력할 때 접근하지 않은 정점일 때! 이때 answer을 추가했다. 코드 #include #include using names..

7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 과정 문제를 보자마자 배추벌레나 컴퓨터 바이러스처럼 DFS가 생각났다. 다만, 이전 문제들과 다르게 3차원벡터가 필요할 것 같았고, 이 부분에서 생각이 오래 걸렸다. 토마토가 익는데는 하루가 필요하고, 분명 중복되게 인접하는 토마토가 있을텐데 이것과 관련하여 최소 일자를 그냥 DFS를 사용해서 구해버리면 되는건가 했다. → 여기서부터 실수였다. 몇일 동안 문제를 풀면서 DFS만 사용했더니 BFS를 잊고 있었다. 이 문제는 한개의 정점으로부..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 과정 지금껏 풀었던 문제와 다르게 문자열형식으로 받아서 그 중 정수만을 빼내야할 것 같았다. 여기서부터 해결하기로 했다. R과 D의 함수자체는 어렵지 않은데, 테스트케이스와 배열의 크기가 커서 타임오버가 걸리지 않을까 걱정했다. 처음 시도는 리스트로 테스트케이스를 굴렸다. 왜냐하면, 1. 함수 R을 할 때 노드 화살표만 바꿔주면 될거 같아서 2. 함수 D를 할 때 벡터로하면 인덱스 정렬을 다시 해줘야할거 같아서 근데 의문이 들었다. 일단 저 코드처럼 R이 나올 때 마다 꼭 뒤집어져야하는가? 그냥 뒤집었는지 아닌지만 알..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 과정 한 컴퓨터 기준 연결되어있는 모든 컴퓨터를 조사하는 느낌으로 저번에 풀었던 배추벌레? 문제랑 비슷한 것을 느꼈다. 그래서 DFS로 계획을 세웠다. 코드 처음에는 이렇게 작성했는데, 터미널을 보면, 2번 컴퓨터와 연결된 컴퓨터 개수가 1개라고 찍힌다. 그 이유는 main에서 시작 컴퓨터 벡터에만 연결상태를 입력했기 때문이다. #include #include using namespace std; int node = 0; // 컴퓨터 수 int edge = 0; //..