본문 바로가기

알고리즘

[충격] PCCP 레벨 0 점 맞음 항상 코테 풀면 테케 다 맞아서 잘한다고 착각한 것 같다. 거기서도 시간 초과가 발생했던 거겠지. 음...문제 범위를 보며 10의 5승이라 반복문 하나만 쓰면 완전 탐색해도 괜찮겠지 여겼는데 뭐지... 나중에 PCCP 기출 나오면 문제 풀어봐야겠다. 더보기
다익스트라 알고리즘 개념 java 1. 개념(1) What? 다익스트라 알고리즘이 무엇인가요? 💡다익스트라 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리 비용을 구하는 알고리즘이다.다익스트라를 사용하면 시작 정점 S에서 직,간접적으로 연결된 모든 정점으로 가는 최단 거리 비용을 한 번에 구할 수 있다.(2) Why? 왜 해당 알고리즘을 써야 하나요? 🤔💭해당 알고리즘을 처음 접한다면 아마 지금까지 가중치가 없는 그래프에 대해서 정점 간의 최단 거리를 구하는 문제만 접해왔을 가능성이 높다. 가중치가 없는 그래프에서의 정점 간의 최단 거리는 BFS를 활용하면 쉽게 풀렸다. 왜냐하면 정점 사이를 잇는 간선의 개수가 곧 비용임으로 BFS를 돌렸을 때, 만나기까지 사용하는 간선의 개수만 세면 되었기 때문이다.하지만 가중치가 있는 그래.. 더보기
[프로그래머스] 선입선출 스케줄링 java 문제 풀이 1. 문제 설명문제 링크처리해야할 작업의 양: n코어의 개수와 코어마다 일을 처리하는데 걸리는 시간 : int [] cores맨 마지막에 일을 끝내는 코어의 번호를 구하라. (번호는 1부터 시작한다.)2. 접근 방식KEY WORD: binary_search이분탐색으로 n의 작업량 이상의 처리를 하는 시간대 중 가장 작은 시간대(k)를 구한다.(n = 15라고 하자. 시간별로 짤랐을 때, 16이 가장 가까운 수 이다.)코어의 맨 마지막 자리부터 k 시간대 일을 하는 녀석을 하나하나 제외시켜가면서 맨 마지막으로 n번째 일을 처리한 코어를 구하고 번호를 출력한다.9시간째에서는 1번 코어와 2번코어만 일하며 16번째인 2번 코어를 제외하면 1번코어가 target값인 15를 처리하는 마지막 코어이다. 그래서 답은.. 더보기
[백준] 6064 카잉 달력 java 풀이 1. 문제 설명문제 링크이란 달력이 있는데, (x,y) -> (1,1) , (2,2) 가다가 x가 M을 넘거나, y가 N을 넘으면 다시 1로 돌아온다.예제에 설명되어 있는 대로, 일때, 13번째 년도는 이 된다. , , , 순으로 온다.문제에서 M,N,x,y를 줄 때, 달력에서 가 몇 번째 년도인지 구하라.2. 접근 방식이것도 도저히 생각이 안나서 다른 사람 풀이 봤다. (요즘 왜 이렇게 풀이가 생각이 안나지? 더 열심히 해야겠다.)KEY WORD: 유클리드 호제법, LCM과 GCD의 관계먼저 ~ 까지 순서대로 번호를 매긴다고 해보자. 이때 우리가 구해야하는 는 K번째 수라고 해보자.x는 K를 M으로 나누었을 때의 나머지이고, y는 K를 N으로 나누었을 때 나머지 이다.에서 는 33번째 수인데,.. 더보기
[프로그래머스] n*2 배열 자르기 문제 풀이 java 1. 문제 설명문제링크2차원 배열의 값을 집어넣고, 그것을 1차원 배열로 늘어뜨려서, 문제에서 원하는 구간 내의 숫자들을 묶어서 반환하는 문제이다.2. 접근 방식KEY WORD: Brute Force, 1차원 배열과 2차원 배열의 위치 관계해당 문제는 n의 maximum이 10^7이므로, O(n)을 초과하는 시간 복잡도를 사용하지 못한다. 따라서 2차원 배열에 값을 다 집어넣고, 그것을 1차원으로 만드는, 마치 문제에서 지시한대로는 풀이를 하지 못한다. 또한 1차원 배열을 바로 만들더라도, n*n은 배열의 메모리를 초과하는 값을 초래할 수 있기 때문에 1차원 배열 전체를 만드는 것도 무리다.따라서 우리는 정확히 left ~ right 까지의 배열을 만들어 값을 구해 반환해야 한다.(1) 1차원 배열 2.. 더보기
[프로그래머스] 행렬 테두리 회전하기 문제 풀이 java 1. 문제 설명문제 링크(1) 회전 시킬 부분 행렬의 좌상단, 우하단의 List가 주어진다.(2) List의 값마다 행렬을 시계 방향으로 회전시킨다.(3) 회전할 때, 움직였던 값 중 가장 작은 값들을 모아서 반환한다.2. 접근 방식KEY WORD: BRUTE FORCE, 배열 회전배열 회전은 브루트 포스 문제를 풀 때 단골로 나온다. 코딩 테스트에서도 배열 회전이라는 키워드가 단독으로 문제에 나오지 않지만, 문제의 조연으로는 자주 등장했던 것 같다. 그래서 회전하는 법에 대해 알아두는 것은 중요하다.문제에서, 회전하는 모습을 친절하게 예시로 알려준다.14 -> 8의 자리로, 8이 9의 자리로 시계 방향으로 움직이고 있음을 볼 수 있다.그렇다면 구현을 할 때는 어떻게 해야할까? 구현할 때는 반 시계 방향.. 더보기
Programmers K진법에서 소수 개수 구하기 java 쉬운 풀이^^ 1. 문제 설명문제 링크2. 접근 방식해당 문제는 문제에서 하라는 대로만 하면 된다.(1) 받은 숫자를 N진법으로 변환한다.문제를 풀던 당시에는 Integer.toString(n, radix) 라는 문법을 알지 못했다. 해당 문법은 n을 2번째 인자인 radix진법으로 변환해서 String으로 반환한다. Integer.toString(n,2)이면 n을 2진법으로 반환해서 String 값으로 반환하는 것이다.이 문법을 몰라서, 직접 반환했다.반환 방법은 다음과 같다.바꾸려는 수를 n, 진법을 radix라고 할 때, n%radix == 0 이 될 때까지 n을 radix로 나눈다.이때 나머지 값을 저장하고 있는다.드디어 n%radix == 0 이 되면 지금까지 나왔던 나머지들을 역순으로 줄 세운다.자세한 변환.. 더보기
[백준] 2667_단지번호 붙이기 java 쉬운 풀이! 1. 문제 설명문제 설명2. 접근 방식KEY WORD: BFS2차원 배열에 값을 담는다.번호 별로 의미가 있다. (0 = 벽, 1 = 미방문한 아파트 단지, 2 = 방문한 단지)(1) 2차원 배열을 순회하다가 값 == 1인 것을 만나면, 해당 값을 시작으로 BFS를 돌린다. 현재 값의 사방을 탐색한다. 사방의 값 중 1인 값이 있으면 큐에 넣고, 해당 위치의 값을 2로 바꾼다. 큐가 빌 때 까지 (더 이상 사방 탐색을 해도 값 = 1이 안 나올 때 까지) 반복한다.(2) 1번은 첫 조회에서 만난 아파트의 아파트 단지 전체를 한번에 보는 것이다. 따라서 1번의 반복 횟수가 곧 아파트의 개수이다.(3) 아파트 단지를 단지내 아파트의 개수에 따라 오름차순으로 정렬한다. 3. 코드 분석import java.i.. 더보기

티스토리툴바