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

이진 검색 트리 (백준 5639번)

2023.12.28

전위순회 결과를 바탕으로 트리를 만들고, 후위순회를 출력하면 된다. 풀이 순서 1. 입력을 바탕으로 트리를 구성. (노드 클래스를 활용) 2. 노드 클래스 내부에 insert 함수 작성. insert 함수 : 입력된 노드의 값을 현재 노드 값과 비교하여, 왼쪽 혹은 오른쪽에 달아주는 함수. 이때 insert 함수에 재귀함수를 적용해야 한다. 해당 위치가 비어있으면 해당 위치에 노드를 달아주고, 비어있지 않다면 해당 위치에 있는 노드의 insert함수를 재귀호출 코드 package com.mincheolsong; import java.io.*; import java.util.*; public class Main { // BOJ 5639번 이진 검색 트리 static class Node{ int num; N..

📂코딩테스트:CodingTest

다익스트라 (백준 13549 숨바꼭질 3)

2023.12.26

다익스트라로 풀 수 있는 문제상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 해당 문제는 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 문제이다. 문제를 그래프로 바꾸는게 중요하다고 생각한다. 수빈이는 위치 X에서 -1, +1, *2 로 움직일 수 있으니까 위치 X를 노드라고 생각했을 때 X-1, X+1, X*2 를 연결된 노드, 가중치는 문제에서 주어진 (1, 1, 0) 으로 생각했다. 다익스트라 알고리즘 (우선순위큐 활용) 코드 package com.mincheolsong; import java.io.*; import java.util.*; public class Main { // boj 13549 ..

📂코딩테스트:CodingTest

트리의 지름 (백준 1167번)

2023.12.26

트리의 지름이란 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것이다. 결론 임의의 정점에서 가장 거리가 긴 노드를 찾는다. (dfs 한 번) 찾아진 노드에서 가장 거리가 긴 노드까지의 거리를 구하면 된다. (dfs한 번) (총 dfs 두 번에 트리의 지름을 찾을 수 있다) 설명 위 트리의 경우 1 - 3 - 4 - 5 가 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것) 경로가 된다. 여기서 트리의 지름이 되는 양 끝 노드는 1과 5이다. 이 때 임의의 정점에서 거리가 가장 긴 노드는 1 혹은 5를 반드시 지나게 된다. 1에서 거리가 가장 긴 경로 : 1 - 3 - 4 - 5 2에서 거리가 가장 긴 경로 : 2 - 4 - 5 3에서 거리가 가장 긴 경로 : 3 - 4 - 5 4에서 거..

📂코딩테스트:CodingTest

플로이드 워셜 알고리즘

2023.12.14

모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산함 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 다익스트라와 다르게 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음. 2차원 테이블에 최단 거리 정보를 저장 DP 유형에 속함 (점화식에 맞게 3중 FOR문을 이용해서 2차원 테이블을 갱신) 노드의 계수가 밀집그래프(완전그래프에 가까운 그래프)인 경우 플로이드 워샬 알고리즘이 효율적이다. 밀집그래프가 아닌 경우 다익스트라를 n번 돌리는게 빠르다 O(n^3)의 시간복잡도로 다익스트라(인접행렬을 사용한 경우)의 시간복잡도와 동일하다 N이 100이면 → 100만이어서 가능, 500이어도 → 1억 2천 500만 이어서 try해볼 ..

📂코딩테스트:CodingTest

백준 9465 스티커

2023.11.29

dp로 푸는 문제. 알게된 점 점화식을 세울 때 arr[r][c]를 포함하는 경우와 포함하지 않는 경우만 생각하지 말자 이번 문제는 arr[r][c]를 뽑을 수 있는 이전 위치를 고려해야 했다! dp는 최적해의 부분최적해를 생각하며 점화식을 세워야 한다. 처음 접근방식 arr[r][c] 의 스티커를 떼는 경우와 떼지 않는 경우를 고려해서 점화식을 세우려고 했다. 올바른 접근방식 arr[r][c]의 스티커를 뗄 수 있는 경우만 고려하고, arr[r][c] 스티커를 뗄 수 있는 이전 위치 (arr[1][c-1] or arr[1][c-2] 혹은 arr[0][c-1] or arr[0][c-2]) 를 부분최적해로 보는 것 이었다. 점화식 r=0인 경우 dp[r][c] = max{dp[1][c-1], dp[1][c..

📂코딩테스트:CodingTest

bfs 방문체크 위치

2023.11.22

백준 문제를 풀다 메모리 초과를 만남.. 분명 다른사람 코드와 같은데, 왜 메모리 초과가 나는지 이상했다. 이유는 bfs 방문체크 위치를 잘 못 해서 결론 : 큐에 삽입하는 순간에 방문체킹을 해서 중복을 방지하자 잘못된 방문체크 위치 (큐를 뽑는 순간 방문체크) 아래 코드는 문제에 사용된 bfs함수 일부분입니다 static boolean move(){ Queue tmp = new LinkedList(); while(!bq.isEmpty()){ int[] c = bq.poll(); int cr = c[0], cc=c[1]; if(cr==er && cc == ec){ return true; } chk[c[0]][c[1]]=true; // 방문체크 for(int d=0;d

📂코딩테스트:CodingTest

[swea 1868-파이썬] 파핑파핑 지뢰찾기

2023.06.22

사용언어 : PYTHON 풀이 1. 행 우선 방향으로 탐색을 진행하다 0인 곳을 만나면 BFS를 수행(연쇄적으로 클릭)하며 정답(ans)를 1증가 이때 0으로 인해 연쇄적으로 클릭된 곳을 -로 표시 2. 행 우선 방향으로 다시 탐색하며 연쇄적으로 클릭되지 않은 곳의 갯수만큼 정답(ans)에 추가 코드 import sys from collections import deque input = sys.stdin.readline # SWEA 파핑파핑 지뢰찾기 # 1. 전체를 탐색하다 0을 만나면 BFS 수행 (방문체크), cnt += 1 # 2. 체크 되지 않은 칸 세기 def click(r, c): # 클릭을 수행하고(중복 클릭은 수행하지 않음), 0이면 True를 리턴하는 함수 if arr[r][c] == '..

📂코딩테스트:CodingTest

[swea 3304-파이썬]최장 공통 부분 수열

2023.06.21

swea 3304 최장 공통 부분 수열 사용언어 : PYTHON 풀이 우선 최적해(최댓값)을 구하는 문제이기 때문에 다이나믹 프로그래밍을 사용하여 풀 수 있다. 순환식(점화식)을 세울때는 "최적해의 일부분이 그 부분의 최적해" 를 생각해야 한다. 이 문제 같은 경우는 두 문자열의 마지막 문자가 같은 경우와 다른 경우를 생각하여 순환식을 세워야 한다. (DP(i,j)에서 i와 j는 문자열 X와 Y의 1...i, 1...j 번째까지의 문자열) (1) 두 문자열의 마지막 문자가 같은 경우 예를들어 CDABE와 CDE라고 가정해보면 마지막 문자 E가 같다. E는 최장 공통 부분수열에 반드시 포함된다. 따라서 최장 공통 부분수열의 길이는 두 문자열의 마지막 문자 E를 제거한 후 찾은 최장 공통 부분수열의 길이 +..

티스토리툴바