두부의 코딩일기

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() 메서드 정의 및 사용 방법 알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 이번 문제는 예제가 7개나 있는 고마운 문제이다. 매번 알고리즘 문제를 풀면서 반례를 찾는게 여간 쉬운 일이 아닌데 정말 고맙다. 8x8 이상의 크기를 입력하고 상하좌우 한 칸씩 색깔이 다른 8x8 크기의 체스판을 만드는데 색칠이 잘 못된 최소 개수를 구하는 문제이다. 만약 10x10 크기의 배열이 입력됐다고 하면 자를 수 있는 경우의 수는 얼마나 될까? 10x10 크기가 주어지면 경..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 이번 문제는 다이나믹 프로그래밍(dp) 문제이다. 다이나믹 프로그래밍에는 Bottom-up 방식과 Top-down 방식이 있는데 이 문제에서는 둘 다 사용이 가능하다. 필자는 Bottom-up 방식이 먼저 떠올라서 반복문으로 풀었다. 우선 이 문제에는 "큰 수로 나누는 게 무조건 좋다"의 함정이 있다. 예제 2번을 보면 쉽게 이해할 수 있다. 큰 수(2)로 먼저 나누는 방법은 10 → 5 → 4 → 2 → 1로 4번의 연산을 거치지만, 1을 먼저 빼고 3으로 나누게 되면 10 → 9 → 3 → 1로 3번의..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 이전에 풀었던 유기농 배추와 동일한 문제인데 난이도가 아주 조금 올라갔다. 아파트 단지 개수뿐만 아니라 단지 내에 몇 개의 집이 있는지를 구해야 하는 문제로 유기농 배추 문제에서 몇 가지 코드만 추가해주면 쉽게 풀 수 있다. 유기농 배추 문제와 달랐던 건 배열의 모양과 입력할 때이다. 예제를 살펴보면 '0110100'로 들어오는데 한 자리씩 잘라서 int형 배열에 넣어줘야 한다. map[i][..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 대표적인 dfs와 bfs 알고리즘 문제 중 하나이다. 필자는 재귀함수를 이용한 dfs가 제일 편하고 익숙해서 이걸로 해결했다. 1. N x M 크기의 int형 배열 2개를 만들어준다. 배추밭(map)과 방문 여부(check)를 기록할 배열이다. 2. 모든 배추밭을 다 돌면서 방문하지않은 곳의 인접한 배추를 찾으면 된다. if (x < map.length-1 && map[x+1][y] == 1 && che..