두부의 코딩일기

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해당 문제는 (0, 0)에서 출발해서 (N, M)까지 최단 경로를 구하는 bfs 문제이다. 서로 인접한 칸만 이동할 수 있으며 1은 이동할 수 있는 칸, 0은 벽을 의미한다. 예제 1번을 보면서 문제를 이해해보겠다. 예제 1번의 최단 경로를 그려보면 위와 같다. 이러한 유형의 문제는 대부분 입력 값을 넣어줄 Map 배열과 방문 여부를 판단하는 visited 배열 두 가지가 필요하다. int[][] map = new int[N+1..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 최근에 풀어본 포도주 시식 문제(2156번)와 거의 똑같아서 점화식을 바로 찾을 수 있었다. 이 문제에서 제공하는 조건은 총 3가지이다. 1. 한 계단 혹은 두 계단을 오를 수 있다. 2. 연속된 3개의 계단은 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야한다. 쉽게 생각해서 i번째 칸에 대해서 두 칸 전(i-2) + 현재 칸(i) 와 세 칸 전(i-3) + 한 칸 전(i-1) + 현재 칸(i)를 비..

HTML에서 div 태그는 주로 웹사이트의 레이아웃 구조를 설계하고 화면을 분할할 때 쓰인다. 과거 웹사이트에서는 table 태그로 공간 분할을 많이 했지만 요즘엔 div 태그를 이용한다고 한다. 하지만 div 태그는 하나의 공간을 의미하는 태그로 정확히 어떤 역할을 하는지 알 수가 없다. 그로인해 HTML5에서 레이아웃 관련 새로운 태그들이 추가되었다. 추가된 태그는 다음과 같다. 태그 설명 header 웹사이트의 메타데이터를 담고 있고, 페이지의 타이틀을 보여주는 부분 nav 페이지 이동할 때 이용하는 부분 aside 본문 옆에 존재하면서 주로 광고나 카테고리 목록으로 이용하는 부분 section 본문을 여러 개 포함하고 있는 부분 article 본문의 주내용이 들어가는 부분 footer 웹사이트의 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 처음엔 dfs를 이용해서 접근했지만 시간을 구하는 게 어려워져서 bfs로 접근했다. 문제에서 제시된 수빈이가 이동하는 방법은 총 3가지이다. 1. n+1 2. n-1 3. 2n 위 방법으로 1초마다 한 번씩 이동할 수 있다. 예제를 통해서 문제를 차근차근 이해해보겠다. 1. 초기 상태 (0초) 2. 1초 수빈이가 이동할 수 있는 곳은 n+1 → 6 n-1 → 4 2..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이 처음 문제를 봤을 때 이해가 잘 안갔다.. 검색을 하고나서야 이해가 갔다. 하나씩 이해해보겠다. 문제에선 두 개의 터렛 x, y 좌표와 류재명과의 r1, r2가 제공된다. 그렇다면 x, y를 기준으로 r1, r2의 반지름을 가진 원을 그릴 수 있다. 두 개의 원이 그러졌다면 A 터렛의 원과 B 터렛의 원의 접점 개수를 구하면 된다. 두 개의 원을 그렸을 때 생기는 접점의 개수에 대한 경우의 수는 몇 개일까? 위 그림처럼 여러가지가 있겠지만 4가..

https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 dfs, bfs 문제처럼 보이지만 쉽게 풀 수 있는 문제이다. 문제의 조건은 아래와 같다. 1. 2칸 이상의 빈 칸이 있으면 누울 수 있다. 2. 반드시 벽이나 짐에 닿게 된다. 이중 for문을 돌리면서 가로, 세로에 연속 2칸이 비어있으면 cnt++을 해준 후에 break; 문으로 for문을 빠져나왔다. 하지만 이렇게 하니까 예외 상황이 하나 생겼다. 바로 한 줄에 2개의 자리가 ..

https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 풀이 엄청 쉬운 문제라서 풀이라고 할 것도 없다. 주어진 변수는 총 4개 한수의 위치를 알려주는 x, y 우측 상단 꼭짓점을 알려주는 w, h 직사각형의 경계선까지 도달하는 최소 거리는 왼쪽, 오른쪽, 위, 아래 총 4가지이다. x, y, w-x, y-h의 최솟값을 구하면 된다. 최소값을 구하는 방법은 Math.min 혹은 if-else문을 사용하면 된다. 필자는 Math.mi..

다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘으로 BFS와 DP를 활용하는게 특징임 다익스트라 알고리즘 작동 원리 1. 방문하지 않은 정점들 중 거리가 짧은 정점부터 방문한다. 2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 예시를 보면서 살펴보겠다. A에서 E로 가는데 최단 거리는? A → D → C → E : 1 + 2 + 6 = 9 A → C → E : 4 + 6 = 10 A → B → D → C → E : 5 + 2 + 2 + 6 = 15 1. 시작 노드를 'A' 로 설정하고 이웃한 노드 중 거리가 짧은 순으로 노드를 선택해서 가중치(1, 4, 5)를 각 각 노드에 입력한다. 2. 1번..

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 오랜만에 쉬운 문제 등장. 0-9번까지 숫자를 넣어주기 위한 cnt 배열을 생성해주고, 방 번호 N을 charAt으로 잘라서 배열에 입력해준다. charAt으로 잘라서 int형 배열에 입력하게 되면 아스키코드 값으로 변환되서 들어오기 때문에 숫자 1로 변경해주기 위해서 아스키코드 값이 48인 '0'을 빼주면서 배열에 입력해준다. int num = N.charAt(i) - '0'; 배열에 입력해줄 때 해당 숫자의 인덱스를 +1 시켜주면 된다. 또한 6과 9를 뒤집어서 사용할 수 있기 때문에 ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색을 이용해서 풀어야하는 문제이다. 잘 모르겠다면 아래의 포스팅을 먼저 보고 오는 걸 추천한다. https://sookr5416.tistory.com/146 자바 이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법 알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서..