Algorithm/문제 풀이

[KAKAO_BLIND_RECRUITMENT_2020] 문자열 압축

문제 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 출제 의도 tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/ 문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악 문자열 자르기 부분 문자열 얻기 문자열 비교하기 문자열 길이 얻기 풀이 문자열의 길이가 L 이라고 한다면, 압축의 기준이 되는 문자열의 길이는 최대 L..

2020. 12. 30. 05:55

Algorithm/문제 풀이

[BAEKJOON_9935 - JAVA] 문자열 폭발

문제 www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 예전에 풀었던 커서이동 문제와 유사.(Stack을 사용) 폭발 문자열의 앞에서부터 검사하기보다는 폭발 문자열의 뒤에서부터 검사. (첫글자부터 마지막글자까지 검사하는것보다 뒤에서부터 검사하는것이 횟수가 적을것이라 판단) 코드 작성은 20분 내외로 완료했지만, 2%에서 fail이 지속발생. → 검사 과정에서 Stack이 비어있는 경우가 발생. ※ 검사 조건문에 검사 대상의 길이를 체크하여 ..

2020. 12. 29. 07:58

Algorithm/문제 풀이

[BAEKJOON_1916 - JAVA] 최소비용 구하기

문제 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 dist값 초기화가 중요. 인접리스트를 구현, 최소거리를 지속적으로 탐색 구현하다보니 프림과 비슷한 구조를 가졌다. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다. (최소스패닝트리가 최단경로트리를, ..

2020. 12. 28. 11:40

Algorithm/문제 풀이

[BAEKJOON_10026 - JAVA] 적록색약_V2

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 풀이 기존에 풀었지만 알고리즘 스터디 문제에 있어서 재풀이. 기존에는 map을 적록색약 전용으로 복사를 해서 풀었지만, 이번에는 하나의 메소드에 적록색약 여부를 전달. map의 크기가 N= N || col = N) { return false; } return true; } } // 좌표를 담을 class class Pos { int row; int col; pub..

2020. 12. 27. 11:48

Algorithm/문제 풀이

[BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)

문제 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리 기본 문제, 개념을 다시 상기 시키고자 풀이. ( 꾸준히 해야 까먹지 않는다.) Prim과 Kruscal 모두 시도. 간적크 간많프 → 간선이 적으면 크루스칼 알고리즘 / 간선이 많으면 프림 알고리즘 ex) 항상 위와 같지는 않다. 하지만 대부분 간선의 갯수에 따라 알고리즘을 선택 MST를 한다면 프림과 크루스칼 두가지 방법으로 풀어보는..

2020. 12. 27. 10:20

Algorithm/문제 풀이

[BAEKJOON_3020 - JAVA] 개똥벌레

문제 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 BruteForce로 풀려다 시간 제한 1sec를 본뒤 고민. 이분탐색을 사용하는 것 까지는 알겠는데 적용방법을 블로그를 통해 참고. 누적합을 적용해야하는 것을 참고했다. 석순과 종유석을 분리하는 이분 탐색으로, 누적합을 통해 파괴하지 않는 장애물을 제외. 석순의 경우 바닥, 종유석의 경우 천장임을 주의하며 풀이. 과정 석순과 종유석이 순서대로 들어오므로, 입력을 각각 다른 배열에 높이를 기준으로 받는다..

2020. 12. 24. 08:00