algorithm

https://www.acmicpc.net/problem/16201태그 : 수학, 구현, 분할정복을 이용한 거듭제곱, 해시맵아이디어는 쉬운 편이라는 생각이 들었다.R, C 값이 매우 컸고 그에 비해 K가 매우 작았다.그래서 비어있는 대부분의 행의 값들은 메모리

https://www.acmicpc.net/problem/1052태그 : 수학, 구현, 비트마스킹우선 문제에서 정답이 없을 경우 -1 출력이라고 적어놨는데.. 낚시였다. 어려운 조건은 아니라 금방 의심은 들지만 왜 굳이 저런 낚시를 넣었을까 싶다.아무튼.. 비

https://www.acmicpc.net/problem/12908태그 : 구현, 그래프, 다익스트라제목만 봤을 때는 단순 bfs류 냄새가 났으나..읽고나서 든 생각은 브루트포스였으나, 구현이 뭔가 이상해졌다.의심하면서 태그를 봤고, 그래프/최단경로 태그를 보

https://www.acmicpc.net/problem/26153태그 : 그래프, 깊이 우선 탐색그래프 문제인데, 브루트포스, bfs, dfs 등의 방법 등이 생각났다.같이 고민하던 동기분이 dp 아이디어를 내주셨고,처음엔 괜찮다고 생각이 들다가 영 아니라는

https://www.acmicpc.net/problem/14500태그 : 브루트포스풀이는 아마 대부분 문제 보자마자 떠오르는 것이 있을 것...처음에 블럭 모양 다섯 개가 끝인 줄 알고 날먹하려다가,회전 / 대칭이동이 가능하다는 것을 보고 뭔가 있나..하다가

https://www.acmicpc.net/problem/15831풀이 : 누적 합, 이분 탐색아이디어는 비교적 빠르게 떠올랐다. 우선 누적 합으로 색깔별 돌 누적 개수를 구한 후,O(N LogN)으로 0부터 순차적으로 시작지점으로 해서 흰 돌을 최소치 이상

https://www.acmicpc.net/problem/8972풀이 방법 : 구현, 시뮬레이션그냥 시뮬레이션1~9 방향으로 이동하기 편하게 dr / dc 배열을 사용했다.로봇이 겹치는 경우엔 배열에 좌표 넣었다가 한번 시뮬레이션마다 지워주었다.열심히 시뮬레이

https://www.acmicpc.net/problem/1038풀이 방법 : dp, 재귀1년 전에 풀이 기록이 있는 문제였다. 아마 당시에는 수학으로 접근해서 풀었던 것 같은데, 기억이 잘 나지도 않고Java도 연습할 겸 다시 풀어보았다.dpi = i자리

문제 태그 : 스택스택이라는걸 알고 풀기 시작했지만...앞에서부터 하나씩 검사하며 코드 짜다가 머리가 뜨거워졌다.뒤에서부터 보니 아이디어도 쉬워지고 구현도 쉬워졌다.뒤에서부터 하나씩 가져와 push하고, 현재 탑이 stack의 top보다 높다면 현재 탑보다 높은 탑 찾

태그 : dp, 배낭 문제 사고과정 가장 쉬운 풀이는 n * M * K 해서 모든 경우 구하는 것이겠지만... 공간/시간복잡도 모두 아웃이다. 여기서 그럼 시간을 줄이려면 결국 M이나 K 탐색 시간을 줄이는 것인데... 아무리 고민해도 떠오르지 않았다. 그래서

https://www.acmicpc.net/problem/1020풀이방법 : dp, 역추적, 구현DP 임을 알고 시작한 문제다수를 하나씩 늘리면 당연히 안되니까 시간을 줄여야하는데자릿수를 잘 사용하면 될 것 같다고 생각했다.일단 cnt배열 int cnti =

https://www.acmicpc.net/problem/28016태그 : dp, 임의 정밀도/큰 수 연산아이디어는 전혀 어려울 것이 없다. 소수점 문제만 아니면 골드 하위까지 내려가도 되지 않을까 싶다.그냥 2차원 dp를 위에서부터 갱신하면 된다.다만 문제를

https://www.acmicpc.net/problem/18244태그 : dp일단 보자마자 매 자릿수가 전 자릿수의 영향을 받기에 DP라는 생각이 들었다.dpik = i번째자리가 j로 시작하며 k개 연속, l방향으로 증감한 수의 갯수로 설정하고 풀었다.1개

https://www.acmicpc.net/problem/18244태그 : 시뮬레이션, 구현그냥 시뮬레이션 문제. 열심히 구현하면 된다.인덱스 연속으로 겹쳐야 하는 것을 제대로 안 읽어서 시간이 좀 더 걸렸다.가로세로는 변수명 짓기가 늘 어려운 것 같다

https://www.acmicpc.net/problem/1321태그 : 세그먼트 트리세그먼트 트리 복습 겸 즐찾 목록에 있던 문제를 하나 집었다.make_tree나 update는 그냥 일반 세그트리와 동일하게 구현하면 된다.get 하는 query만 조금 수정

https://www.acmicpc.net/problem/2138태그 : 그리디https://www.acmicpc.net/problem/1080문제를 읽자마자 생각난 문제이다. 바로 그리디하게 스위치를 누르면 되겠다고 생각했다.처음에는 첫 전구가 다를

https://www.acmicpc.net/problem/32069태그 : 그리디, 브루트 포스일단 L값이 눈에 띄었다. 좌표로 뭘 처리할 문제는 아니라고 생각했다.출력할 K 수가 비교적 작고, 가로등의 거리가 O(1)에 구해지니 O(K)에 구할 수 있겠다고

https://www.acmicpc.net/problem/2411태그 : dp문제를 읽고 바로 DP라고 떠올랐다.이동 경우가 두 가지밖에 되지 않고, 맵이 크지도 않아서 dp100으로 풀이를 시작했다.그런데 풀다보니 단순 평면 DP로는 경로별 갯수차이 세기가

https://www.acmicpc.net/problem/3078 태그 : 누적 합 사고 과정 N이 30만 이내이고, 이름 길이가 최대 20인 조건을 보고, 바로 sum300001 테이블을 떠올렸다. len[300001] 배열에 해당 인덱스의 이름의 길이를

https://www.acmicpc.net/problem/3078 태그 : 누적 합 사고 과정 N이 30만 이내이고, 이름 길이가 최대 20인 조건을 보고, 바로 sum300001 테이블을 떠올렸다. len[300001] 배열에 해당 인덱스의 이름의 길이를

https://www.acmicpc.net/problem/3910 태그 : 그래프 탐색, DFS(IDDFS?) 풀이 처음엔 DFS나 BFS로 접근하려 했는데, 꽤 고민을 해봐도 방법이 떠오르지 않았다. 백트래킹 태그를 봐도 감이 잘 오지 않았다. 그래서 G

https://www.acmicpc.net/problem/2616 풀이 방법 : DP길이 N인 객차들을 적절히 3분할 해서 최대 승객 수를 구해보자.뭔가 누적 합으로 한 번에 I~J의 승객 수를 한 번에 구할 수 있도록 해야겠다는 생각이 든다.DPi = i번

https://www.acmicpc.net/problem/31266태그 : DP, 비트마스킹, 비트필드DPDP 랜덤디펜스를 하다가 나온 문제이다.11명 총합의 최대치를 구하는건 어렵지 않아보인다.문제는 포지션별 최소 한 명인 조건, 골키퍼가 단 한 명일 조건이

https://www.acmicpc.net/problem/31434태그 : dp이제는 문제를 읽으면 이 정도는 바로 dp라고 떠올릴 수 있는 것 같다.매 초 행동은 1 + N가지이다. 그냥 s 그대로 당근 구매 / N번 스피드 효과 구매dpi = i초에서 j

https://www.acmicpc.net/problem/31566태그 : 그래프 탐색, 플로이드-워셜제한시간이 1초, N <= 100이였다.20만번의 쿼리 내에 특정 노드를 포함하지 않는 최단 경로를 찾아야 했다.그 과정에서20만번 쿼리 내내 다익스트라

https://www.acmicpc.net/problem/1517태그 : 정렬, 세그먼트 트리, 분할 정복가장 쉽게 푸는 법 : 0번 인덱스부터 오른쪽 배열에서 더 작은 값들의 갯수를 센다.N^2 -> 시간초과. 어떻게 정렬을 잘 해서 할 수 있나 고민을 해보

LCA란. B형 특강에서, 트리 관련 강의를 들었는데, 이 때 언급된 주제이다. LCA란 태그를 알고는 있었는데, 이번 기회에 공부하게 되었다. Lowest Common Ancestor. 최소 공통 조상. 트리에서 임의의 두 노드를 찍었을 때, 두 노드가 만나

https://www.acmicpc.net/problem/13306태그 : 자료 구조, 트리, 오프라인 쿼리이런 고민을 하다가, 태그를 열어보니 오프라인 쿼리라는 처음보는 친구가 있었다.이게 뭔... 하면서 오프라인 쿼리에 대해 또 검색을 해보았다..검색해보니

https://www.acmicpc.net/problem/12839태그 : DP, 비트마스킹, 비트필드DP 이런 사고 흐름을 가지고 풀어나갔다. 그런데 특정 박스에서 특정 카드를 선택하고, dp 테이블에 그때마다 나가고 들어오는 카드 양을 갱신하자니 계산이 너

https://www.acmicpc.net/problem/1970태그 : dpdpi = max(dpi + 1 + i와 j의 건배여부, dpi + dpk + 1)그런데 이 흐름으로 구현하면, 시간복잡도가 O(N^3)이 된다.빅오 표기법의 허점? 이라고 볼 수 있

https://www.acmicpc.net/problem/12105태그 : dp, 수학, kmp일단 문자열이 나타나는지 10000자리에 대해 판별해야 한다.kmp에 취소선을 그은 것은, kmp가 생각이 나긴 하지만 (n - m) \* m에 대해서도 문제없이 1

https://www.acmicpc.net/problem/1102태그 : dp, 비트마스킹, 비트필드dp문제가 굉장히 직관적이라 바로 dp인 것을 알 수 있을 정도이다.n개의 발전소가 켜지기 위해선 n - 1개가 켜진 상태에서, 어떤 발전소에서 한 개의 발전소

https://www.acmicpc.net/problem/28102태그 : 그래프, 유니온파인드, 이분 그래프처음 읽고나서 드는 생각은 k 조건이 너무 말도 안되게 크다는 것이였다. 여기서 오히려 거리를 실제로 구하는건 이상한 짓이니, 다른 방법을 찾아야 한다