프로그래머스16 프로그래머스 - 행렬과 연산 문제 설명 행렬이 주어진다. 주어진 연산에 의해 행렬이 이동하고 난 후 결과를 출력하는 단순한 문제이다. 하지만 이문제는 효율성 측정되는 문제라 최적화를 생각해야한다. shiftRow, rotate 두가지 명령만이 존재한다. 일반적인 시뮬레이션으로 구현하면 shiftrow는 최대 n *m 번의 연산이 필요하고 rotate는 n+m-2번이 필요하다. 그리고 명령어는 최대 10만이라 정확성은 통과할지라도 효율성은 당연히 실패한다. 최적화하기에 시도했던 방법은 연산의 일부를 합치면 최적화가 가능한가 그려봤다. 하지만 나오지 않았다. 2022 테크 여름인턴십 코딩테스트 해설 해당 내용을 참고하였더니 자료구조의 쓰임을 잘 알고있는지 체크하는 문제였다. 각각을 단순한 시물레이션이아닌 자료구조의 최적화를 유도했던 문.. Algorithm/프로그래머스 2023. 4. 8. 프로그래머스 - 알고리즘 공부 문제 설명 모든 문제를 풀수 있도록 알고력과 코딩력을 얻는데 걸리는 최소 시간을 구하는 문제이다. 주의사항 배열의 인덱스 범위 설정 최고 가질 수 있는 알고력과 코딩력은 최대 150이다. 그런데 내가 문제를 풀 때 150이상의 알고력 또는 코딩력을 얻을 수 있음을 유의해야 한다. 배열을 더 크게 잡거나 혹은 배열 범위를 넘어갈때 안쪽으로 다시 조절해줘야 한다. 다익스트라 풀이 주의사항 아마 효율성 부분을 통과할 수 없을 수 있다. 이부분은 우선순위 큐에 있는 쓸데없는 데이터들이 많아서 그런것일 수 있다. 하지만 또다른 에외도 존재한다. 정제를 안해줘서 가 아니라 코드가 좀 길어서 시간초과가 난다.. 스타일 차이인데 왜 시간초과가 나는지 모르겠다.. TRY 다이나믹 2022 테크 여름인턴십 코딩테스트 해설.. Algorithm/프로그래머스 2023. 4. 6. 프로그래머스 - 등산 코스 정하기 문제 설명 n개의 등산지점이 있다. 출발지점으로 부터 목적지 지점까지 , 목적지점으로부터 출발지점까지 최소 인텐시티를 등상코스를 정하라 인텐시티란 거쳐가는 최대 간선 비용이다. 생각한 아이디어 인텐시티를 짧게 하려면 짧은 코스트를 가진 방향 리스트로 부터 구할 수 있다고 생각했다. 하지만 일반적인 다익스트라는 한 지점으로부터 다른지점의 최소 거리를 구하는 것이다. 조금 변형하여 최소거리가 아닌 최소 인텐시티 테이블을 두고 구하면 어떨까라는 아이디어는 해설을 참조하여 발견했다. 주의사항 간선의 정보를 저장하는 구조를 잘만들어야 한다. 봉우리는 단 한번만 지나야 하는 규칙이 존재한다. 다른 출입구는 거칠 수 없어야 한다. 이런 경우가 있을 수 있다 봉우리가 가장 작은 간선비용을 가져서 한번더 지날 수 있기 .. Algorithm/프로그래머스 2023. 4. 6. 프로그래머스 - 혼자서 하는 틱택토 문제 설명 선공과 후공의 순서로 틱택토 게임을 한다. 주어진 보드가 주어졌을 때 규칙을 지키면서 제대로 이행한 보드인지 판별하는 문제이다. 규칙을 잘 지키면서 했으면 1을, 안지켰으면 0을 리턴한다. 주의사항 규칙의 반례를 직접적으로 찾아 나가야한다. o-x를 뺀 개수는 무조건 0이 나오거나 1이 나와야 한다. [선공과 후공의 관계이기 때문에] o와 x가 둘다 틱택토를 완성할 수는 없다 [그러면 o가 먼저 틱택토 나오고 끝나야 한다] 3) o만 틱택토를 완성했다면, o-x의 차이는 무조건 1이여야 한다 [선공과 후공의 관계이기 때문에] 4) x만 틱택토를 완성했다면, o-x의 차이는 반드시 0이나와야 한다. [선공과 후공의 관계이기 때문에] 3,4을 찾는데 엄청 오래걸렸다.. 풀이 static final.. Algorithm/프로그래머스 2023. 4. 3. 프로그래머스 - 점찍기 TRY [완전탐색] 거리 백터를 이용한 완전 탐색 FAIL [시간 초과] k가 1이고 거리제한(d)이 10만일 경우 n^2으로 시간 초과로 이루어짐. 풀이 [점과점 사이의 거리 공식을 이용] x를 정해버리고 y가 갈 수 있는 최댓값을 구한후 누적 카운팅함. 주의사항: 자료형의 범위 long 변수에 int 변수를 제곱하더라도 그 안에서는 overflow가 일어남. /** * note: 한칸식 전진하는 스텝은 4개 빼고 나머지 TLE 발생 * 풀이: 점과 점 사이의 거리 공식을 이용하여 x축을 구하고 거기에서 y축의 최대값을 구하여 그 안에서 배수의 개수로 나누어 구함. * - 즉, x를 정해버리고 y가 될 수 있는 수를 찾음. * @param k: 방향 백터 배수 * @param d: 원점과의 거리 제한 .. Algorithm 2023. 3. 2. 이전 1 2 3 4 다음
