CS/PS (6) 썸네일형 리스트형 Greedy Problem in BOJ Greedy 문제만 몇 개 풀었는데 어쩜 이렇게 실력이 쓰레기같은지 하나 풀 때마다 턱턱 막혀서 화가 너무난다. 그래서 살짝 문제 몇개를 정리 해보려 한다. 아오... [BOJ] #8980 택배 풀이 가장 많이 고민한 그리디 문제 중 하나다. 다들 어떻게 이런 생각을 금방금방 해내는지 모르겠다 트럭에 실을 수 있는 최대 용량 C와 각각 마을에 있는 짐의 무게와 그 짐의 도착지가 주어진다. 이 문제는 왜 그리디일까? 한 번 방문한 도시를 다시 방문하지 않기 때문이다. 1번 도시부터 출발하여 오름차순으로 도시들을 방문한다. 따라서 다음과 같은 알고리즘을 적용할 수 있다. 옮겨야 할 박스의 정보를 도착 도시를 기준으로 오름차순으로 정렬한다. 정렬한 정보들 중 i번째 정보를 볼 때, i번째 짐의 시작도시부터 도.. [BOJ] #10255:교차점 풀이 CCW에 대해서 공부했다!!! 뭐 이런식으로 아 이따가 해야지 Code #include #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a) 0) return 1; else if (tmp st && d en && d = en && d [BOJ] #2066:카드놀이 풀이 9차원 DP배열을 이용하여 문제를 해결하였다. 뭔가 더 좋은 해법이 있을 것 같은데 귀찮다 이제… 내가 이래서 안되는듯 ㅋㅅㅋ 9차원 DP문제! 이런거 처음 풀어봐섴ㅋㅋㅋ 신기해서 포스팅한다 무려 11중 for문을 썼다!!!!! 이렇게 푸는 게 맞나 싶다. 뭔가 이상하다이상하다 이러면서 풀었다. dp차원 이렇게 높은거 처음써봐서 머리 터지는 DP를 너무 못해서 어떻게 풀어야할지 전혀 감히 잡히지 않았었다… 그러다가 안봐야지 안봐야지 했던 질문게시판을 보고 DP[5][5][5][5][5][5][5][5][5]을 써서 해결하셨다는 분들을 봤다. 내가 풀어야지 하고 이틀정도 생각한 것 같다. 머리가 돌대가리니까 생각하는 데 시간이 너무 오래걸린다. DP[][][][][][][][][]의 i번째 []은 i.. Code Jam to I/O for Women 처음으로 참여해 본 코드잼 39점을 받아 women에서 218등, 한국에선 10등 정도의 등수를 받았다. 심지어 한국에서도 등수가 2자리라니 ㅜㅠ 일단 느낀점은, 방학동안 진자 팽팽 놀기만 했구나 자존심 상한다 ㅋㅋㅋㅋㅋ이런 거에 자존심 상한다니 좀 어이 없을 수 있겠지만, 일단 submit 회수가 너무 많아서 점수가 같은 분들 중 penalty가 거의 제일 많았다. 코딩에나 아이디어 구상에나 잔실수가 너무 많은 것 같다... 구글 가고 싶은데 이대로는 안 될 것 같다. 등수보니까 미친듯이 자존심이 상한다. 딥러닝 스터디 대충 끝나는 대로 바로 boj/leetcode 들어가서 음청 공부해야 겠다. 제발 구글 인턴..! 제발 제발 블로그를 티스토리로 옮길 것 같은데 바로바로 안 쓰면 또 안 할 것 같아서 .. [BOJ] #11003:최소값찾기 풀이 sliding window기법을 사용하는 문제라고 해서 걍 dp인가 했는데 deque를 쓰는 문제였다. N,L의 범위가 5,000,000인데 븅신같이 세그먼트 트리로 풀려고 하고 있었다. O(N*lgN)이니까 대략 1.2억번의 계산을 해야한다. 근데 시간 제한이 3초인데...?으음... 하고 있었는데 입출력이 각각 5백만개씩 천만개가 되어서 그렇다고 질문에 써있다. #수정렬하기3 이라는 문제가 있는데 이 문제가 시간 제한이 2초인 이유난 천만개의 입출력 때문이라고 한다. 세그먼트로도 풀리긴 하는 것 같다! 대신 재귀호출 전에 조건을 잘 정해줘야 한다. 범위에 맞지 않으면 아예 호출도 안하는 식으로 ㅇㅇ 하지만 내가 나중에 이용하지 못할 것 같다... 결국 deque로 풀었다! 사실 deque 처음 .. [BOJ] #2178:미로찾기 풀이 top-down DFS (WA) top-down DFS (AC) BFS (AC) 원래 계정에 있던 걸 gyurious 계정으로 옮기면서 심심해서 다시 풀어본 BFS 미로찾기 문제이다. bfs/dfs 단계를 닦는 기초문제로 강의안 같은 데서 많이 볼 수 있다. 그런데 이걸 하루종일 여러가지 방법으로 다시 풀어보면서 이해가 안 가는 점을 발견했다. 먼저 첫번째 코드 top-down 을 DFS를 통해 재귀적으로 구현한 코드이다. (0,0) 부터 (N-1, M-1)까지의 모든 경로를 탐색한다. 경우의 수가 너무 많지 않나 싶지만 memoization을 이용, 한 번 갔던 칸에 또 접근 하면 해당 칸부터 (N-1, M-1)까지의 거리를 return하게 하여 시간복잡도를 줄였다. 이렇게 하면 되야 하는 거 아.. 이전 1 다음
