예전에 풀어본적이 있던 유형의 문제 같은데 풀이가 잘 생각나지 않았다. 다른 사람의 풀이를 보고 대충 힌트를 얻어 구현했다. https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net #include using namespace std; int n, result = INT_MIN; string s; int cal(int a, int b, char op){ switch(op){ case '+': a += b; break; case '*': ..
dfs를 이용하여 푸는 문제이다. 풀이를 생각해보는데 쉽게 떠오르지 않았다. 고민 끝에 다른사람의 풀이를 참고하였다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include using namespace std; vector node[10002]; bool visited[10002] = {false,}; int result = 0; int endPoint = 0; void dfs(int p, int len){ if(v..
[ OpenCV ] 도로 차선 인식 프로그램
도로 차선을 인식하는 프로그램을 만들어보았다. OpenCV를 사용하고 언어는 C++을 사용했다. 1. 구현 순서 및 설명 구현한 순서는 다음과 같다. (1) 원본 영상을 읽어오기 (2) 흰색, 노란색 범위에 있는 것만 필터링하여 후보로 저장 (3) 영상을 GrayScale로 변환 (4) Canny Edge Detection으로 에지를 추출 (잡음 제거를 위한 Gaussian 필터링도 포함) (5) 자동차의 진행 방향 바닥에 존재하는 차선만을 검출하기 위한 관심 영역을 지정 (6) Hough 변환으로 에지에서의 직선 성분을 추출 (7) 추출한 직선 성분으로 좌우 차선에 있을 가능성이 있는 직선들만 따로 뽑아서 좌우 각각 직선을 계산하고 선형 회귀로 가장 적합한 선 찾기 (8) 자동차의 진행 방향을 예측 (..
[ 리눅스 ] 네트워크 소켓 프로그래밍으로 파일 다운로드/업로드 클라이언트, 서버 만들기
리눅스에서 네트워크 소켓 프로그래밍을 이용해 파일을 다운로드하고 업로드할 수 있는 클라이언트와 서버를 만들어보았다. - 파일 전송 서버는 서버에서 실행중이며 클라이언트가 다운받고자 하는 파일을 전송하는 역할을 한다. - 파일 전송 클라이언트는 서버에 전송할 파일을 선택하여 전송(업로드)한다. - 클라이언트는 접속한 디렉토리에 대해서 파일을 업로드, 다운로드 하도록 한다. - text파일과 binary 파일 모두 전송이 가능하도록 한다. 명령어들은 다음과 같이 구현했다. cd : 현재 디렉토리 이동, get : 다운로드 명령, put : 업로드 명령, quit : 종료 명령 #include #include #include #include #include #include #include #include #d..
bfs 문제인데, 조금 응용이 필요한 문제였다. 풀이를 고민하다가 두가지 의문이 풀리지 않아서 다른 사람의 풀이를 참고하여 풀었다. 다음에 비슷한 유형의 문제에서는 잘 풀 수 있었으면 좋겠다. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 위에서 말한대로 풀지 못했던 두 가지 의문을 다음과 같이 풀었다. 1) 이 문제는 지금껏 풀었던 문제와 다르게 방문했던 곳을 다시 방문할 수도 있다. 열쇠를 구하러 갔다가 다시..
bfs문제 중 조금 어려운 수준에 속하는 문제다. 그동안 배열을 이용하면서 bfs를 수행했는데, 이 문제는 배열의 인덱스끼리 서로 내용을 바꾸어야하는 점에서 풀이를 생각해내지 못했다. 상하좌우 모두 방문해야하는데, 그때마다 배열의 내용을 바꾸면 다음 방문에 영향을 끼치기 때문이다. 매 방문마다 바뀌는 배열을 모두 저장할 수도 없는 것이고.. 그러면 어떻게 해야할까 생각을 하다가 풀지 못하고 다른 사람의 풀이를 참고하게 됐다. 배열이 아닌 간단하게 string을 쓰는게 흥미로웠다. https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc...
bfs문제를 풀던 중 조금의 응용이 있는 문제다. 다른 사람의 풀이를 참고해서 풀었기 때문에 정리해보려한다. www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net #include using namespace std; int n,m, secureCnt=0, result=2500; int lab[50][50] = {0,}; int visited[50][50]; int dx[4] = {0,-1,0,1}, dy[4] = {1,0,-1,0}; bool virus_visited[10..
요즘은 백준으로 유형별 문제를 풀고 있다. 그 중에서도 bfs(너비 완전 탐색)문제들을 풀고 있다. 처음에는 조금 쉬운 문제 위주로 풀어서 금방 풀었지만, 조금씩 어려운 문제를 풀다보니 조금 더 응용을 요하는 것 같다. 풀이 방법을 고민하다가 다른 사람의 풀이를 참고했다. 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이..