본문 바로가기

분류 전체보기

 (386)
[boj] 백준 gold5 14567 선수 과목 (Java) - dp [문제] https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [풀이] 과목 별 진입차수를 계산하여 진입 차수가 0이면 dp[i]에 1을 저장한다. 이는 선수과목이 없으므로 1학기 째에 바로 들을 수 있음을 의미한다. dp[i] = k는 i번 과목을 이수하기 위해 필요한 최소 학기를 저장한다. 만약 5번 과목의 선수관계가 1 - 3 - 5, 4 - 5 두 가지 존재한다면 5번 과목을 이수하기 위한 최소 학기는 3학기이다. 즉, 1~n번까지 과목을 순회하며 i번 과목을 선수 과..
[boj] 백준 gold5 5557 1학년 (Java) - dp [문제] https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net [풀이] dfs로 풀게 되면 O(2^n)의 시간복잡도를 갖게 된다. dp를 통해 해결할 수 있는데 이전의 수에 현재 수를 +하거나 - 하는 2가지 경우가 존재한다. 또한 수가 0~20 사이에 존재해야 한다. 따라서 dp[i][num] 은 0~i 번까지의 수를 차례로 더하거나 빼서 num을 만들 수 있는 경우의 수로 두고 풀 수 있다. [코드] package dp; import ja..
[pro] 프로그래머스 level2 42885 구명보트 (Java) - 투포인터 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제를 제대로 읽으세요.. 구명보트는 작아서 최대 2명!!! 밖에 탈 수 없다. 따라서 정렬해준 후 가장 무거운 사람과 가장 가벼운 사람의 무게 합이 limit 이내라면 구명보트 수 증가 후 인덱스를 둘 다 이동시켜주고, 아니라면 무거운 사람 혼자 타야하므로 구명보트 수 증가 후 무거운 사람을 가리키는 인덱스만 감소시켜준다. [코드] import java.util.*; class..
[sof] 소프티어 <인증평가(6차) 기출> 출퇴근길 - DFS [문제] https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_174270&psProblemId=1529 https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=1529&submissionSn=SW_PRBL_SBMS_174270 softeer.ai [풀이] 이 문제의 핵심은 역방향 간선 그래프를 이용하는 것이다. 출근길과 퇴근길에 모두 포함될 수 있는 정점을 구해야 한다. 이를 위해 집 s를 시작점으로 dfs를 한 번 돌리면 s와 연결되어있는 모든 정점을 구할 수 있다. 주의할 점은 출근길 경로에 회사 t는 한번만 등장한다. 즉 t에 도달하면 dfs를 멈춘다. 이제 s와 ..
[pro] 프로그래머스 level3 1833 캠핑 (Java) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/1833?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 먼저 데이터를 정렬해준 후 모든 쐐기 쌍들에 대해서 텐트를 설치할 수 있는지 비교해준다. 직사각형의 넓이가 0이면 텐트를 설치할 수 없으며(같은 r이나 같은 c값을 갖는 경우), 내부에 다른 쐐기가 있다면 텐트를 설치할 수 없다. [코드] import java.util.*; class Solution { public int solution(int n, in..
[pro] 프로그래머스 level2 178870 연속된 부분 수열의 합 (c++) - 투포인터 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 투포인터를 이용해 풀 수 있다. 처음 low와 high 인덱스는 모두 0을 가리킨다. 배열을 누적해서 더해가며 sum이 k보다 작으면 high를 증가시켜 더하고, 커지면 현재 low가 가리키고 있는 값을 뺀 후 low를 증가시킨다. sum과 k가 같다면 더 짧은 부분 수열을 선택할 것이므로 길이를 비교해서 더 짧은 경우 갱신해준다. [코드] #includ..
[boj] 백준 21611 마법사 상어와 블리자드 (Java) - 시뮬레이션 [문제] [풀이] 오늘 하루종일 마법사 상어와 복제 디버깅만 하다가 끝나는 줄.. (어디서 막혔는지 알고 신나서 고쳐서 예제 다 돌아가길래 맘편히 자나 했는데 시간초과 떠서 던짐) 이 문제의 키포인트는 1~n*n-1 까지의 달팽이 수열에 대해 미리 r, c 좌표를 저장해두고 사용하면 된다는 거다. 이 수열은 마법사 상어와 토네이도 문제에서 나온 것과 똑같이 구현해줬다. 1. di, si 방향으로 얼음을 날려서 구슬을 파괴한다. 이때 파괴된 구슬은 폭발한 구슬이 아니라 세면 안된다. 2. 구슬이 빈칸을 채우기 위해 이동한다. 3. 4개 이상 연속하는 구슬이 폭발한다. 4. 다시 구슬이 빈칸을 채우기 위해 이동한다. 더이상 폭발하는 구슬이 없을 때까지 2-3을 반복한다. 5. 구슬이 변화한다. 연속하는 구슬..
[boj] 백준 20055 컨베이어 벨트 위의 로봇 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net [풀이] 단순 시뮬레이션. 하라는 순서대로 구현하면 된다. 딱히 설명할 게 없다.. 편의를 위해 컨베이어 벨트 내구도를 저장하는 배열과 로봇 위치를 저장하는 배열을 따로 뒀는데 컨베이어 벨트 회전할 때 로봇 위치도 변경하는 거 잊지 않도록 주의! [코드] package 시뮬레이션; import java.io.*; import java.util.*; public cla..

티스토리툴바