'📂코딩테스트:CodingTest' 카테고리의 글 목록 (4 Page)

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) 을 둬서 계산이 완료된 좌표의 경우 계산된 결과값을 리턴하는 방..

📂코딩테스트:CodingTest

구현, 백트래킹 (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개 놓는 과정은 필요하지 않다. 왜..

📂코딩테스트:CodingTest

백트래킹(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) 조건 계단을 마지막 블럭..

📂코딩테스트:CodingTest

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

📂코딩테스트:CodingTest

두 지점이 동시에, 벽에 닿기 전 까지 움직이는 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()..

📂코딩테스트:CodingTest

벨만 포드 알고리즘

2024.01.12

간선 중심 알고리즘 👉 그래프들을 에지 리스트로 구현 음수 간선이 포함된 상황에서의 최단 거리 문제에 사용. 음수 간선의 순환을 감지할 수 있음. 매번 모든 간선을 전부 확인 최단 거리 리스트에서 업데이트 반복 횟수는 V - 1 시간복잡도 : O(VE), 다익스트 알고리즘에 비해 느리다 음수간선이 있어도 순환이 발생하지 않는다면 최단거리를 계산할 수 있다. (음수간선의 순환이 발생하면 최단거리가 음의 무한인 노드가 발생하게 됨) 동작원리 1. 출발 노드를 설정 2. 최단 거리 테이블을 초기화 3. 다음의 과정을 N-1 번 반복 3-1. 전체 간선 E개를 하나씩 확인 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신 4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3..

📂코딩테스트:CodingTest

서로소 집합 자료구조 (Union Find) (백준 1043번)

2024.01.03

더보기 [Gold IV] 거짓말 - 1043 문제 링크 성능 요약 메모리: 14352 KB, 시간: 128 ms 분류 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 3일 16:32:22 문제 설명 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 ..

📂코딩테스트:CodingTest

다익스트라 (boj 12851 숨바꼭질2)

2024.01.02

문제 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 기존의 숨바꼭질 문제에서 최단경로의 갯수까지 구해야 한다. 1. 목적지에 도달하면 함수를 종료하는 것이 아닌 계속 탐색을 이어나가도록 함수를 구성했다. while(!pq.isEmpty()){ Node cur = pq.poll(); if(cur.idx==K && cur.w==dist[K]){ // 목표지점에 도달한 경우 count+=1; } ... } ..

티스토리툴바