목록알고리즘 (76)

아무코딩

[백준 11967] 불켜기(c++)

문제풀이 불이 켜진곳만 갈수 있고 불을 켜는 곳은 다른방이다. 그래서 갔던 곳도 다시 가보면 갈 수 있는 곳이 늘었을 수도 있다. 그래서 bfs를 반복해서 돌려야된다. 언제까지 돌려야되냐면 count가 증가하지 않을 때 까지 돌려야 된다. 불을 켜는 정보는 2차원으로 이루어진 vector로 구현된 adjacencyList 에 저장한다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70..
알고리즘/백준 2020. 5. 30. 01:19
[백준 2616] 소형기관차 (java)

문제풀이 dp를 이용해서 푸는 문제이다. 문제가 어려워서 다른 풀이를 참고하였다 이전 객차까지의 최댓값(dp[i][j-1])과 현재 객차를 포함했을 때의 최댓값(sum[j] - sum[j-maxLength]) + dp[i-1][j-maxLength]) 중 큰 값이 현재.i번째 기관차가 1~j객실중 끌 수 있는 승객의 최댓값이 된다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..
알고리즘/백준 2020. 5. 29. 10:40
[백준 1987] 알파벳

문제풀이 dfs를 사용하며 최대한 갈수 있는 칸수를 계속 비교하여 업데이트 해준다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Baekjoon1987 { static final int COUNT_OF_ALPHA..
알고리즘/백준 2020. 5. 29. 00:29
[백준 17471] 게리멘더링 (java,c++)

문제풀이 java 의 경우에는 비트마스크를 이용해서 풀어보았고, c++의 경우에는 dfs를 사용해서 풀었다. 7달 전에 작성한 방법과 다른방법으로 풀어보고자 비트마스크를 사용해보았다. 문제 풀이 방법은 구역을 다 나누어보고(완탐), 그렇게 나누었을 때 조건이 성립하는지(연결이 되는 상태인지)를 체크해준다. 조건이 만족할시에는 최솟값 업데이트를 해준다. 소스코드 java 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..
알고리즘/백준 2020. 5. 28. 23:28
[백준 2166] 다각형의 면적 (c++)

문제풀이 벡터의 외적을 활용한 문제이다. "다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. " 라는 말을 처음에 파악하지 못해 어려움을 겪었지만 이말인 즉슨 시계방향 혹은 시계반대방향으로 쭉 다각형을 이어 그리며 바로 인접한 점의 점이 주어진다는 것을 의미한다. 아마 문제 출제의도였던 CCW라는 알고리즘을 적용하기 좋게 인풋이 주어지도록 한것 같다. CCW는 그냥 내용을 살펴보니 외적을 이용한 사선공식과 같았다. 위의 식이 세점이 주어졌을때 삼각형의 넓이를 구하는 공식이다. 이를 이용하여 쭉 더하다보면 면적을 구할 수 있다. 이식은 각이 유의미 해서 점의 순서도 중요하다!! 유의해서 문제를 풀면 오목한 다각형의 상황이 나오더라도 예외처리가 된다. (음수의 넓이로 더해지기..
알고리즘/백준 2020. 5. 22. 13:32
[백준 1717] 집합의 표현 (c++)

문제풀이 union-find를 이용한 문제입니다. paraent를 자기자신으로 초기화 한뒤 계속 한쪽을 붙여주며 붙여주고나서는 parent를 가리키는 방식입니다. 간단한 방식이고 더 효율적으로 푸려면 자식이 많은 트리에 계속 붙여나가고 루트노드에 바로 직접 자식이 붙어있도록 최적화를 한다면 더 빨라 질것 같으나 해당문제에서는 그정도 까지는 필요없다고 판단하여 이렇게 풀었습니다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include using namespace std; int N,M;..
알고리즘/백준 2020. 5. 21. 20:23
[백준 1167] 트리의 지름 (c++)

문제풀이 매우 아이디어가 좋은 문제이다. 루트 노트로부터 가장 멀리있는 노드로부터 또다시 가장 먼노드를 찾으면 그 두 노드가 지름을 담당하는 두노드다 그 두노드의 사이의 길이가 트리의 지름의 길이이다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace std; typedef struct treeNode{ int edge,num; ..
알고리즘/백준 2020. 5. 20. 19:25
[백준 1484] 다이어트 (c++)

문제풀이 투포인터를 사용한 문제이다. 계산된 값이 크면 기억한 몸무게를 계산된 값이 작거나 같으면 현재 몸무게를 증가시키며 일치하는 값의 현재몸무게는 바로 출력해준다. 값이없을때 처리를 따로해주지않아 한번 틀렸었다... 주의하자.. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; int G; int curWeight=2; int memWeight=1; long long getG(){ return pow(curWeight,2) - pow(memWeight,2); } int main() { cin>>G; bool ch..
알고리즘/백준 2020. 5. 20. 17:25
Prev 1 2 3 4 5 ··· 10 Next