본문 바로가기

알고리즘

(32)

[백준] 12865번 평범한 배낭 문제 제목처럼 평범한 Knapsack 문제 입니다. 하지만, 너무 간만에 봐서 다 까먹고 쉽게 풀지 못한 문제이기도 합니다...ㅠㅠ backtracking으로 풀어도 봤습니다. dfs로 재귀방식으로 모든 경우를 따져봤지만 역시나 시간초과가 뜹니다. 결국 DP로 풀어야 하는 문제입니다! DP 변수의 각 index(물건) 마다 0~k까지의 무게에 대해 최대값을 넣어주면 됩니다. 2가지 경우로 나눠서 풀어주기만 하면 간단합니다. 1) i 번째 물건을 안넣는 경우 2) i 번째 물건을 넣는 경우 1번의 경우는 그냥 i-1의 무게를 유지해주면 되는 문제고, 2번의 경우는 현재 무게( j ) - 넣고자 하는 물건의 무게에 해당하는 v값을 더해주면 됩니다. 대신 넣을 때는 주의해야 할것이, 넣는 것이 오히려 안넣을 ..

[백준] 9251번 LCS 단순히 LIS(Longest Increasing Subsequence) 처럼 풀려고 하다가 엄청 헤멘 문제 입니다.. LCS를 해결하는 방식이 있습니다. 우선 표를 통해서 먼저 설명하겠습니다. (문제에서 주어진 것 처럼 ACAYKP, CAPCAK를 활용합니다) A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 최종적인 표의 모습입니다. 알면 쉽게 풀리는.. 2가지 규칙만 적용하면 끝나는 문제입니다. 1) 같은 문자가 나오면 대각 왼쪽 상단 + 1 2) 다른 문자가 나오면 max(상, 좌) 먼저, 각 문자 배열 + 1만큼 DP(Dynamic..

[백준] 2206번 벽 부수고 이동하기 벽 부수는 것을 처음에 너무 간단하게만 생각했다가 여러번 틀린 문제입니다. queue에 넣는 조건을 잘 나누지 않으면 메모리 초과가 나오기 십상이니 명확하게 구분해야만 해결할 수 있는 문제였습니다. 먼저, 현재 좌표의 방문 여부를 벽을 부순적이 있는 경우와 없는 경우로 나눠서 진행해야 합니다. 안그러면 아래 예시와 같은 경우에 -1이 나오게 됩니다. 4 4 0000 0 1 1 1 00 1 1 00 10 한번 방문해서 실패했다고 무조건 visited를 true로 바꿔주면..! 아래처럼 되버려서 실패하고 맙니다. (0,0)->(0,1)->(1,1)->(2,1)->(3,1) 경로로 이동해서 한번 실패했다면, 해당 경로는 전부 visited = true가 되버립니다. 그러면, (0,0)->(1,0)->(2,0)..

[카카오 코딩 테스트] 길 찾기 게임 https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/ 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요. 지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다. 문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 […] tech.kakao.com 처음에 엄청 복잡하게 생각해서 여러 시행착오를 겪은 문제입니다....

[카카오 코딩 테스트] 무지의 먹방 라이브 https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/ 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요. 지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다. 문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 […] tech.kakao.com 4번 무지의 먹방 라이브는 효율성이 중요한 문제였습니다. 정확성만..

[카카오 코딩 테스트] 후보키 https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/ 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요. 지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다. 문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 […] tech.kakao.com 3번 문제 후보키는 정답률이 16.09%였습니다. 완전 탐색을 어..

Bit 연산으로 집합구하기 완전탐색을 하기 위해서는 여러 방법이 있을 수 있겠지만 만약 int arr[] = { 1, 2, 3, 4 }; 라는 배열이 있다고 할 때, 이 부분 집합들을 구해야 한다면 어떻게 해야 될까요?? 부분집합 크기가 1인 경우, 2인 경우 .. 4인경우 다 나눠서 구할 수는 있지만 만약 arr의 크기가 100이라면? 그보다 크다면?!! 딱히 생각나지 않습니다.. 이때! bit 연산으로 쉽게 구할 수 있습니다! 0000 0001 0010 ... 이런식으로 각 결과마다 1인 부분만 출력한다면 쉽게 부분집합을 구할수 있겠죠?? 먼저 코드를 보여드리고 설명하도록 하겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace s..

[백준] 1707번 이분 그래프 [풀이] 백준 사이트의 정답률은 작성 당시 22퍼센트 밖에 안되서 지레 겁먹을수 있으나! 이분 그래프의 개념만 알면 bfs 혹은 dfs로 쉽게 풀수 있는 문제 입니다!! 문제의 설명만 보면 뭐가 이분그래프인지 잘 모르겠는데요, 그림을 보면 바로 알 수 있습니다! 위 그림 처럼 색이 서로 다르게 칠해질 수 있어야 이분 그래프 입니다. 쉽게 말해 니편 내편 가를 수 있어야 한다는 것입니다 ㅎㅎ 저는 bfs로 풀이 했는데요, 현재 노드가 1번 팀이라면 다음 노드는 2번 팀 이런식으로 팀을 구분 했고, 만약 팀이 겹치게 된다면 바로 false를 리턴했습니다. 아래는 풀이한 코드입니다 :) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

이전 1 2 3 4 다음

티스토리툴바