개발하는 고라니

1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net [DFS or BFS] 2차원 배열이 map으로 주어지는 문제에서는 늘 BFS로 풀었어서 이번엔 DFS로 풀어보았다. B와 W로 이루어진 지도를 char로 그대로 저장하지 않고 boolean으로 저장하였다. W 이면 true로, B이면 false로. 물론 char[][]로 저장하여도 상관없다. 이제 2차원 배열 모든 정점을 방문할 차례인데, B로 이루어진 덩어리와 W로 이루어진 덩어리의 개수를 Math.pow해서 반환하도록 했다. DFS..

17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net [DFS + 동적 프로그래밍] 동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고... 이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할..

1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net [문자열 + 해싱] 나는 주어진 단어들을 소인수 분해하듯 알파벳 별로 나누어 배열에 저장하였다. 해싱이라고 하기도 뭐하지만.. 입력으로 주어지는 단어는 알파벳 대소문자로만 이루어져있기 때문에 뜻밖의 변수는 없을 것이다. a의 아스키코드는 97이고, A의 아스키코드는 65이다. 따라서 단어를 받으면 맨 앞, 맨 뒤 글자를 제외한 중간 문자열을 char로 변환해 'a'를 빼주었다. 그러면 0~25가 나올 수도 있고, 음수가 나올 수도 있는데 음수가 ..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net [DFS] 문제의 주어진 입력을 토대로 N x N 크기의 단방향 인접 행렬을 만들었다. 그리고 마지막 줄에서 제거할 노드의 번호를 입력 받는데, 이 때 제거할 노드를 방문 했다고 처리한다. 이제 DFS를 수행할 차례인데, 만약 root 노드와 제거할 노드가 동일하다면 DFS를 수행해서는 안된다. 따라서 root노드와 제거할 노드가 다르다면 DFS를 수행한다. 이때 DFS는 다음과 같은 로직을 갖는다. static void DFS(int x){ visit[x..

17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [BFS] 백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다. 예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저..

일전에 WebSocket(웹소켓)과 SockJS를 사용해 Spring 프레임워크 환경에서 간단한 하나의 채팅방을 구현해본 적이 있다. [Spring MVC] Web Socket(웹 소켓)과 Chatting(채팅) 기존 공부 용도의 게시판(?)에 여러 기능을 추가하던 차, 관리자와 멤버 간 채팅 기능을 구현하고 싶었다. 채팅을 하려면 웹 소켓이 필요하다고 한다. 간단하게 구현하는 것은 어렵지 않으므로 dev-gorany.tistory.com 이때는 무작정 여러 블로그를 참고하면서 채팅이라는 기능을 구현하고 다뤄보는 것에 의의를 두었다. 이번에는 Spring Boot 환경에서 여러개의 채팅방을 구현하고, 채팅이 저장될 수 있게 하기까지를 우선 목표로 설정하고 좀 더 공부하며 진행해보고자 한다. WebSock..

XSS는 Spring Boot의 내용은 아니긴 하나, Web 카테고리를 따로 만들지 않아 어쩔수 없이 여기에 작성한다. XSS XSS는 Cross Site Scripting의 약자이다. 원래대로라면 CSS라고 불리는 것이 맞지만, CSS는 이미 Cascading Style Sheets가 사용하고 있기 때문에 XSS라고 불린다. 이는 웹 해킹 공격 기법 중 하나로 "사용자가 웹 페이지에 접속하는 것으로 올바르지 않은 스크립트가 실행되는 취약점 또는 공격 방법"이라고 설명할 수 있고, "게시판이나 웹 메일 등에 Javascript와 같은 스크립트를 입력해 개발자가 의도하지 않은 동작이 수행될 수 있게 하는 공격 기법"이다 라고 할 수 있겠다. 많이 알려진 웹 해킹 공격 기법 들은 대부분 서버를 노리지만, X..

코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [Floyd-Warshall] 플로이드 와샬 알고리즘을 수행해서, i번 사람이 j번 사람에게 직접/간접적으로 도달할 수 있는지 체크한 다음, i번 사람이 자기 자신을 제외한 모든 사람에게 도달할 수 있으면 순위를 확실히 알 수 있다. 문제에서 주어진 조건은 간선이 단방향이라는 것을 알려준다. 따라서 주어진 입력을 적절히 이용하여 직접적인 A와 B의 관계를 boolean[ ][ ]에 표현하고 플로이드 와샬을 수행하면, A가 C에게 도달 할 수 있는지 여부를 알 수 있다. 표를 보며 이해하면 더 쉽게 와닿을 수 있을 것이다. 주어진 입력으로 boolean[][] 배열을 지..