코딩하기 좋은날

1/6~ 1/17까지 2주의 알고리즘 특강을 듣고 어제 삼성 SDS B형(프로시험)도 치고 왔습니다. 우선 가게되면 아침 9시부터 저녁 6시까지 하루종일 문제를 풀어서 문제는 정말 많이 풀게 되는 것 같습니다. 또실제로 실력이 굉장히 좋으신 임직원분이 가르쳐 주셔서 풀다가 모르는 것이 생길 때 바로바로 물어볼 수 있어서 좋았습니다. 수업은 자체 제작된 교재로 진행하며 백준 문제를 가지고 합니다. 알고리즘 기초, 자료구조, 정수론,조합론,그래프, DP 의 주제들이 다루어지는데 사실 여기서 배우는 알고리즘을 아예 모르고 간다면 자기 혼자서 그날 모르는 알고리즘 공부한다고 다른 문제들을 못 풀게 됩니다 ㅠㅠ (실제로 단절점이나 LCA는 잘몰라서 그날 힘들었습니다.) 교육을 끝내고 삼성 sds B형(pro) 시..

이번 겨울에 삼성 sds 알고리즘 특강에 참가하게 되었습니다. 1월 6일부터 약 2주간 진행된다고 하네요. 신청하고나서 알고리즘 문제를 풀었습니다. 아마 많이 푼 사람들을 뽑아서 교육 시키는 것 같습니다. 작년 초부터 알고리즘 문제를 풀기 시작했는데 한 4~5개월 바짝하다가 거의 안 풀고 있었는데 아는 사람의 추천으로 한번 해볼까 싶어 신청을 하였고 5문제중에 저는 4문제를 풀었습니다. 기간은 한 1주일 정도 준것 같습니다. 문제를 간단하게 대충 설명하자면 1번은 큐브를 돌리는 문제였는데 주어진 대로 돌려서 면을 출력하는 구현 문제였습니다. 2번은 스도쿠? 관련 문제였고 일반적으로 스도쿠를 해결하는 방식처럼 dfs+백트래킹 하면 된걸로 기억합니다. 3번은 분할정복 이용하여 해결하는 문제였습니다. 4번은 ..

https://www.acmicpc.net/problem/17069 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 초기에 1,2에있는 파이프를 이리저리 옮겨 끝좌표 까지 갈수있는 경우의 수를 구하는 문제입니다. 각각 가로 세로 대각선일때 이동가능한 방향과 조건들이 주어져있습니다. 파이프 옮기기 1같은경우는 bfs나 dfs로도 해결이 가능하였을걸로 아는데 옮기기 2는 N의 크기가 커져서 dp를 사용하여 풀어야 합니다. dp배열은 우선 좌표정보와 좌표에서 상태를 저장해야하므로 3차원으로 잡고 상태 같은 경우는 0,1,2 순으로 가로,세로,대각선으로 정했습니다. dp식은 크게 어려울것이 없습니다. 현재 좌표가 i,j라하면 dp[i+1][j][0] = dp[i][j+1][0] = dp[i][j]..

https://www.acmicpc.net/problem/17135 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 적들이 주어진 맵에 존재하고 성벽에 궁수 3명이 있을때 궁수들의 위치를 배치하여 가장 적을 많이 처치 할 수 있는 수를 구하는 문제입니다. 모든 가능한 궁수들의 배치에 대하여 각각 시뮬레이션을 해보면 됩니다. 주어진 조건에 따라 현재 제거할 수 있는 가장 가까운 적(거리가 가장가까운)들을 차례대로 제거하고 적들을 한칸씩 아래로 내리면서 더이상 적이 없을때까지 진행해주시면 됩니다. 저는 벡터에 적들의 좌표를 유지시키면서 풀었습니다. 다음은 코드입니다. #include #include #include #include using namespace std; int N,M,D; int..

https://www.acmicpc.net/problem/12920 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이문제는 평범한 배낭1의 업그레이드(?) 문제입니다. 아마 이문제 푸시는 분들은 평범한 배낭1문제를 푸셨을 거라고 생각하는데요. 두문제의 유일한 차이는 물건의 개수입니다. 이문제 같은 경우 물건의 개수가 여러개 일 수 있습니다. 따라서 각각 경우를 모두 고려해주어야 하는데 어떻게 해야할지 생각이 잘 안나서 다른 분들의 풀이를 참고 하였습니다. 가장 중요한 아이디어는 사용할 수 있는 물건의 개수를 2의 제곱수의 합으로 분리 시키는 것입니다. 예를 들어 A라는 물건이 7개 있다면 각각 1개 / 2개 /4개의 물건으로 분리시키고 그에 맞는 만족도를 저장합니다. 이런식으로 분리시키면 각각 1,..

https://www.acmicpc.net/problem/10942 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 수열이 주어졌을때 구간에 대한 팰린드롬 여부를 출력해야 하는 문제입니다. 수열의 길이는 2000 이고 총 100만개의 쿼리가 들어오므로 모든 구간에 대한 팰린드롬 여부를 미리 구해놓아야 합니다. 따라서 저는 2차원 dp배열을 선언하고 재귀함수를 호출하는 식으로 구했습니다. 길이가 1일때와 2일때는 미리 구해야 하는데 길이가 1인경우는 항상 팰린드롬이므로 1을 저장합니다. 길이가 2일때는 두문자가 같다면 팰린드롬이므로 1을 저장하고 그렇지 않으면 팰린드롬이 아니므로 0을 저장합니다. 이후 구간의 양끝에서부터 길이를 줄여나가면서 찾으면 됩니다. 현재 함수에서 보는 구간이 s,t라..

https://www.acmicpc.net/problem/2248 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 이전에 쓴 1256 사전과 유사한 문제입니다. N자리의 이진수가 있을 때 L개 이하의 1이 존재가능 하다고 할 때 이중에서 I번째 순서의 이진수를 찾는 문제입니다. I는 범위안에 있도록 주어진다 했으니 최대 가능한 I가 2^31번째 일것입니다. 따라서 이전의 사전 문제처럼 dp를 이용하여 개수들을 저장하고 skip하는 방식으로 해결을 하여야 합니다. dp배열에는 이항계수 성질인 nCk = n-1Ck-1 + n-1Ck 를 이용하여 n개의 비트중 1이 k개일때를 저장 했습니다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 이렇게 저장 한뒤 원하는 이진수를 찾는..

https://www.acmicpc.net/problem/1256 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 a와 z로만 이루어진 단어가 사전순으로 정렬 되있을때 K번째 단어를 찾는 문제입니다. a,z가 최대 100개이고 K가 10억개이므로 단순히 개수를 세는 방법으로 해결이 불가능합니다. 문제를 해결하기 위해서 저는 먼저 2차원 배열에 a가 i개 z가 j개 있을때 나오는 조합의 개수를 저장하였습니다. 식을 세워보면 dp[i+1][j] = dp[i][j] * (i+j+1) / (i+1) dp[i][j+1] = dp[i][j] * (i+j+1) / (j+1) 과 같은 식으로 개수를 구할 수 있습니다. 각 조합의 개수를 구한다음 이제 K번째 단어를 찾아야 하는데 문자를 앞에서부터 하나씩 ..