알고리즘(29)
-
[PS] 백준 2933 - 미네랄
* 문제 링크 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄�� www.acmicpc.net 문제 이해 1. 주어지는 입력은 동굴의 상태로써 기존에 많이 풀었던 문제와 달리 테트리스 같은 높이가 있는 문제이다. 2. "각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다 " 문제의 이 내용이 처음에 이해가 잘 안 갔었는데 결국에는 한 칸이 미네랄이고 칸이 붙어있으면은 클러스터라는 뜻이다. 3. 두 사람이 번갈아가며 막대기를..
2020.05.03 -
[알고리즘] 정렬(7) : 위상정렬 (Topological Sorting)
목차 1. 위상정렬의 개념 2. 위상정렬의 구현 3. 위상정렬 코드 개념 위상정렬은 방향이 있는 그래프에서 정점들 간의 선후 관계를 위배하지 않도록 정렬하는 방법입니다. 위상정렬에 대하여 설명하기 앞서 간단한 위상정렬의 예시에 대해 알아보겠습니다. 위상 정렬은 선수과목이 있는 대학교의 커리큘럼을 생각하면 이해하기 쉽습니다. 다음과 같은 커리큘럼이 존재할 때 임베디드 시스템이라는 과목을 수강하기 위해서는 어떠한 순서로 과목을 수강해야 할까요? 여러가지 방법이 있겠지만 한 예시로 다음과 같은 수강 방법을 들 수 있습니다. UNIX 시스템 → 어셈블리 언어 → 논리회로 설계 → 운영체제 → 컴퓨터 구조론 → 마이크로프로세서 → 임베디드 시스템 하지만 선수과목이 존재하기 때문에 다음과 같은 선후관계는 반드시 지..
2020.05.03 -
[PS] 백준 2467 - 용액
문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다. www.acmicpc.net 해설 문제를 빠르게 해결하기 위해서는 문제 설명이 터무니없이 길다거나 익숙하지 않은 단어가 있을 때 문제 해결에 도움을 줄 수 있는 핵심 키워드를 뽑아내는 것이 중요합니다. 이 문제의 경우 과학 - 산성..
2020.04.26 -
[PS] 백준 2638 - 치즈
* 문제링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다. www.acmicpc.net * 유사문제 BOJ 2573 - 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의..
2020.04.25 -
[알고리즘] DP - 이항계수 (Binomial coefficient)
목차 1. 이항계수의 정의 2. 이항계수 점화식 3. 파스칼의 삼각형 4. 이항계수 구현 정의 이항계수는 이항식을 이항정리로 전개했을 때 각 항의 계수를 나타냅니다. 이항식 $(x + y)^2$ 를 전개한 결과는 다음과 과 같습니다. $(x + y)^2 = x^2 + 2xy + y^2$ 이 때 위의 전개 식에서 각 항의 계수인 [1, 2, 1] 이 나타내는 것이 바로 이항계수 입니다. 이항계수는 조합을 통해 구할 수 있습니다. 이번 포스팅에서는 조합을 통해 이항계수를 구하는 점화식과 이 점화식을 통해서 재귀적으로 그리고 동적계획법으로 이항계수를 구하는 방법에 대하여 알아보도록 하겠습니다. 점화식 이항계수를 구하는 점화식에 대해 알아보도록 하겠습니다. $(x + y)^n$ 이라는 이항식이 주어졌을 때 이항..
2020.04.23 -
[SW 역량테스트 기출풀이] 백준 - 17143 낚시왕
문제 [BOJ 17143 : 낚시왕] 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 흔히 말하는 맞왜틀을 방지하기위해서 문제를 풀기전에 읽고 해설하는데 시간을 쏟는 연습을 하고 있습니다. 그럼에도 불구하고 원트라이에 풀지 못하였는데, 어디서 막혔었고..
2020.04.16