'📂코딩테스트:CodingTest' 카테고리의 글 목록 (3 Page)

투포인터 알고리즘

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

📂코딩테스트:CodingTest

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

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. 두 번 이동 시키기 정사각형의 갯수를 구하기 위해 드..

📂코딩테스트:CodingTest

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

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번 풀이과정) 하며 우선순위가 가장 높은 프로세스..

📂코딩테스트:CodingTest

[프로그래머스] 의상

2024.04.01

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

📂코딩테스트:CodingTest

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

2024.03.29

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

📂코딩테스트:CodingTest

이분탐색

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..

📂코딩테스트:CodingTest

visited배열이 3차원인 bfs 최단경로 탐색 문제 (백준 1600번)

2024.02.28

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있www.acmicpc.net 풀이를 위한 핵심말 이동 횟수에 따른 방문처리를 해줘야 합니다. 보통 방문체크를 visited[][] 와 같이 2차원 배열로 진행하지만, 이렇게 하게되면 말로 이동한 지점에 visited가 true로 되어 그냥 이동이 더 이상 진행하지 못하는 경우가 생길 수 있습니다. 예를들어 (0,0)에서 bfs를 수행하면 (0,1) (1,0) (1,2)가 방문체크 되고 큐에 들어갑니다. 여기서 한..

📂코딩테스트:CodingTest

이분 그래프 (백준 1707)

2024.02.22

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 풀이를 위한 아이디어 : 이분그래프의 하나의 간선에 연결된 두 노드의 색상은 서로 달라야 한다. 모든 노드에 대해 bfs를 수행하면서 연결된 노드와 서로 색상이 다른지 확인해야 한다. 변수 방문처리와 색상확인을 동시에 수행하는 int[] chk 배열을 뒀다. -1 : 아직 방문하지 않은 노드 ..

티스토리툴바