색다르게 이 한 문제에서 마주친 삽질을 기록하면 어떨까 싶어서 적어봅니다 TIL을 가장한 삽질로그! (무려 세시간 가량을 잡아먹은..)https://www.acmicpc.net/problem/2504대표적인 스택 유형 문제다.다만, 주어진 괄호가 올바른 괄호냐
문제 링크: https://www.acmicpc.net/problem/12851약 세시간 가량 매달린 거 같은데 푼 게 너무 기뻐서 기록해본다~!😂 처음 접근법은 아예 답이 다르게 나오고, 다른 풀이 참고해서 중간에 무한루프도 몇번 돌아보고, 결국엔 일일이
문제: https://www.acmicpc.net/problem/1890처음에는 BFS로 풀어보려다가 메모리 초과가 나서 찾아보니까 방문 표시가 필수라고..! 최악의 경우 BFS의 너비만큼 O(2^n)까지 갈 수 있다.그렇다고 방문표시하면 답이 틀려가지고(한번
https://www.acmicpc.net/problem/1700그리디 전략을 잘 세우는 것을 넘어, 개인적으로 고려할 게 많은 문제였다. 처음에는 그리디 전략은 멀티탭에 꽂혀있는 물건의 남은 횟수 중 제일 작은 것으로 풀었는데, 한참 헤매다보니 전략 자체가
https://www.acmicpc.net/problem/3190전형적인 시뮬레이션 문제로, 뱀의 위치 변화를 어떻게 표현할까 고민하다가 큐로 관리하기로 했다.큐의 앞 부분은 뱀의 머리의 위치, 뒷부분은 뱀의 꼬리의 위치라고 생각하고, 만약 이동한 곳에 사과가
문제 https://www.acmicpc.net/problem/18405 접근방식 처음에는 번호별로 따로 큐를 관리하는 식으로 구현했는데 하다보니 하나의 번호가 여러군데 등장하는 경우 등, 복잡하고 고려해질 게 많아서 큐에다가 레벨 정보를 함께 넣는 식으로 해결하
은근히 고려할 게 많아서 까다로웠던 문제였지만 재밌었다👀✨https://www.acmicpc.net/problem/16234dfs 재귀호출로 합을 누적시키기 위해 total을 전역 변수로 두고, 인구이동이 일어나는지 확인 용으로 flag 변수 역시 전역 변수
https://www.acmicpc.net/problem/1766선행되는 노드를 먼저 방문해야 하고, 문제 번호가 커지는 순으로 풀어야 한다. 예시 입력으로가 주어진 경우,3 -> 1 -> 5 -> 4 -> 2 순으로 풀면 조건1은 만족하겠지만, 2를 만족하지
https://www.acmicpc.net/problem/21609무지개 색을 처리하는 방식이 까다로웠던 문제.. 이것 때문에 한참 헤맸다.처음에는 블록 그룹을 색출하는 과정이다. 블록 그룹이 없는 경우, 그대로 프로그램이 종료된다.조건에 부합하는 블록 그룹을
https://www.acmicpc.net/problem/13305최대한 작은 비용으로 갈 수 있는 만큼 가는 게 이득이다. min heap을 활용해서 (비용, 인덱스)를 담아서 그리디 하게 처리했다.비용 작은 것부터 하나씩 pop 하면서 last_index를
https://www.acmicpc.net/problem/16929DFS로 사이클이 존재하는지 판별하는 문제다.처음에는 초기 위치를 넣어서 DFS 탐색을 시작했다가, 해당 위치와 꼭 만난다는 보장이 없다는 사실을 깨닫고 (..)방문한 목록에 있는지 확인하는 방
https://www.acmicpc.net/problem/17140문제에서 하라는대로 따라가면 되는 전형적인 시뮬레이션(구현) 문제다.단순하게 표현하면:이런 알고리즘인데, 어떻게 접근할지는 다들 어렵지 않게 생각할 거 같은데, 구현하면서 중간중간 막히는 게 있
https://www.acmicpc.net/problem/2660가장 먼 연결 관계가 그 사람의 점수가 된다는 걸 알 수 있다."몇 사람을 통하면 모두가 서로 알 수 있다"는 조건이 있기 때문에, 아예 연결이 안되는 경우는 없으므로, 그 비용이 무한으로 나올
https://www.acmicpc.net/problem/10942쿼리 개수 m이 최대 1,000,000기 때문에 그때그때 팰린드롬인지 확인하는 Brute force 방식으로는 해결할 수 없다.모든 부분 문자열에 대해 캐싱을 해두고 팰린드롬인지 확인하는 게 시
https://www.acmicpc.net/problem/1495범위에 해당하면 큐에 집어넣어서 다음 레벨에서 연산할 수 있도록 한다.이때, visited 처리를 해야 메모리 초과없이(최악의 경우 2의 50제곱) 동작할 수 있다.첫번째 방식으로 풀고 알고리즘
맞왜틀 기록하기 ~https://www.acmicpc.net/problem/17609투포인터 방식으로 풀 수 있다.처음부터 회문 통과면 0,그게 아니라면 하나씩 좁혀가며 왼쪽 끝을 제거한 결과와, 오른쪽 끝을 제거한 결과끼리 비교할 수 있다.둘 다 안 되는
https://www.acmicpc.net/problem/14267처음에는 매 칭찬마다 dfs를 수행했는데 시간 초과가 났다. 최악의 경우, 트리 깊이는 n인데 칭찬 역시 m개 라면 100000 \* 100000번의 dfs 재귀 호출이라 그런가보다.다른 분들의
https://www.acmicpc.net/problem/20055독해가 더 어려웠던 문제..🤐컨테이어 벨트와 로봇을 큐로 관리하고 요구하는 그대로 시뮬레이션 하면 되는 문제다.큐.rotate(횟수)는 처음 알아간다 !
문제 https://www.acmicpc.net/problem/5549 접근 방식 👉 2차원 누적합으로 접근할 수 있다 > 2차원 누적합은 어떻게 다르지 ? 1차원 누적합: prefix_sum[n]은 1번째부터 n번째 까지의 누적합을 말한다. 아래와 같이
https://www.acmicpc.net/problem/14500가능한 모든 모양을 미리 저장해둔 뒤, 일일이 대입해보며 가장 큰 합을 구하는 방식이다.풀다가 현타 온다는 특징이 있다.처음에는 어떻게 dfs로 푼다는건지 감이 안 잡혔는데, 그려보면 'ㅗ' 모
https://www.acmicpc.net/problem/1194➿ BFS & 비트마스킹 활용사실 비트마스킹 말만 들어봤지, 사용해본 적은 없었는데이 문제는 도무지 각이 안 잡혀서 다른 풀이들을 참고하다가.. 비트마스킹 아니면 안되겠다 싶었다.❔ 내가 이해한
https://www.acmicpc.net/problem/1976최단거리를 구하는 문제는 아니지만 모든 노드에서 다른 모든 노드까지의 연결 여부를 알기 위해 플로이드 워셜을 사용하기로 했다.여행 계획이 주어졌을 때 단순히 a - b가 직접적으로든 간접적으로든
https://www.acmicpc.net/problem/11060✅ DP 재밌군 .. 점점 정들어가는 중 ,,
https://www.acmicpc.net/problem/2470정렬의 특성을 활용해 좀 특이하게(?) 풀었다.플러스 마이너스와 상관없이 정렬하면 양옆의 두 가지가 무조건 0에 가까운 용액이라는 점이 보장이 되기 때문에 이 점을 활용했다.
https://www.acmicpc.net/problem/1937DP를 활용한 DFS 방식으로 풀 수 있다.처음에 완전탐색, 순수 DFS로 접근한다고 간주하면, 최악의 경우 500 \* 500번 탐색을 수행하므로 아마 시간초과 걸릴 것이다. 여기서 한번이라도
https://www.acmicpc.net/problem/20922투포인터로 l, r을 늘려가며 딕셔너리로 값을 tracking 하는 방식이다.처음에는 l을 늘릴 때마다 validation 검사를 했는데(=k개를 초과하는지) 당연히 시간초과 걸렸다. 생각해보니
https://www.acmicpc.net/problem/1238✨reverse dijkstra✨는 처음이라 기록하는 TIL이 아닌 YIL (Yesterday-I-Learned 🙄)여기서는 각각의 위치에서 목적지 X까지 갔다가 + 오는 최단 거리가 가장 긴
https://www.acmicpc.net/problem/4179BFS를 활용한 시뮬 문제처음엔 하나의 큐에 지훈이 위치 먼저 넣고, 불들의 위치를 같이 넣고 시작했는데, 이렇게 하니 50%쯤 틀렸다.반례 :이런 케이스에서 지훈이가 탈출할 수 있기 때문!불이
https://www.acmicpc.net/problem/14425처음 n개의 문자열을 trie에 적재한 뒤, 주어진 m개의 target 문자열들에 대해 일치하는 문자열들의 개수를 구했다.이때, 일치하는 문자열을 구하기 위해 target의 문자 하나씩 타고 끝
https://www.acmicpc.net/problem/14425처음 n개의 문자열을 trie에 적재한 뒤, 주어진 m개의 target 문자열들에 대해 일치하는 문자열들의 개수를 구했다.이때, 일치하는 문자열을 구하기 위해 target의 문자 하나씩 타고 끝
https://www.acmicpc.net/problem/16918간만에 시뮬 문제 푸니.. 신난다ㅎㅎㅎㅎ..😇 (아님)시간의 흐름에 따라 폭발물을 폭발시키기 때문에 각 칸을 초로 관리했다. 폭발하면 0이 되고, 시간이 1초 지날 때마다 각 칸의 수를 늘렸다
https://www.acmicpc.net/problem/10775그리디 아이디어가 가미된 유니온 파인드 방식이다.유니온 파인드에서 각 노드의 부모는 제일 작은 숫자를 가진다는 특징이 있는데, 이를 활용하여 1 ~ gi 중 도킹되지 않은 가장 큰 게이트(=그리
https://www.acmicpc.net/problem/17298얼마전에 본 코테에서 본 문제랑 유사하다. 한시간 정도 시간 끌다가 테케 거의 다 실패해서.. 눈물 머금고 문제 리뷰 남기기 ( ˃̣̣̥᷄⌓˂̣̣̥᷅ )수열의 크기가 1000000므로, 이중으로
https://www.acmicpc.net/problem/2206벽 하나씩 깨보면서 bfs 돌려보면 시간 초과로 안된다. 정확히 8개월 전의 내가 그렇게 시도한 걸 발견❕맵 자체도 최대 1000 \* 1000이기 때문에, 하나의 BFS로 끝내는 게 좋다. 1도
https://www.acmicpc.net/problem/1253투포인터처음에는 |Ai| ≤ 1,000,000,000 조건을 고려 못하고 right 포인터를 기준 idx - 1로 잡았다가 틀렸다.배열의 값들이 음수 양수 포함인걸 고려해서 left = 0, ri
https://www.acmicpc.net/problem/11003✔️ Do it! 알고리즘 코딩 테스트 자바 편 풀이 참고👉 슬라이딩 윈도우 + 덱 활용정렬 효과를 내기 위해 덱을 활용한 점이 새로워서 기록한다 !1 ≤ L ≤ N ≤ 5,000,000라는