본문 바로가기

분류 전체보기

 (60)
[Baekjoon]2206.벽 부수고 이동하기 2206.벽 부수고 이동하기 http://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 미로 탐색과 비슷한 문제지만 벽을 최대 1개까지 부술 수 있다는 점이 다르다. 조건에 따라 bfs를..
[Baekjoon]5427.불 5427.불 http://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 3055.탈출과 거의 같은 문제였다. 다른 점은 이 문제에서는 도착지점이 맵에 주어져있지 않고 맵 밖으로 빠져나가야 탐색이 끝난다는..
[Baekjoon]2146.다리만들기 2146.다리만들기 http://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서 www.acmicpc.net dfs와 bfs를 모두 사용하여 풀 수 있는 문제였다. 크게 두 부분으로 나누어서 풀었다. 섬을 구분짓는다.(dfs..
[Baekjoon]2589.보물섬 2589.보물섬 http://www.acmicpc.net/problem/2589 맵이 주어졌을때 두 지점의 최단거리 중 최댓값을 구하는 문제이다. 노드 간 최단 경로를 찾는 문제이므로 bfs를 사용했다. 맵을 순회하며 땅인 지점에서 bfs를 수행. dist배열에 거리 저장. dist배열에서 최댓값을 찾고, 1로 돌아가서 반복. dist배열은 2차원 배열로 bfs를 시작한 지점으로부터 해당 인덱스까지의 거리를 저장한다. 시작 지점에 따라 최단거리가 다르기 때문에 bfs가 끝나면 초기화해주고 다른 육지 지점으로 가서 다시 bfs를 수행한다. 육지가 위 그림처럼 생겼을때 처럼 1에서 bfs를 수행하면 가장 멀리 떨어진 지점까지 거리는 4이다. 하지만 와 같은 경우가 최댓값을 가진다. 이 점을 잘 생각하여 di..
[Baekjoon]2573.빙산 2573.빙산 http://www.acmicpc.net/problem/2573 dfs로 푸는 문제였는데 문제의 조건 하나를 생각하지 못해서 계속 시간초과가 났다. 문제를 꼼꼼히 읽고 이해하는 연습이 더 필요할 것 같다. 접근은 다음과 같다. 빙산을 녹인다. dfs로 빙산의 개수를 카운트한다. 카운트가 2이상이면 종료하고 아니면 1로 돌아가서 반복한다. 빙산을 녹이는 melting메소드를 짜면 나머지는 일반적인 탐색문제와 동일하다. 먼저 getAdjSea메소드로 각 칸이 인접한 0의 개수(바다와 인접한 면)를 세서 melt배열에 따로 저장한다. 그 다음 원래 배열 map에서 배열melt에 저장된 값을 빼주고 만약에 그 값이 0보다 작으면 0으로 저장한다. 이후에 map을 순회하며 빙산을 만나면 dfs를 실..
[Baekjoon]2468.안전 영역 2468.안전 영역 http://www.acmicpc.net/problem/2468 연구소, 단지번호 붙이기 등 탐색 문제와 비슷한 방법으로 풀 수 있는 문제였다. 강수량 1증가. 탐색으로 안전영역 카운트. 최댓값이면 갱신, 아니면 1로 돌아가서 반복. 탐색은 dfs를 이용했고 explore메소드는 맵을 순회하며 dfs를 할지 말지 결정하는 메소드이다. 단지 번호 붙이기에서도 같은 방법을 사용했다. 다른 문제풀이와 다른 점은 flood메소드에 있다. 먼저 모든 지역이 물에 잠길 때까지만 함수를 실행하기위해 주어진 맵의 최고점을 max에 저장해놓고 while문을 통해 강수량이 max보다 작을 동안에만 실행했다. 또한 강수량이 증가할때마다 탐색을 다시 진행하기위해 visited배열을 초기화했다. privat..
[AWS]EC2 인스턴스에 파일 전송하기(2/2) - FileZilla로 파일 전송 및 실행 EC2로 생성한 Ubuntu 서버에 파이썬으로 작성한 파일을 옮겨서 실행을 해보자. 보통 깃헙에 파일을 올려놓고 그걸 서버에서 받아 실행하는 경우가 많다는데 이번에는 내려받을 파일이 하나만 있어서 굳이 그렇게 할 필요가 없다고 강의에서 설명했다. 그래서 FilZilla를 이용해서 Ubuntu서버로 파일을 옮기는 방법을 사용했다. 먼저 FileZilla를 다운받고 실행한다. 그 다음 사이트 관리자를 실행한다. 좌상단에 있는 기기가 연결되어 있는 아이콘을 클릭하면 된다.(Mac용 기준) 새 사이트를 클릭하면 우측 화면이 활성화 된다. 프로토콜은 SSH로 접속할 것이므로 SFTP로 설정하고 호스트에는 EC2 인스턴스의 퍼블릭IP를 입력한다. 로그온 유형은 키파일, 사용자명은 ubuntu로 한다. (만든 인스턴..
[Linux]chmod에 대하여 AWS EC2에 ssh를 이용하여 접속할때 키파일에 대한 퍼미션 에러가 났었다. 키파일에 대한 권한 설정을 바꿔줌으로써 해결할 수 있었는데 그 의미는 다음과 같았다. chmod 뒤에 숫자 세개가 나오는데 차례대로 나/그룹/전체에 대한 권한을 의미한다. 권한은 세가지로 read(4), write(2), execute(1) 가 있는데 이 숫자들 합의 조합으로 권한을 나타낸다. 예를 들어 5면, 5 = 4 + 1 로 read, write 권한이 있음을 의미한다. 즉 chmod 400의 의미는 4/0/0 이므로 나에게만 읽기 권한이 있도록 하는것이다. 다른 예를 들면 600: 나에게만 읽기,쓰기 권한 744: 나는 읽기,쓰기,실행 권한 / 그룹,전체는 읽기 권한 이런 식으로 권한 설정을 한다.

티스토리툴바