알고리즘/백준 (41) 썸네일형 리스트형 13549번 - 숨바꼭질 3 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 13549번 - 숨바꼭질 3을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/13549 [문제 접근]저는 이 문제를 풀지 못했습니다. 정확히는 방향성을 잡지 못했습니다. 항상 유형별 문제만 풀다가, 유형을 모르는 문제를 풀려고 하니까 방향성을 잡기가 어렵네요.처음에는 그리디로도 생각했다가,, DP도 생각했는데, 정당성 그리고 점화식을 세울 수가 없더라구여.1시간을 고민 끝에 결국 문제 관련 자료를 찾아보았고, 그래프와 관련된 문제라는 것을 알 수 있었습니다.그래서 저는 BFS로 접근했고 풀어냈습니다!.근데 이 문제를 BFS로 풀어서 맞춘 것은 순전히 우연이었습니다. 이 문제는 우리가 알고 있는 BFS를 단순히 사용해.. [백준/C++] 알고리즘 2011번 - 암호 코드 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 2011번 - 암호 코드를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2011 [문제 접근]읽어보면 이전상황을 이용해 현재 상황을 구한다는 느낌이 옵니다.즉 패턴을 발견할 수 있습니다. 동일한 구조의 작은 문제들의 해법을 이용해 동일한 구조의 큰 문제의 해법을 구할 수 있습니다.즉 다이나믹 프로그래밍 냄새를 술술 풍깁니다. [풀이 전략]다이나믹 프로그래밍의 첫번째 단계는 점화식 정의입니다.저는 dp[i]를 i번째까지 해석가짓수로 정의하였습니다.왜냐구여? 일단 가장 문안하게 정의내렸습니다.이렇게 했는데 점화식이 안구해지면 그에 맞춰서 dp[i] 정의를 다르게 하거나 dp[i][j] 정의로 변경하면 됩니다. i번째 .. [백준/C++] 알고리즘 9655번 - 돌 게임 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 9655번 - 돌 게임 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/9655 [문제 접근]여러가지 접근 방법이 있지만, 다이나믹 프로그래밍을 연습하는 목적으로, 다이나믹 프로그래밍 방법을 시도하였습니다.이 문제가 다이나믹 프로그래밍 냄새를 풍기는 부분이 있습니다. 바로 현재 상황 n을, n-1 이전 상황 혹은 n-3 이전 상황을 이용하여 구할 수 있기 때문입니다. 그래서 구체적으로 다음 스텝은 뭐냐구여?.점화식 정의를 해야합니다.저는 처음에 풀이를 했을 때 점화식 정의를 잘못하여 풀었는데 풀리는 이상한 상황이 발생하였습니다. 저는 dp[i]를 "i번째 돌이 남았을 때 이기는 사람"이라고 정의를 했습니다.n-1이전상.. [백준/C++] 알고리즘 10942번 - 팰린드롬? 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 10942번을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/10942 [문제 접근]시간 제한은 0.5초M의 크기는 1백만, N의 크기는 2천입니다.여기서 완전탐색으로 질문 1번에 수열을 모두 탐색을 하면 n번 연산이 필요하기 때문에 총 연산량은 M x N 으로 20억연산이 됩니다.c++에서 1초에 대략 1억번 연산을 한다고 했을 때, 20초로 시간 초과가 납니다.즉 이 문제는 O(N)의 시간복잡도를 가진 알고리즘으로 접근해야 하고, 다이나믹 프로그래밍이 적합하다는 것을 유추할 수 있습니다. O(NlogN)시간복잡도를 가진 알고리즘을 생각할 수 있지만, 팰린드롬의 반복성을 생각했을 때 다이나믹프로그래밍+ O(N)이 더.. [백준/C++] 알고리즘 2660번 - 회장뽑기 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2660 [문제 접근]처음에 문제를 읽고 머릿속에 명확히 문제 상황이 그려지지 않았습니다.그래서 예제를 토대로 그림을 그려가며 이해를 시도했습니다. 사람을 정점으로, 친구관계를 간선으로 치환하여 생각했고,조건에서 몇 사람을 통하면 모두가 서로 알 수 있다고 했기 때문에 BFS를 이용해서 거리가 가장 먼 정점을 점수로 두었습니다.인접리스트를 활용하여 BFS를 둘 경우에는 O(V+E)의 시간복잡도가 걸립니다.제한시간은 1초이지만, 회원의 수가 50명이하여서, O(V+E) * 50 충분히 제한시간 안에 들어갈 수 있다고 판단하였습니다. [풀이 전략]1. 무방향 그래프임.. [백준/C++] 알고리즘 1715번 - 카드 정렬하기 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1715번 - 카드 정렬하기 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1715 [문제 접근]- 최소한의 비교를 하기 위해서는 매번 최소의 선택을 해야 합니다. 여기서 그리디 문제일 수도 있다는 것을 느꼈습니다.- 시간제한이 2초이고 N이 10만이하이기 때문에, O(N^2)풀이는 불가능 합니다. 최소를 구하는 문제여서 자료구조 중 이진검색트리, 우선순위 큐가 떠올랐습니다.- 리스트에서 가장 작은 두 데이터를 선택하고 다시 이 두 데이터의 합을 리스트에 넣고 다시 가장 작은 두 데이터를 선택하고의 반복.. [풀이 전략]- 매순간 리스트에서 최솟값을 가져오기 유리한 자료구조인 우선순위 큐를 이용하여 구현하였습니.. [백준/C++] 알고리즘 1806번 - 부분 합 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1806번 - 부분 합 을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1806 [문제 접근]- 제한 시간이 0.5초이고 n이 10만이하이기 때문에 O(N^2)풀이는 불가능합니다.- 1차원 배열에서 O(N^2)이 아닌 풀이를 원하기 때문에 이분탐색 혹은 투포인터가 떠올랐습니다. [풀이 전략]- 투포인터를 이용하여 풀이하였습니다. [코드]#include #include #include using namespace std;int n , s ;int arr[100'001] ; int main() { ios::sync_with_stdio(0); cin.tie(0); int res = 1'000'000'.. [백준/C++] 알고리즘 1620번 - 나는야 포켓몬 마스터 이다솜 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 1620번 - 나는야 포켓몬 마스터 이다솜 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1620 [문제 접근]- 이름에 대응되는 숫자를, 숫자에 대응되는 이름을 출력하는 문제입니다.- n과 m이 10만이하이고, 시간제한이 2초이기 때문에 시간복잡도 O(N)이나 O(NlogN)이 통과할 거 같습니다. [풀이 전략]- 해시맵 두 개를 이용하여 풀었습니다.- 문자열이 숫자인지 아닌지 판별하는 함수를 작성했습니다. [코드]#include #include #include #include using namespace std;bool isNumber(string str) { for(auto c: str) { .. [백준/C++] 알고리즘 7785번 - 회사에 있는 사람 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 7785번 회사에 있는 사람 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/7785[문제 접근]- 각 사람마다 최종적인 값이 enter인지 파악이 관건이라고 생각했습니다. 또한 enter의 개수가 leave개수보다 많아도 동일하다고 생각했습니다. - 시간 제한은 1초이고, n이 백만입니다. 1억번 연산하는데 c++은 대략 1초가 걸리니 시간복잡도가 N^2 풀이는 이 문제를 통과할 수 없습니다. 해시, 이진 검색 트리, 이분 탐색, 투포인터가 떠올랐습니다. [풀이 전략]- unordered_map과 map 중 고민하다가 최종 출력이 이름 역순이어서 이미 순서가 정해진 ordered_map이 더 간단하다고 판단이 .. [백준/C++] 알고리즘 22862번 - 가장 긴 짝수 연속한 부분 수열 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 22862번 - 가장 긴 짝수 연속한 부분 수열을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/22862 [문제 접근]시간 제한이 1초이고 n이 100만이하이기 때문에 O(N) 혹은 O(NlogN) 시간복잡도로 풀어야하는 문제입니다.연속한 부분 수열을 다루고 있기 때문에 투 포인터로 접근했습니다.여기서 유의할 점은 입력이6 22 1 4 4 4 일 때 출력이 3이 나와야하는 점입니다. [풀이 전략]1. 시작과 끝을 나타내는 변수 st,en을 생성 및 초기화합니다.2. 삭제 횟수를 세는 cnt를 생성 및 초기화합니다.3. en 4. en -st - cnt로 조건을 만족하는 부분 수열의 길이를 찾은 후 기존에 저장된 .. 이전 1 2 3 4 5 다음
