알고리즘 (11) 썸네일형 리스트형 백준 1972 놀라운 문자열 - substr로 해결못하는 문자열 처리 문제 문제 링크 https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 문제 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 �� www.acmicpc.net 종강 기념으로 다시 알고리즘 시작한다! 길고 긴 학기였다... 해결 아이디어 문자열 처리 문제이다. 각 case에 대해 1부터 len-1 까지, 처음부터 끝까지 검사하고 , set를 이용해 하나도 겹치지 않고 나오는지 개수를 파악해서 검사했다. 총 n^3의 시간복잡도가 사용되겠지만 case수가 100개가 최대이므로 시간내에 돌아간다. 코드 #include using namespace.. 백준 14226 이모티콘 - 2차원 배열로 상태저장 bfs - c++ 링크 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 아이디어 오랜만에 bfs관련 풀어본 문제. 이문제는 주의해야 할점이, 클립보드에 복사한 이모티콘 갯수는 몇번이고 재사용이 가능하.. 백준 1261 알고스팟: bfs와 caching 쓰는 문제 c++ https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 사실 이 문제는 분류가 다익스트라 알고리즘으로 분류되어있었는데, 그 알고리즘에 대해서 몰라도 풀수 있다. 전형적인 bfs문제는 아니고 다이나믹 프로그래밍의 캐시 개념만 조금 쓰면 풀 수 있다. 어떻게 보면 최단 경로 문제이기 때문에 (빙빙 돌아가면서 벽을 부숴가면서 미로를 탐색하진 않을것 아닌가?) bfs를 쓰는 것은 당연한 .. PS 알고리즘 공부 한달차(1~30일) - 느낀점, 생각 정리 한달차 - 푼 문항 124문항 -solved.ac - 목표했던 골드는 찍었지만, 아직 부족한 점을 너무나도 많이 느낀다. - 현재는 완전 탐색(브루트포스)를 풀고 있는 중이다. plzrun 님의 블로그에 나와있는 코스를 한달째 밟고 있는데, 아직 완탐 부분이 조금 남아 있다. 아마 학교 조교와 오픽 준비를 안했더라면 저 부분들도 다 풀 수 있었을텐데, 4주는 넘기고 약 5주를 바라봐야 할 것 같다. - 개인적으로 제일 어렵다고 느끼는 파트들을 2개 꼽자면 dp 와 완전탐색이다. 일단 완전탐색은, 어떤 문제를 보면 이걸 bfs dfs로 풀어야 되겠다라던지, dp로도 풀 수 있겠다 라던지 등등의 감각은 조금씩 생기는것 같은데, 구현 능력이 조금씩 떨어 지는 것 같다. 오늘 풀다가 벽을 느낀 문제가 하나 있다.. 백준 1697 숨바꼭질 - bfs - c++ https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 한 7번;; 만에 풀었다. 큐에다가 bfs를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만 따져야 되는 조건들.. 백준 1107 리모컨 - 브루트포스 - c++ https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 우선 이 문제를 풀기 전 내 아이디어(브루트 포스 첫 문제다.) 고장난 리모컨 버튼들을 입력받아서, 0-9에서 뺀다. 그럼 잘 작동하는 리모컨 버튼만 입력을 받을 수 있을 것.(arr나 벡터에 저장하기.) 가장 큰 자리수부터 검사해서, 배열에 있는지 없는지 확인. 없으면 차이의 절댓값이 제일 작은 녀석을 골라서 다 밑의 자리.. 백준 1992 - 쿼드트리 (분할정복) C++ https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net 언제 괄호를 출력해야 하는지 확실히 구분해야 한다. 분할정복이 이뤄지는 시점 시작과 끝에만 괄호를 집어 넣을 것. 그 부분 에만 괄호가 들어가야 하고, 그 이외의 시점에는 숫자만 출력하는 것을 확실히 해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 백준 1780 종이의 개수 - 분할정복 - C++ https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 전형적인 분할정복 알고리즘이다. n*n짜리 배열에서 같은 숫자가 나오면 패스고, 다른 숫자가 검출이 되면 n/3*n/3짜리 배열 9개.. 이전 1 2 다음
