자료구조 기초 응용 문제이다. 나는 list로 문제를 풀었지만 stack 두개를 가지고도 문제를 풀 수 있다는 걸 다른사람의 풀이를 보고 깨달았다. 커서를 기준으로 왼쪽과 오른쪽을 스택에 넣어 푼다는 점이 흥미로웠다. 간단하지만 은근히 자료구조를 잘 활용해야 풀 수 있다는 점에서 좋은 문제라고 생각했다. https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net #include using namespace std; int mai..

요즘 백준에서 그래프 유형 문제를 많이 풀다보니 그래프 문제를 푸는 실력이 많이 좋아진 것 같다. 카카오 문제를 풀면 괜히 기분이 좋다 ㅎㅎ 문제를 보고 플로이드 와샬 문제라는 것을 깨닫고 풀었는데, 다익스트라로도 좋은 풀이가 있는 것을 보고 정리해보려한다. https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, ..
그래프 문제로 어려운 난이도는 아니지만 좋은 문제 같아서 정리해보려한다. 풀이를 생각하는 과정이 마음에 들었다. https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 마을 안의 도시끼리 한 길로만 연결되고 나머지 길은 없앨 수 있다는 점에서 최소 스패닝 트리를 생각했다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 유지비를 최소로 하기 위해서 정렬 후 유지비가 작은 길부터 크루스칼 알고리즘을 사용하면 된다. 그런데..
예전에 풀어본적이 있던 유형의 문제 같은데 풀이가 잘 생각나지 않았다. 다른 사람의 풀이를 보고 대충 힌트를 얻어 구현했다. 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..

리눅스에서 네트워크 소켓 프로그래밍을 이용해 파일을 다운로드하고 업로드할 수 있는 클라이언트와 서버를 만들어보았다. - 파일 전송 서버는 서버에서 실행중이며 클라이언트가 다운받고자 하는 파일을 전송하는 역할을 한다. - 파일 전송 클라이언트는 서버에 전송할 파일을 선택하여 전송(업로드)한다. - 클라이언트는 접속한 디렉토리에 대해서 파일을 업로드, 다운로드 하도록 한다. - 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...