본문 바로가기

전체207

[백준 1774번] 우주신과의 교감 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 굉장히 재밌게 번역된 문제입니다. 번역되었다고 말하는 이유는, 이 문제는 원래 영문으로 된 문제입니다 (출처가 미국 정보 올림피아드). 그럼에도 전혀 번역되었다고 생각하지 못할 법한 내용으로 재밌게 번역되어 문제를 풀기에도 즐거웠네요. 문제를 자세히 읽어보면, 다음과 같이 요약할 수 있습니다. 정해진 노드가 입력으로 주어진다. 이미 건설된 노드 간의 엣지.. 2020. 11. 27.
[백준 16236번] 아기 상어 이 문제는 삼성 SW 역량 테스트 기출문제 입니다. 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 이용한 탐색을 핵심으로 하는 문제입니다. BFS에 대한 이론적 배경은 여기를 참고하세요. BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다. 문제가 내용이 긴데, 요약하면 아래와 같습니다. 상어는 본인보다 작은 물고기만 잡아먹을 수 있다. 상어는 빈 공간 혹은 자기보다 .. 2020. 11. 23.
[백준 2014번] 소수의 곱 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 언뜻 봐서는 어려워 보이는 수 관련 문제입니다. 문제 분류는 수학, 자료 구조, 정수론, 우선순위 큐라고 하네요. 얼핏 생각하면 다소 어려운 문제이긴 합니다. 숫자에 곱셈을 하는 정해진 횟수가 존재하지 않다 보니, 2, 2*2, 2*2*2, 2*2*2*....*2 등도 존재할 수 있기 때문에, 곱을 얼마나 해야 할지 감이 오질 않았어요. 고민 끝에 제가 .. 2020. 11. 21.
[백준 9935번] 문자열 폭발 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열을 다루는 문제입니다. 처음에는 정말로 단순하게 접근했다가, 답은 잘 나오는데 시간 초과가 떠 버리는 바람에 (...) 결국 다시 생각해서 접근했습니다. 제가 직접적으로 스택을 사용하지는 않았지만, 문제 분류 중에 스택이 적혀 있습니다. 실제로 많은 분들이 스택을 이용해서 문제를 해결하셨더라구요. 제가 접근한 방법은 아래와 같습니다. 결과 문자열을 담기 위한 c.. 2020. 11. 21.
[백준 1958번] LCS 3 난이도: 골드 3 문제 링크: www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 앞에서 몇 번 다루었던 LCS 문제입니다. 차이점이라면 이번에는 문자열 3개를 비교한다는 점! 따라서 dynamic programming 기법을 이용하기 위한 array 역시 3차원을 사용합니다. 기본적인 LCS algorithm에 대한 설명은 이 글을 참고하시기 바랍니다. 주의할 점은 문제에서 LCS가 Longest Common Subsequence를 뜻한다고 명시하고 있습니다. 즉, 연속된 문자만을 인정한다는 의미입니다... 2020. 11. 15.
[백준 15483번] 최소 편집 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net LCS와 유사한, 다이나믹 프로그래밍을 이용하는 문제입니다. (LCS algorithm에 대한 설명은 여기로) 두 개의 string: subject, target가 있다고 합시다. subject = 'for', target = 'whileforif' 로 하겠습니다. subject에 적절한 연산을 통해, target과 같게 만들고자 합니다. 여기서 연산이란, 삽입, 삭제, 수정 3가지를 의미합니다. 접근 방법은 다음과 같습니다: 2-dimensio.. 2020. 11. 15.

티스토리툴바