문제 : 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. 두 번 이동 시키기 정사각형의 갯수를 구하기 위해 드..
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42587 풀이과정 1. 우선순위가 가장 높은 프로세스를 찾아야 합니다. 👉우선순위 큐를 활용 O(logn)하여 구할 수 있습니다. 2. 문제의 2번 조건을 구현해야 합니다. 2번 조건의 동작에서 다시 큐에 넣는 원소들의 순서는 유지됩니다. 위 그림과 같이 (2,1)은 뒤로 가야하는데 이때 뒤로 가는 (2,1)의 순서는 유지됩니다. 따라서 큐를 활용해서 구현할 필요 없이 주어진 priorities 배열들을 순서대로 무한순회(?)하면 됩니다. 3. 문제에서 요구하는 정답인 해당 프로세스가 몇 번째로 실행되는지 파악해야 합니다. 배열들을 무한순회(2번 풀이과정) 하며 우선순위가 가장 높은 프로세스..
문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42578 풀이과정 처음의 접근 : 옷 종류 별 갯수를 저장하는 배열을 생성하고, 그 배열을 백트래킹으로 탐색하며 모든 경우에 대해 계산을 진행하려 했습니다. 하지만 이렇게 하면 시간복잡도를 만족할 수 없었습니다. 새로운 접근에 대한 생각 : 진 부분집합에 대해 생각했습니다. 진 부분집합의 갯수는 2^n - 1 이므로, 이 문제에서 최악의 경우 n = 30이 되므로 처음의 접근과 같이 완전탐색을 진행하면 당연히 시간초과가 발생하는 것이었습니다. 올바른 풀이 1. 옷 종류별로 옷의 갯수를 + 1 해줘야 합니다. 여기서 +1은 (입지않음을 의미합니다) 2. +1된 옷 종류별 옷의 갯수들 끼리의..
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges 풀이과정 우선 방이 생성되는 조건에 대해 파악해야 합니다. 방이 생성되는 조건은 1. 이전에 방문했던 정점을 다시 방문해야 함 2. 이전에 연결한 선분이 아닌 새로 생긴 선분이어야 함 각 정점에 대한 그래프를 코드로 나타내는 과정이 중요하다고 생각합니다. 이때, 기존의 그래프 문제와 다르게 인접행렬이나 인접리스트로는 해당 문제를 구현할 수 없습니다. arrows의 크기가 1 이상 100,000이하라는 조건으로 인해 인접 행렬의 경우200_001 * 200_001 의 크기가 되기 때문입니다. 아래와 같이 HashMap 자료구조와 Node 클래스를 통해서 그래프를 구현할 수 있습니..
이분탐색은 크게 존재여부를 파악하는 알고리즘, 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..
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)가 방문체크 되고 큐에 들어갑니다. 여기서 한..
websocket에 대해 공부하고 정리한 글입니다. 웹소켓 통신의 시작 웹소켓 통신은 시작은 HTTP request 입니다. 이때 HTTP request 헤더에는 Connection : "Upgrade", Upgrade : "websocket"을 포함하고 있습니다. GET /spring-websocket-portfolio/portfolio HTTP/1.1 Host: localhost:8080 Upgrade: websocket Connection: Upgrade Sec-WebSocket-Key: Uc9l9TMkWGbHFD2qnFHltg== Sec-WebSocket-Protocol: v10.stomp, v11.stomp Sec-WebSocket-Version: 13 Origin: http://localhos..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 풀이를 위한 아이디어 : 이분그래프의 하나의 간선에 연결된 두 노드의 색상은 서로 달라야 한다. 모든 노드에 대해 bfs를 수행하면서 연결된 노드와 서로 색상이 다른지 확인해야 한다. 변수 방문처리와 색상확인을 동시에 수행하는 int[] chk 배열을 뒀다. -1 : 아직 방문하지 않은 노드 ..
