컴쟁이의 알고리즘 썸네일형 리스트형 백준 알고리즘 - 2636 치즈 www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 백준 알고리즘 2636 치즈 문제입니다. 여러가지 방법을 생각해보았지만 결국 전부 탐색해보는 수밖에 없다는 결론에 이르렀을 때, 그 탐색 방법으로는 BFS가 떠올랐습니다. 이 문제만의 차별점이라면 BFS 탐색을 한번만 하고 끝나는 것이 아니라 한번 마치고 해당되는 치즈들 녹이고, 또 탐색하고 해당되는 치즈들을 녹이는 등과 같이 BFS 탐색을 여러번 반복한다는 것입니다. 아래는 제 코드입니다. import java.io.Buffer.. 더보기 백준 알고리즘 2206 - 벽 부수고 이동하기1 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 백준 알고리즘의 2206번 문제 '벽 부수고 이동하기1'입니다. 제가 여지껏 풀어왔던 행렬 길탐색 문제들은 전부 DFS와 가지치기로 풀리는 문제들이었습니다. 그런데 이 문제는 DFS와 가지치기로 코드를 작성해도 풀리지 않더라구요. 결론적으로 이번 문제를 풀면서 BFS가 DFS보다 빠르다는 확증을 얻었습니다. 평소에는 머리로는 알고 있었지만 전부 DFS로 풀어도 해결이 되었기에 깊게 고민.. 더보기 알고리즘 문제를 풀 때 생각해야하는 것들 요즘 들어 백준에서 알고리즘 문제들을 많이 풀고 있습니다. 그런데 머릿 속에서 생각하고 손으로 그려보며 로직을 나름 이해했다고 생각했는데 코드로 옮기다보면 꼬이는 경우가 다반수입니다. 만일 간단한 문제라면 생각하고 손으로 내려오는 대로 적어도 해결되겠지만 문제가 복잡하다면 코드를 작성하던 중에 이전 내용을 한번 놓치면 계속 같은 곳을 빙빙 돌게 되지요. 항상 문제라고 생각만 하였지만 막상 고쳐보려하니 답답하기만 했었는데요, 오늘 유투브에서 강의를 보다가 문득 고칠 수 있는 방법을 생각해냈습니다. 우선 평소 하던 것처럼 머리로든 손으로든 직접 문제를 해결해보며 로직을 이해합니다. 그리고 그 흐름을 머릿 속으로 한번 그려봅니다. 그리고 코드를 작성하기 이전에 주석을 이용해서 그 흐름을 코드창에 옮겨 적습니다. 더보기 백준 1759번 - 암호 만들기 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 굉장히 오랜만에 포스팅하네요. 그동안 문제를 안 푼건 아니지만 이것저것 할일이 있다보니 포스팅이 뜸해졌습니다. 물론 다 변명입니다만 :) 이번 문제는 언뜻 보면 문자열 문제같아 보이지만... 그냥 조합 문제입니다. 다만 그냥 조합은 아니고 조건이 붙은 조합입니다. 문제를 읽어보자면 주어진 문자들을 사용해 정해진 길이로 만들 수 있는 가능한 모든 암호의 경우의 수를 구하는데, 여기서 오름차순으로 이미 순서가 정해져 있.. 더보기 백준 알고리즘 - 2477 참외밭 www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나 www.acmicpc.net 백준 알고리즘의 2477번 문제, 참외밭입니다. 난이도는 실버5정도 되는데 문제를 이해하는 것은 별로 어렵지 않지만 실제로 구현하는데 더 나은 방법이 없는지 생각하다가 오래 걸렸습니다. 어떤 참외밭이 있는데, 1m^2마다 수확되는 참외의 양이 정해져 있어 밭의 크기만 알면 해당 밭에서 참외가 얼마나 수확 가능한지 알 수 있습니다. 그런데 특이하게 모든 밭은 'ㄱ'이나 'ㄴ' 등과 같이 어디 한군데가 찌르러진 육각.. 더보기 백준 알고리즘 - 17470 배열 돌리기 5 www.acmicpc.net/problem/17470 17470번: 배열 돌리기 5 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 하... 문제의 '배열 돌리기 5'입니다. 정답 비율 16.667%에 달하는 무시무시한 문제입니다. 게다가 제가 사용하는 Java8 기준으로는 정답자가 단 3명밖에 없습니다. 결론적으로 말씀드리자면 못풀었습니다. 원인은 찾았는데 해결 방법을 못찾겠어요. 우선 기본적인 문제 자체는 '배열 돌리기 3'과 같습니다. www.acmicpc.n.. 더보기 백준 알고리즘 - 15686 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이번 문제는 백준 알고리즘의 15686번 문제인 '치킨 배달' 문제입니다. N x N 크기인 마을이 있는데 여기에는 1로 표시되는 가정집과 2로 표시되는 치킨집이 존재합니다. 그런데 이 마을에서는 치킨을 너무나도 좋아하는 나머지 각자의 집에서 제일 최단거리인 치킨집까지의 거리를 '치킨 거리'라고 일컫는답니다. 그런데 이 마을에 있는 모든 치킨집은 같은 프렌차이즈여서 효율을 극대화하기 위해 .. 더보기 백준 알고리즘 - 9742 순열 www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 혹시 NextPermutation이라고 아시나요? 저도 최근에서야 배운 일종의 순열을 만드는 방법 중 하나입니다. 이 방법은 우선 입력될 Array가 오름차순으로 sort 되어있어야만 유의미한 알고리즘입니다. public static boolean nextPermutation(char[] arr, int N) { int i = N - 1; while(i > 0 && arr[i-1] >= arr[i]) --i; if(.. 더보기 이전 1 2 3 다음
