목록알고리즘 문제/Programmers (27)

기술 블로그

스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971 dp 동적계획법 코테 [0] [1] ... [i-2] [i-1] [i] ... 에서 i번 째 스티커를 뜯을 수 있는 경우는i-1번 째 스티커를 뜯지 않아야 한다.다시 말하면, [i-2]까지 누적된 최댓값에 해당 i번 째 스티커를 더해준다. 즉, dp[i] = dp[i-2] + sticker[i] 그리고, i번 째 스티커를 뜯지 않을 수 있으므로 dp[i] = dp[i-1]도 고려해줘야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465..
알고리즘 문제/Programmers 2020. 6. 26. 12:12
올바른 괄호의 개수

https://programmers.co.kr/learn/courses/30/lessons/12929 카탈랑(또는 카탈란) 수이다. f(n) = (2nCn) / (n+1) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576import java.io.*;import java.util.*; public class Solution { static BufferedReader br; static BufferedWriter bw; static int c(int n, int r) { if(r == 0 || r ==..
알고리즘 문제/Programmers 2020. 6. 25. 23:28
베스트앨범

https://programmers.co.kr/learn/courses/30/lessons/42579 제가 푼 이 코드가 정답이긴 하나 복잡하니 다른 블로그의 코드를 참고하세요. 후에 다시 풀 예정입니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301..
알고리즘 문제/Programmers 2020. 6. 24. 18:11
셔틀버스

https://programmers.co.kr/learn/courses/30/lessons/17678 핵심은 다음 2가지이다. 1. 모든 버스를 사용하였고(n만큼), 모든 손님을 모두 다 태웠을 경우에는 마지막에 탄 사람의 시간(=Last)에서 1을 빼준다.2. 위의 경우가 아니라면, 버스의 마지막 운행시간이 정답이다. 주의할 것은 35~37번 째 줄에서 break를 통해 time이 계산되기 전에 빠져 나오는 경우도 생각하자. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283..
알고리즘 문제/Programmers 2020. 6. 24. 13:06
예산

https://programmers.co.kr/learn/courses/30/lessons/43237 budgets를 Vector에 넣어주고, Vector를 정렬해주는 방식(Collections.sort())으로 구현했다가 효율성에서 시간 초과가 발생했다. 그래서, 그냥 Arrays.sort()를 사용했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103import java.io.*;import ..
알고리즘 문제/Programmers 2020. 6. 24. 01:31
N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895 문제 분류가 dp라서 dp로 접근하려다가 계속 고민해봐도 안 풀리길래 dfs로 풀었다. 최댓값이 32,000이므로 N을 활용해서 최대 NNNNN까지 만든 후에 활용하면 된다. 이때, +와 *는 상관없지만, -와 /는 연산자를 기준으로 앞, 뒤의 순서에 영향을 받기 때문에 이 부분도 고려해준다. 사실 long을 쓸까 말까 하다가, int로 썼다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778..
알고리즘 문제/Programmers 2020. 6. 24. 00:04
외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062 카카오 kakao 백트래킹 BruteForce 브루트포스 기출 복습 구현 필수 추천 코테 코딩 프로그래머스 2020 KAKAO BLIND RECRUITMENT 처음에 bitmask + dp로 풀려다가 인덱스를 몇 차원으로 해야할지 무엇으로 구성해야할지 헷갈려서 그냥 Backtracing으로 접근하였다. 핵심은 모든 경우의 수(조합)에 대하여 vector v를 구성한다. 그리구, 구성한 vector v에 대하여 또 다시 weak에서 출발점을 달리하여 새로운 weak(temp)를 구성한다.(temp = 새로운 weak) 예시) weak = {3, 5, 7, 9}, n = 12라고 하고, 출발점을 7로 한다면..
알고리즘 문제/Programmers 2020. 4. 3. 14:15
블록 이동하기

https://programmers.co.kr/learn/courses/30/lessons/60063 2020 KAKAO BLIND RECRUITMENT 카카오 bfs 구현 처음 풀었을 당시에 못 풀었던 문제이다. 내가 작성 중이었던 코드를 보니 map까지 활용하고 있었다. 왜지? 하여튼 오늘 다시 풀어봤는데 한 번에 통과하였다. 핵심은 ㅡ과 | 모양에 따른 구현을 다르게 해주고, 각각의 모양에서도 어떤 위치를 중심축으로 정할 것이고 또한, 그 중심축에서도 어느 방향으로 회전할 것인지에 대한 BFS를 구현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575..
알고리즘 문제/Programmers 2020. 4. 1. 20:59
이전 Prev 1 2 3 4 Next 다음