'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (2 Page)

[백준] 연구소 3 (조합, bfs)

2024.04.07

https://www.acmicpc.net/problem/17142 풀이과정 0. 입력을 받을 때 채워야 할 빈칸의 갯수를 저장합니다. 1. 백트래킹을 활용해서 바이러스들의 조합을 선택합니다. 2. 선택된 바이러스들에 대해 bfs를 수행하여 퍼트립니다. 바이러스를 퍼트릴 때, 빈칸과 바이러스가 있는 칸에 대해 구분해서 코드를 작성해야 합니다. 빈 칸의 경우 0번 풀이과정에서 저장한 목표와 비교하기 위해 cnt값을 증가시켜 줍니다. 바이러스의 경우 cnt 값을 증가시키지 않고 방문처리와 bfs큐에 넣는 동작만 수행합니다. 처음에는 swea의 지뢰문제와 헷갈려서 바이러스를 만나면 계속 퍼지도록 구현해서 계속 틀렸습니다 ㅠㅠ 3. 빈 칸을 다 채웠으면 이동한 시간을 return 합니다. bfs에서 시간은 계속..

🥇코딩테스트:Algorithm

배열 시계방향 회전 공식

2024.04.06

N = 행 길이 M = 열 길이 int[][] origin = { {1,2,3}, {4,5,6}, {7,8,9} }; // 원본 배열 int[][] result; // 회전 배열 시계 방향 90도 회전 : (i,j) = (N-1-j, i) 혹은 (j, N-1-i) = (i,j) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { rotate_arr[i][j] = arr[N - 1 - j][i]; } } 반 시계 방향 90도 회전 : (i,j) = (j, N-1-i) 혹은 (N-1-j, i) = (i, j) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { rotate_arr[i][j] = ar..

🥇코딩테스트:Algorithm

투포인터 알고리즘

2024.04.05

구현 코드만 간략하게 작성..(외우기 위해서 😂) 리스트에 순차적으로 접근해야 할 때 사용할 수 있습니다. 투 포인터 알고리즘 기본 포멧int N = 5; // 데이터의 개수 Nint M = 5; // 찾고자 하는 부분 합 Mint[] data = {1,2,3,2,5};int cnt = 0;int interval_sum = 0;int end = 0;for(int start=0;start

🥇코딩테스트:Algorithm

[백준] 드래곤 커브 (구현)

2024.04.05

문제 : https://www.acmicpc.net/problem/15685 풀이과정 1. 드래곤 커브를 그리는 함수를 구현해야 합니다. 1-1. 리스트를 활용 드래곤 커브는 현재까지 만들어진 모양을 바탕으로 새로운 모양을 만들게 됩니다. 리스트를 활용해서 드래곤 커브의 방향을 구현했습니다. 1-2. 90도 회전 90도 회전의 경우 0 방향은 1 1 방향은 2 2 방향은 3 3 방향은 0 이 됩니다. (현재방향+1)%4 연산을 통해 이를 구현할 수 있습니다. static void update_history(){ // g번 이동시키기 for(int i=0;i=0;j--){ history.add((history.get(j)+1)%4); } } } 1-3. 두 번 이동 시키기 정사각형의 갯수를 구하기 위해 드..

🥇코딩테스트:Algorithm

[프로그래머스] 프로세스 (우선순위큐)

2024.04.02

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42587 풀이과정 1. 우선순위가 가장 높은 프로세스를 찾아야 합니다. 👉우선순위 큐를 활용 O(logn)하여 구할 수 있습니다. 2. 문제의 2번 조건을 구현해야 합니다. 2번 조건의 동작에서 다시 큐에 넣는 원소들의 순서는 유지됩니다. 위 그림과 같이 (2,1)은 뒤로 가야하는데 이때 뒤로 가는 (2,1)의 순서는 유지됩니다. 따라서 큐를 활용해서 구현할 필요 없이 주어진 priorities 배열들을 순서대로 무한순회(?)하면 됩니다. 3. 문제에서 요구하는 정답인 해당 프로세스가 몇 번째로 실행되는지 파악해야 합니다. 배열들을 무한순회(2번 풀이과정) 하며 우선순위가 가장 높은 프로세스..

🥇코딩테스트:Algorithm

[프로그래머스] 의상

2024.04.01

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42578 풀이과정 처음의 접근 : 옷 종류 별 갯수를 저장하는 배열을 생성하고, 그 배열을 백트래킹으로 탐색하며 모든 경우에 대해 계산을 진행하려 했습니다. 하지만 이렇게 하면 시간복잡도를 만족할 수 없었습니다. 새로운 접근에 대한 생각 : 진 부분집합에 대해 생각했습니다. 진 부분집합의 갯수는 2^n - 1 이므로, 이 문제에서 최악의 경우 n = 30이 되므로 처음의 접근과 같이 완전탐색을 진행하면 당연히 시간초과가 발생하는 것이었습니다. 올바른 풀이 1. 옷 종류별로 옷의 갯수를 + 1 해줘야 합니다. 여기서 +1은 (입지않음을 의미합니다) 2. +1된 옷 종류별 옷의 갯수들 끼리의..

🥇코딩테스트:Algorithm

[프로그래머스] 방의 개수

2024.03.29

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges 풀이과정 우선 방이 생성되는 조건에 대해 파악해야 합니다. 방이 생성되는 조건은 1. 이전에 방문했던 정점을 다시 방문해야 함 2. 이전에 연결한 선분이 아닌 새로 생긴 선분이어야 함 각 정점에 대한 그래프를 코드로 나타내는 과정이 중요하다고 생각합니다. 이때, 기존의 그래프 문제와 다르게 인접행렬이나 인접리스트로는 해당 문제를 구현할 수 없습니다. arrows의 크기가 1 이상 100,000이하라는 조건으로 인해 인접 행렬의 경우200_001 * 200_001 의 크기가 되기 때문입니다. 아래와 같이 HashMap 자료구조와 Node 클래스를 통해서 그래프를 구현할 수 있습니..

🥇코딩테스트:Algorithm

이분탐색

2024.03.06

이분탐색은 크게 존재여부를 파악하는 알고리즘, lower bound와 upper bound를 찾는 알고리즘 두 가지가 있다. 존재여부를 파악하는 경우 = 중복원소를 고려하지 않음lower bound와 upper bound = 중복원소를 고려존재여부 파악 (중복원소 고려하지 않음)public static int binarySearch(int[] arr, int key) { int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스 int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스 while(lo arr[mid]) { lo = mid + 1; } }} 중복원소 고려lower boundprivate static int lowerBound(int[] arr, in..

티스토리툴바