메이쁘

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제는 백준 9933번 : 민균이의 비밀번호 처럼 문자열 처리 방식으로 양 끝에서부터 가운데까지 하나씩 숫자를 비교하며 구분하는 것인 줄 알았다가 시간이 다른 사람들보다 2배 이상 차이가 나서 급하게 다른 방법을 고민하며 찾던 중 동적 프로그래밍(DP) 방식을 통해 해결한다는 힌트를 얻었고, DP를 사용해서 시간을 절반 이상 줄이게 되었다!! DP를 사용하기 위해서는 규칙을 파악할 필요가 있다. 팰린드롬이란 앞뒤가 똑같은 전화번호 ..

https://www.acmicpc.net/problem/9933 9933번: 민균이의 비밀번호 문제 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다. 파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다. 예를 들어, 민균이의 비밀번호가 www.acmicpc.net 문자열 처리 문제이다. 풀이 방법은 간단한데, 2중 for문을 통해 String 단어 두 개씩 꺼내서 각각의 양 끝 문자부터 시작..

https://www.acmicpc.net/problem/2857 2857번: FBI 문제 5명의 요원 중 FBI 요원을 찾는 프로그램을 작성하시오. FBI요원은 요원의 첩보원명에 FBI가 들어있다. 입력 5개 줄에 요원의 첩보원명이 주어진다. 첩보원명은 알파벳 대문자, 숫자 0~9, 대시 (-)로만 이루어져 있으며, 최대 10글자이다. 출력 첫째 줄에 FBI 요원을 출력한다. 이때, 해당하는 요원이 몇 번째 입력인지를 공백으로 구분하여 출력해야 하며, 오름차순으로 출력해야 한다. 만약 FBI 요원이 없다면 "HE GOT AWAY!"를 www.acmicpc.net 엄청 쉬운 문제. String 함수 중 contains를 사용하면 끝이지만 연습 겸 자바 정규표현식을 이용했다. find를 사용하기 위해서는 ..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net BFS를 사용하는 문제이다. 차이점은 자기 자리에서 이동할 수 있는 경우의 수가 8가지 라는 점..? 하지만 다른 사람들보다 계산 ..

허프만 코드란? - 데이터를 효율적으로 압축하는 데 사용하는 알고리즘으로, 그리디 알고리즘에 속함. - 데이터 빈도 수에 따라 우선순위 큐에서 작은 두 개의 노드를 꺼내고 이를 합쳐 트리를 만드는 과정이 있다. - 고정 길이 코드와 가변 길이 코드 두 가지 표현 방법이 존재함. 허프만 코드 인코딩 과정(허프만 코드를 만드는 과정) ** 참고로 여기서 말하는 방식은 가변 길이 코드 표현 방법에 해당한다. - (a) ~ (f) 까지의 과정을 담은 그림으로, 이 그림을 보면 바로 이해할 수 있을 것이다.. - (a) : 예를 들어, 인코딩을 할 문자열이 casdffsdasadceacsd 라고 주어지면, 이 문자열에 각 알파벳 별로 얼마나 포함되어있는지(빈도 수) 나타낸 수 이다. 이 수들을 우선순위 큐에 담아..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 문자열 처리 분류 문제. 두 문자열 A와 B의 length를 구한 다음 0부터 B.length - A.length 까지 for문 진행. 이..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net 다익스트라 알고리즘 + BFS(너비우선탐색)을 섞은? 문제이다. 2차원 int 배열 map과 각 지점마다의 최단 거리..

Union / Find 알고리즘이란? -> 그래프 알고리즘 중 하나로 합집합을 찾는 방법. -> 상호 배타적 집합(Disjoint-Set)이라고도 함. -> 여러 노드(정점)가 주어질 때, 두 개의 노드(정점)를 선택해서 현재 두 노드(정점)가 서로 같은 그래프에 속하는지 판별하는 알고리즘. -> Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 -> Union : x와 y가 포함되어 있는 집합을 합치는 연산 -> 처음에는 모든 노드의 부모를 해당 인덱스(자기 자신)로 설정 샘플 코드 - Union 함수 // 두 노드를 합치는 함수 public static void union(int x, int y) { x = find(x); y = find(y); if(x != y) parent[y] = x; ..

크루스칼 알고리즘이란? -> 프림 알고리즘과 같이 MST(최소 스패닝 트리) 를 찾기 위한 알고리즘. -> 조금 Greedy한 방법. -> 간선을 중심으로 탐색하면서 노드를 확인용으로만 사용함. -> 핵심은 각 단계에서 사이클을 이루지 않은 간선을 선택하는 것! -> Union-Find 개념이 필요함! https://maivve.tistory.com/11 -> 시간복잡도 : O(ElogV) 지만, 프림보다 크루스칼이 빠르다. 매커니즘 1) 모든 간선들을 우선순위 큐에 넣고 weight를 오름차순해서 가장 작은 값부터 poll 한다. 2) poll 한 간선의 양 끝 점이 같은 부모인지 체크한다. 3) 같은 부모이면 다음 간선을 선택하고 3-1) 다른 부모이면 해당 간선을 최종 선택한다. -> 가중치 추가 ..

벨만-포드 알고리즘이란? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. 사이클 포함 X. -> 음의 가중치도 계산 가능. 다익스트라 알고리즘보다 시간복잡도 높음(더 느림). -> 간선들을 중심으로 찾음 -> 방문되지 않은 정점(값이 무한대인 정점)에서 출발하는 간선들은 고려하지 않는다. -> 즉, 다익스트라의 변형을 통해 음수간선에 대한 처리 및 음수 사이클을 체크하기 위한 알고리즘. -> 여기서 모든 사이클을 한 번 다 돌아도 distance의 변화가 하나도 없으면 그냥 해당 for문을 종료시켜도 됨. ** 최악의 경우 시간복잡도 O(n^3), 보통 O(VE) 샘플코드 public static boolean bellman(int n, int m, int sta..