첫날이라 정신도 없고, 서버도 말썽을 많이 부려서 테스트하기 많이 힘들었다. 서버 계속 터져서 중간에 때려 칠려고 한건 비밀~ 그래도? 결과가 잘 나와서 기분 좋게 집에 갈 수 있었다. 문제 분석 0과 1은 세트 문제라서 1풀면 0은 그냥 돌려서 풀 수 있는 단순 출력문제로 나왔다. A1. 테스트 문제라 그런지 A1번은 대회 안내할 때, 문제 예제로 나왔던 문제가 그대로 나왔다. 2일 동안 주차된 위치가 주어지고, 한번도 주차되지 않았거나 2일 연속으로 주차된 공간의 수를 출력하는 문제이다. 1차원 배열에 체크하면서 0인 것과 2인 것의 수를 세서 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..
정렬된 배열에서 최대와 최소를 잡고 중앙값을 이동시킨다. 그러다 보면 원하는 값이나 위치에서 멈추게 된다. 이것을 이분 탐색(Binary search)이라고 부른다. 기본적인 탐색은 다음과 같이 진행할 수 있다. low = 배열의 시작 인덱스 high = 배열의 끝 인덱스 while(low < high) { 1. low와 high의 중앙값을 찾음. 2. 중앙값이 원하는 수보다 큰지 작은지 판별 3. 큰 경우 : low = mid+1 작은 경우 : high = mid-1 } 탐색이 끝난 후에는 조건을 어떻게 처리했느냐에 따라 답이 저장되는 변수가 달라진다. (그래 봐야 low, middle, high 중이지만...) 하지만 이 테크닉을 실전에서 사용하기 위해서는 약간의 가공(?)이 필요하다. 이것을 매개 ..
https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 매우 쉬운 문제이다. 배열에 막대기의 길이를 전부 입력받고, 뒤에서부터 보면서 현재보다 더 큰 것을 체크해주며 진행하면 된다. 구현된 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /* ID : Literhyeon LANG : C++ */ #include using namespace std; i..
본격적으로 최단 경로 알고리즘에 대해 알아보자. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for문으로 구현하여 최단 경로를 알아내는 알고리즘이다. 본격적으로 구현하기 전에 몇가지 세팅이 필요한데... 우선 연결 관계를 표현할 배열이 하나 필요하다. 그리고, 자기 자신으로 가는 것은 최단 경로가 0이므로 그대로 둔다. 입력은 두 정점과 가중치가 주어진다. 두 정점이 연결되어 있다는 것을 배열의 [정점A][정점B] = 가중치의 형식으로 나타낸다. 정점들의 연결 관게와 가중치가 모두 처리 되었다면! 자기 자신으로 가는 경우에는 0으로 처리하고, 배열에 저장된 값이 없으면 절대 나올 수 없는 수로 처리해 준다. 이제 본격적으로 플로이드 와샬 알고리즘을 사용해 최단 경로를 구할 건데... 원리는 다음..
최단 경로 알고리즘을 하기 전에 백트레킹을 이용해서 최단 경로를 찾는 코드를 짜 보자! 그래프 용어 그래프에서 사용하는 용어는 다음과 같다. 정점 : 한 지점을 나타낸다. 간선 : 정점과 정점을 연결한 것을 나타낸다. 가중치 간선 : 정점과 정점 사이를 이동하는데 드는 비용이나 힘이 표시된 간선 그래프의 표현 그래프는 크게 2가지로 표현할 수 있다. - 인접행렬 - 인접리스트 배열로 그래프를 구현해 놓은 것을 인접행렬이라고 부른다. 구현은 매우 간단하다. 두 정점의 연결 관계가 입력되었을 때, (vertex1, vertex2)와 (vertex2, vertex1)에 체크 또는 가중치를 넣어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 //인접행렬에 체크하기 while(m--) { int..
이분 탐색은 원하는 값을 찾을 때, 완전탐색보다 더 빠르게 찾을 수 있는 알고리즘입니다. 일반적인 탐색보다는 나중에 매개 변수 탐색에 더 많이 사용되지만, 기본적인 탐색도 알아두면 좋습니다. 먼저 정렬을 해 주는 것이 중요합니다. 그 이유는 중앙값을 기준으로 값을 찾아 나갈 것인데, 정확한 기준이 없다면 중앙값을 어떻게 바꿔 나가야 하는지를 모르기 때문입니다. 그 다음! 양끝 지점을 잡고, 그 중앙값에 따라 판별을 합니다. 이 판별은 두가지 경우로 나뉘게 됩니다. 1. 찾는 값이 중앙값보다 큰 경우 - 작은 지점을 중앙값으로 갱신합니다. 2. 찾는 값이 중앙값보다 작은 경우 - 큰 지점을 중앙값으로 갱신합니다. 이렇게 판별하는 이유는 중앙에 있는 값보다 작다면? 굳이 더 큰 수들을 볼 필요가 없기 때문입..
DFS와 BFS는 그래프 탐색의 기초적인 알고리즘입니다. 이것을 기반으로 구현할 수 있는 알고리즘도 있으니 꼭 알고 있어야만 하는 알고리즘이기도 합니다. 그래프 탐색을 하기 전에 알아두면 좋은 몇가지 용어가 있는데, ( 아래 그림을 참조... ) 정점 : 동그라미 안에 숫자가 있는 것을 정점이라고 한다. 간선 : 정점을 이어놓은 부분을 간선이라고 한다. 1. DFS ( 깊이 우선 탐색 ) DFS는 깊이를 우선으로 탐색하는 알고리즘입니다. 시작 노드와 연결된 것을 쭉 타고가서 더 이상 연결된 것이 존재하지 않을 때까지 탐색을 한 다음에 그 다음 연결된 노드에 이 과정을 반복하며 탐색하는 방법입니다. 다음 그림을 보면, 깊이 우선 탐색을 1부터 진행하여 나오는 결과는 1 -> 2 -> 7 -> 8 -> 9 ..
//1250 int f() { int idx = 1, MAX = d[0]; for(int i=0; i MAX) { M = d[i]; idx = i+1; } } return idx; } //1251 long long int f() { long long int MAX = 0; for(int i=1; iMAX?d[i]:MAX; } long long int ans = MAX; for(int i=1; i0) { printf("positive"); } else { printf("negative"); } } } //1257 void f(int k) { int count = 0; for(int i=2; i= 1) { printf("composite"); } else { printf("prime"); } } //1258..