mincheolsong

DFS + DP (백준 1520 내리막길)

2024.02.20

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이과정 (r,c)에서 목적지 (M-1,N-1)까지 갈 수 있는 모든 경로의 갯수는 (r,c)와 인접한 (nr,nc)에서 목적지 (M-1,N-1)까지 갈 수 있는 경로 갯수의 합이다. 위 과정을 그림으로 나타내면 아래와 같다 보통의 bottom-up 방식으로 구현하는 dp가 아니었다. 메모리제이션 방법 방문체크 배열(visited) 을 둬서 계산이 완료된 좌표의 경우 계산된 결과값을 리턴하는 방..

🥇코딩테스트:Algorithm

구현, 백트래킹 (15684 사다리 조작)

2024.02.16

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이과정 check() :i번 세로선의 결과가 i번이 나오는지 확인하는 함수 사다리 0개 놓고 check()하기 사다리 1개를 놓는 모든 경우에 대해 check()하기 사다리 2개를 놓는 모든 경우에 대해 check()하기 사다리 3개를 놓는 모든 경우에 대해 check()하기 만약 사다리 1개를 놓는 과정에서 check()==true가 된다면 사다리 2개, 3개 놓는 과정은 필요하지 않다. 왜..

🥇코딩테스트:Algorithm

백트래킹(14890 경사로)

2024.02.14

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 모든 행에 대해서 왼쪽에서 오른쪽으로 진행하며 지나갈 수 있는 길인지 확인하는 방식으로 문제를 풀었다. ✅왼쪽 블럭과의 높이 차이(gap) 계산 gap == 0 : 다음 칸으로 재귀 gap == 1 : 왼쪽 블럭에 계단을 놓을 수 있는지 확인한 후 다음 칸으로 재귀 gap == -1 : 이면 오른쪽 블럭에 계단을 놓을 수 있는지 확인한 후 계단 이후 칸으로 재귀 ✅백트래킹 종료(basecase) 조건 계단을 마지막 블럭..

🥇코딩테스트:Algorithm

BFS (백준 16234 인구이동)

2024.02.09

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이순서 0. 하루마다 NxN크기의 땅을 확인하며 국경을 허물었는지 확인 while(true){ if(!solve()){ // 국경 허물 수 있는지 확인하고 국경 허물고 인구수 갱신 break; } ans+=1; } 하루마다 (0,0)에서 bfs를 수행하며 국경을 허물고 인구를 이동시켰다. static boolean solve(){ visited = new boolean[N][N];..

🥇코딩테스트:Algorithm

두 지점이 동시에, 벽에 닿기 전 까지 움직이는 bfs (백준 13460 구슬탈출2)

2024.01.21

특이한 bfs문제 핵심 로직 1. 구슬을 동시에 움직이기 2. 벽에 닿기 직전까지 최대한 움직이기 3. 빨간 구슬과, 파란 구슬이 겹치는 경우를 처리 1. 구슬을 동시에 움직이기 빨간공과 파란공의 좌표를 같이 가지고 있는 Marble 클래스를 만들었다. class Marble{ private int redRow,redCol,blueRow,blueCol; public Marble(){} public Marble(int redRow, int redCol, int blueRow, int blueCol){ this.redRow = redRow; this.redCol = redCol; this.blueRow = blueRow; this.blueCol = blueCol; } public int getRedRow()..

🖥️컴퓨터과학:CS

[운영체제]6장. cpu스케줄링

2024.01.16

프로그램 동작순서 1. 프로그램이 시작되어 메모리에 올라감 2. PC(프로그램 카운터)라는 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지게 됨 3. CPU는 PC가 가리키는 주소의 기계어 명령을 하나씩 수행 기계어 명령 종류 cpu내에서 수행되는 명령 (예 : ADD명령) 메모리 접근을 필요로 하는 명령 (예 : Load명령, Store명령) 입출력을 동반하는 명령 1번, 2번은 비교적 빠른명령 (사용자 프로그램이 직접 cpu를 가지고 수행) 👉 CPU버스트 3번은 상대적으로 느린 명령 👉 I/O 버스트 프로그램들은 CPU버스트가 긴 경우도 있고 짧은 경우도 있고, I/O버스트가 긴 경우, 짧은 경우 있고 다양하다. 따라서 CPU 스케줄링이 필요함. CPU스케줄링의 두 가지 분류 비선점형..

📖데이터베이스:DB

SQLD

2024.01.14

1과목 발생시점에 따른 엔티티 분류 기본/키엔티티 : 다른 엔터티로부터 주식별자를 상속받지 않고 자신의 고유한 주식별자를 가지며 사원, 부서, 고객, 상품, 자재 등이 예가 될 수 있는 엔터티 중심엔티티 행위엔티티 데이터 모델링이란 정보시스템을 구축하기 위한 데이터 관점의 업무 분석 기법 현실세계의 데이터에 대해 약속된 표기법에 의해 표현하는 과정 데이터베이스를 구축하기 위한 분석/설계의 과정 데이터 모델링 유의점 중복 비유연성 : 데이터의 정의와 데이터의 사용 프로세스를 분리 비일관성 데이터모델링은 DB구축하기만을 위한 것이 아니라, 모델링 자체로서 업무를 설명하고 분석하는데 중요한 의미가 있다 개념적 데이터 모델링 : 추상화 수준이 높고 업무중심적이고 포괄적인 수준의 모델링 진행. 전사적 데이터 모델..

📖데이터베이스:DB

[MySQL] 최상위 레코드 하나 가져오기

2024.01.13

order by와 limit을 활용 SELECT name from animal_ins order by datetime limit 1;

전체 글

DFS + DP (백준 1520 내리막길)

구현, 백트래킹 (15684 사다리 조작)

백트래킹(14890 경사로)

BFS (백준 16234 인구이동)

두 지점이 동시에, 벽에 닿기 전 까지 움직이는 bfs (백준 13460 구슬탈출2)

[운영체제]6장. cpu스케줄링

SQLD

[MySQL] 최상위 레코드 하나 가져오기

티스토리툴바