본문 바로가기

분류 전체보기155

[알고리즘] 백트래킹이란? & 대표 문제: 백준 15679 N과M(1) - 자바 ✔️ 백트래킹이란?백트래킹이란?해를 찾는 도중에 막히면 더이상 탐색하지 않고, 이전 단계로 되돌아가서(재귀) 해를 찾아나가는 기법을 의미한다. 백트래킹은 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 이처럼 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning) 이라고 한다.  따라서, 백트래킹은 모든 노드를 DFS를 통해 탐색하면서 더 이상 필요가 없는 부분을 쳐내는 가지치기(pruning)를 하는 것이다.  DFS 완전탐색으로 경우의 수를 찾아야할 경우, 불필요한 탐색을 건너뛸 여지가 있다면 백트래킹을 이용할 수 있다. .. 2024. 10. 1.
[백준] 7576 토마토 : 자바 BFS [골드5] ✔️ 문제 설명 (펼치기)더보기문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 .. 2024. 10. 1.
[백준] 1600 말이 되고픈 원숭이 : 자바 BFS [골드 5] ✔️ 문제 설명 (펼치기)더보기문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x   x  말  x   x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.이제 원숭이는.. 2024. 9. 29.
[백준] 15486 퇴사2 (자바) : DP [골드 5] ✔️ 문제 설명 (펼치기) 더보기더보기문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.35112421020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 .. 2024. 9. 17.
[CS 스터디 질문] 컴파일(Compile), 런타임(Runtime) ✔️ 컴파일(Compile) 이란?컴파일(compile)은 개발자가 프로그램을 위해 작성한 소스 코드를 다른 프로그램 또는 기계(Hardware)가 처리하기 용이한 형태로 바꾸는 과정을 의미한다.  컴파일 언어에는 Java, C, C++ 등이 있으며, 실행(런타임)되기 위해서는 반드시 컴파일(Compile) 과정을 거쳐야한다. C, C++ 컴파일러에서는 기계어로 번역된 실행 파일(예: .exe 파일)이 생성된다.자바 같은 경우는 소스 코드가 바이트코드로 변환되어 .class 파일로 저장된다. 반면에, JavaScript, Php, Python 같은 언어들은 스크립트 언어이며 컴파일 과정없이 기계어로 번역되는 즉시 동작된다. 컴파일을 진행하는 일련의 과정을 컴파일 타임이라고 한다.언제 발생?: 프로그램 실.. 2024. 9. 12.
[CS 스터디 질문] 자바의 메모리 & 변수 ✔️ 자바의 메모리 모델 java.exe가 실행되면 자바 가상 머신이 만들어진다. 이때 자바는 메모리 공간의 효율성을 높이기 위해 자바의 사용에 맞게 메모리 공간을 여러 영역으로 나눈다. 자바 프로그램이 확보한 메모리 영역은 크게 메서드(method) 영역, 스택(stack) 영역, 힙(heap) 영역 으로 구분하여 사용한다. ➕ 메서드(Method) 영역 = Static 영역 - 모든 스레드가 공유해서 사용하는 영역프로그램 실행에 대한 코드, 정적(static) 변수 및 메서드, 생성자, 런타임 상수 풀 등이 메서드 영역에 생성된다. 런타임 상수 풀 : 리터럴 상수나 메서드 및 필드 참조 등의 정보가 저장되는 테이블프로그램 시작 전에 로드되고 프로그램 종료 시 소멸된다. JVM에 의해 하나만 존재하며,.. 2024. 9. 5.

티스토리툴바