재원블로그 재원블로그

이 문제는 스택, 문자열을 이용한 그리디로 풀었다. 처음에는 이 문제에 kmp 알고리즘을 적용해봤다. 일부 테스트 케이스는 맞췄으나, 나머지에서 시간 초과가 났다. 다른 방법을 찾을 수 없어 검색을 통해 그리디 알고리즘을 사용한다는 사실을 발견했다. 만약 "110" 을 제외한 나머지 부분에 0이 하나도 없다면, 앞에 "110" 들을 나란히 붙여주는 것이 가장 숫자가 작다. 0이 하나라도 있다면 마지막 0 뒤에 110을 채워 넣어야 그 뒤에 있는 1들이 뒤로 밀려나면서 숫자가 작아지게 된다. 이를 그대로 구현하면 시간 초과 없이 정답이 나온다. #include #include #include #include using namespace std; int findLastZero(string str) { int..

이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 처음에는 출발지들에 대해 루프를 돌면서 산봉우리들에 대해 루프를 돌고, 해당 출발지, 산봉우리 쌍에 대해 다익스트라 알고리즘을 사용했다. 그러나 이 방법으로는 당연히 시간 초과가 난다. 다른 방법으로 처음 다익스트라 알고리즘을 시작할 때, 우선순위 큐에 모든 출발지를 넣고 각 노드가 SUMMIT을 만나면 종료하도록 구현하는 것이다. 이 방법을 사용하면 한 번의 다익스트라 호출로 산봉우리들로 가는 최단 거리를 알 수 있다. #include #include #include #include #include using namespace std; struct compare { bool operator() (pair& left, pair& right) { retur..

이 문제는 원형 탐색, 순열을 이용한 완전 탐색을 이용해서 문제를 풀었다. 이 문제에서 핵심은 시계, 반시계 방향으로 두 가지 탐색을 하는 것이 아닌, 시계 방향 하나로만 탐색해도 전체 가짓수를 셀수 있다는 것이다. 또한 dist가 큰 사람부터 사용하는 것이 더 적게 지우는데 유리하다는 것이다. 이 두가지를 이용해서 문제를 풀었으나, 13번 테스트 케이스만 시간 초과가 났다. 검색을 통해 순열을 이용해서 부분 배열에 대한 순서쌍을 모두 탐색하는 방식으로 문제를 푸는 것을 확인했다. 내가 이전에 풀었던 방식으로는 아마 중복된 경우를 같이 카운트해서 시간 초과가 났을 확률이 높다고 생각했다. Java에는 순열 표준 라이브러리가 없어서 아쉬웠다. 그래서 C++로 풀었다. #include #include #in..

이 문제는 dfs를 이용해서 풀었다. 이 문제에서 핵심은 visited를 설정할 때 3중 배열로 설정해야 한다는 것이다. 한번 방문한 노드도 재방문할 수 있는 dfs이기 때문에 양과 늑대의 수도 매개변수에 포함시키고, 이들을 합한 3개의 매개변수에 대한 visited로 방문 여부를 판단하는 것이 핵심이다. 이 문제에서 굉장히 애를 먹은 부분이 있는데, if - else if - else 부분에서 코드 오류를 겨우 찾아냈다. 처음에는 if와 else if 의 조건 하나에 모든 요구사항을 다 넣었다. 그런데 이렇게 되면 if와 else if에 맞지 않는 조건이 else로 가버린다. 원래의 흐름은 양이냐 늑대냐 빈 노드냐 이기 때문에 정답이 나오지 않게 된다. 몇 시간의 삽질 끝에 겨우 오류를 찾아내 문제를 ..

이 문제는 bfs를 이용해서 풀었다. 처음에는 재귀를 이용해서 풀었으나, 정답이 나오지 않았다. 로봇 구현까지는 문제 없었으나, 최솟값을 계산하는 과정에서 정답이 나오지 않았었다. 그래서 풀이를 참고했고, bfs를 이용해서 쉽게 풀 수 있었다. 요즘 자꾸 재귀로만 풀려고 하는 경향이 생겼는데, bfs를 잘 이용해야겠다. 결국 내가 아는 선에서 문제를 출제할 것이라는 생각을 가지고 문제에 임해야겠다. import java.util.*; class Solution { static final int RIGHT = 0; static final int UP = 1; static final int LEFT = 2; static final int DOWN = 3; static final int INF = 100000..

이 문제는 백트래킹을 이용해서 푸는 문제이다. 처음에는 이 문제를 풀 때 apeech 보다 1 많은 화살로 한번에 빼는 방식으로 풀었으나 오답이 나왔다. 그래서 검색을 통해 그냥 백트래킹을 이용하는 것이 구현도 직관적이고 풀이도 쉽다는 사실을 발견했다. 처음 풀었던 방식의 문제점은 화살이 남는 경우에 대해 로직이 모호하다는 것이다. 마지막까지 도달했을 때 남은 화살을 전부 0점에 꽂아넣는 방식으로 구현했으나 오답이었다. 그냥 백트래킹은 당연히 시간 초과가 나기 때문에, 여러 가지 장치를 해주면 시간 안에 풀 수 있다. 먼저 start 매개변수를 두어 순서가 뒤바뀐 똑같은 결과를 만들지 않도록 순서를 강제한다. 그 다음 apeech보다 1만 많으면 되므로, ryan이 이미 화살이 더 많은 경우에는 cont..

STORY 1. 서버의 개요 1. 클라이언트와 서버의 차이점 서버 머신은 하드웨어나 OS 부분에서 클라이언트와 다를 수 있다 그러나 LAN 어댑터, 프로토콜 스택, socket 라이브러리 등은 전혀 다르지 않음 하지만 사용법은 조금 다를 수 있음 2. 서버 애플리케이션의 구조 하나의 프로그램으로 여러 클라이언트와 소통하기는 어려움 그래서 서버 프로그램으로의 접속을 기다리는 부분, 클라이언트와 소통하는 부분 두 부분으로 나눔 클라이언트가 접속 요청 시 접속 기다리는 부분에서 소통하는 부분으로 소켓을 넘겨줌 클라이언트는 결과적으로 하나의 태스트/스레드와 1대1로 소통하게 됨 3. 서버측의 소켓과 포트 번호 데이터를 송수신하는 입장에서는 클라이언트, 서버 개념이 없을 수도 있지만, 접속 동작을 수행할 때는 좌..

STORY 1. 웹 서버의 설치 장소 1. 사내에 웹 서버를 설치하는 경우 가장 간단한 방법 사내 LAN에 서버 설치하고, 인터넷에서 직접 액세스 IP 주소가 부족하여 이 방법 안씀 또한 보안 문제 → 공격에 노출 그래서 방화벽을 둠 특정 서버에서 동작하는 특정 애플리케이션에 액세스하는 패킷만 통과, 나머지는 차단 그러나 만능은 아님 → 액세스를 허가한 애플리케이션에 보안 구멍이 있으면 공격받음 2. 데이터센터에 웹 서버를 설치하는 경우 데이터센터 시설에 서버를 가지고 들어가서 설치하거나 프로바이더가 소유하는 서버를 빌려쓰는 형태 고속 액세스 가능 안전성도 높음 STORY 2. 방화벽의 원리와 동작 1. 패킷 필터링형이 주류이다 지금은 거의 무조건 서버의 바로 앞에 방화벽이 있는 것이 보통 방화벽은 패킷..