본문 바로가기

전체 글

 (24)
[프로그래머스] 퍼즐 조각 채우기 https://dev-ljw1126.tistory.com/448 각 조각과 공간을 구하는 것까지는 했으나 막힌 점 2가지로 인해 위 링크를 참고해서 풀었다. 어려웠던 점어떻게 회전을 시키지?어떻게 비교하지? 중요한 점1. 정규화“정규화”를 통해 각 공간과 조각의 좌표값을 표준화해서 비교할 수 있게 만든다.정규화 코드 및 방법방법각 X, Y값들의 최소값을 찾은 뒤, 모든 좌표값들을 각 최솟값 기준으로 빼준다. public List normalize(List data) { // 정규화 시키는 함수 // 각 모양의 중간을 (1,1) 기준으로 만들어서 다른 모양들과 쉽게 비교할 수 잉ㅆ게 한다. int minX = 51; int minY = 51; ..
[백준] 1865 웜 음의 가중치인 것을 보고 최단 거리 알고리즘 중 다익스트라와 플로이드-와샬은 사용할 수 없다는 것을 알고 벨만-포드 알고리즘을 사용해야한다는 것을 알았으나, 벨만 포드 알고리즘이 기억나지 않았다... 벨만-포드 알고리즘에 대해서도 추후 글을 올릴 예정이다. 이 문제는 단순히 벨만-포드 알고리즘을 사용해 최단 거리를 구하는 문제가 아닌, 음수 순환 발생 여부를 확인해야하는 문제다. 벨만-포드 알고리즘에 대해 간단히 적어보자면 - 한 정점에서 다른 정점들까지의 최단 거리를 구하는 알고리즘(음의 가중치에서도 동작한다.)- 매 단계마다 모든 간선을 확인하며 최단 거리를 구하는 방식이다. 특징- N번의 연산을 진행한 이후로도 최단 거리 배열의 값이 변한다면, 사이클이 존재하는 것을 의미한다.- 사이클 내에 음수 ..
[백준] 14938 서강그라운드 https://www.acmicpc.net/problem/14938 문제 요약- 특정 지역(정점)에 내렸을 때, 얻을 수 있는 최대 아이템 갯수를 구한다.- 각 아이템들을 정점에 위치해있다.- 내린 지역 기준으로 수색범위 l 이내에 있는 지역의 아이템만 가져올 수 있다. 과정 및 풀이1.  지역간 최단 거리를 구한다. => 수색 범위내에 존재하는지 확인하기 위한 용도2.  각 지점들에 내렸을 경우들에 대해IF(수색 범위 내에 존재) => 해당 지역 아이템 합산3. 2번 과정을 모든 정점들에 대해 진행해 획득할 수 있는 최대 아이템 갯수를 구한다. 알고리즘- 최단 거리를 구하는 문제이므로 대표적인 최단 거리 알고리즘인 플로이드-와샬, 다익스트라 2가지 알고리즘을 활용해 풀었다. 플로이드-와샬import j..
LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 요즘 코테를 소홀히 한 것도 있지만 부쩍 코테 난이도가 올라간 것 같다. CS 기본 공부를 하건, 면접 준비를 하건, 자소서를 쓰건,  결국 취업을 하기 위해서는 코테를 통과해야하는데 매번 떨어진다. 단순히 양치기가 아니라 효율적인 공부 방법을 마련하고 더 제대로, 본격적으로 코테를 준비해야할 것 같다. 예전에 11053번 문제를 풀 때, 참고하고 알고리즘을 공부했었는데 이보다 조금 더 난이도 높은 11054번(가장 긴 바이토닉 수열) 문제를 풀다가 알고리즘을 까먹어 내꺼로 만들고자 정리한다. https://www.acmicpc.net/problem/11053https://www.acmicpc.net/problem/11054 최장 증가 부분 수열이란(LIS)?원소 n개일 때, 일부 원소들만 골라내서 만든..
[DB] 락(Lock)이란? 트랜잭션 락(Lock)이란? 락(Lock)이란?여러 커넥션에서 동시에 동일한 자원을 요청하는 경우, 순서대로 하나의 커넥션만 접근할 수 있게 해주는 기능동시에 데이터베이스에 접근하는 상황(동시성)에서 데이터 무결성과 일관성을 지키기 위한 용도락의 종류공유 Lock(Shared Lock, Read Lock, S-Lock)배타 Lock(Exclusive Lock, Write Lock, X-Lock)공유 락(Shared Lock, Read Lock, S-Lock)읽기 작업(Read)을 위해 잠그는 락여러 사용자가 동시에 데이터를 읽어도 일관성에 영향을 주지 않기 때문에, 공유 Lock간에는 동시에 접근이 가능하다단, 다른 배타 Lock은 막는다.배타 락(Exclusive Lock, Write Lock, X-L..
Spring 관련 면접 질문 정리 추후 Spring에 대해 다시 공부하며 각 이론들에 대해 개별적으로 작성해볼 계획이다. 그러나, 큰 틀에 대해서 우선 정리할 겸 면접을 대비한 질문들을 정리해두기 위해 이 글을 작성한다.  Spring 관련 백엔드 면접 질문 ✅ 웹 서버(WS)와 웹 애플리케이션 서버(WAS)가 어떻게 다른가요?더보기웹 상에서 서비스를 제공하기 위해 사용되는 서버들이다. 웹 서버(WS)클라이언트가 웹 브라우저를 통해 요청한 정적 콘텐츠를 제공하는 역할URL을 통해 요청한 웹 페이지를 찾아 전송한다.정적 리소스 파일(HTML 페이지, 이미지, 비디오 및 파일 등)을 제공하는 서버주로 HTTP 를 사용(FTP와 SMTP도 지원)간단한 요청에 대한 응답을 제공한다Apache, Nginx, LLS 등이 있다웹 애플리케이션 서버(..
[DB] 트랜잭션이란? 스터디원들과 매주 1개 CS 주제에 대해 공부하고 정리하는 활동을 진행하고 있다. 첫번째 활동으로는 트랜젝션이란 무엇인가에 대해 진행하여 정리한다. 🗄️트랜잭션이란?DB의 상태를 변경시키는 작업의 단위한꺼번에 수행되어야 할 연산들을 모아둔 것한번에 처리하거나, 한번에 원 상태로 복구하거나🗃️ 트랜잭션의 특징(ACID)1. Atomicity(원자성)트랜잭션 내에서 진행되는 모든 연산들은 DB에 반영되거나, 전혀 반영되지 않아야한다.All or Nothing2. Consistency(일관성)트랜잭션의 작업 처리 결과는 항상 일관성 있는 DB 상태로 변환되야 한다.트랜잭션 수행 전, 후의 시스템 상태가 같아야한다는 것3. Isolation(독립성)하나의 트랜잭션이 실행될 때, 다른 트랜잭션이 끼어들 수 없..
[백준, DP] 12865 평범한 배낭 https://www.acmicpc.net/problem/12865 과거 Knapsack 문제, 즉 배낭 문제 유형을 풀었기에 보자마자 DP 문제 중 Knapsack 문제란 걸 알았다.그러나, 분명 풀었었고 공부했다고 했지만 기억이 나지 않았다. 정확히 말하면 점화식과 어떤 원리로 문제를 풀어야 하는지 기억해내지 못했다. 고로, 이번 기회에 Knapsack 까지 공부하고 정리할겸 이 글을 쓴다. 배낭 문제조합 최적화의 유명한 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져있는 경우, ‘일정 가치’와 ‘무게’가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.이런 배낭 문제는 2가지 타입이 있다.1. 분할가능 배낭문제(Fractional Knapsack P..

티스토리툴바