mincheolsong

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

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

🥇코딩테스트:Algorithm

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)가 방문체크 되고 큐에 들어갑니다. 여기..

💎백엔드 : Backend

웹소켓

2024.02.22

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

🥇코딩테스트:Algorithm

이분 그래프 (백준 1707)

2024.02.22

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

💎백엔드 : Backend

스프링 시큐리티

2024.02.21

스프링 시큐리티의 동작 원리에 대해 공부하고 정리한 내용입니다. 전체 동작과정 필터란? 스프링 컨테이너 외부에 존재하여 스프링과 무관한 자원에 대해 동작합니다. 보통 web.xml에 등록. 인코딩 변환 처리, XSS 방어 등의 요청에 대한 처리로 사용됩니다. 인증과 인가의 차이점 인증 : 해당 사용자가 본인이 맞는지를 확인하는 절차 인가 : 인증된 사용자가 요청된 자원에 대해 접근이 가능한가를 결정하는 절치 Servlet Container와 Spring Container DelegatingFilterProxy Servlet Container와 Spring의 Spring Container를 연결해주는 필터입니다. servlet container에 존재하는 필터입니다. 필터(Filter)도 스프링에서 관리가..

전체 글

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

[프로그래머스] 의상

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

이분탐색

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

웹소켓

이분 그래프 (백준 1707)

스프링 시큐리티

티스토리툴바