Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- api 요청 수 제한
- AWS
- oauth
- 프로그래머스
- 파일 url
- Dev-Matching
- bucket4j
- TypeORM
- Deep Dive
- 유효시간 설정 url
- 자바스크립트
- 프리코스
- 우아한 테크코스
- concurrency limit
- 우아한테크코스
- invalid_grant
- 음악 url 파일 다운로드
- compateto
- NestJS
- this
- 프론트엔드 과제
- 스프링부트
- 코멘토 #코멘토실무PT #실무PT후기 #실무강의 #리액트강의 #웹프로그래밍 #react #웹개발실무
- api 비동기처리
- 프론트엔드
- 검색
- 딥다이브
- redis
- 타입스크립트
- 모던 자바스크립트
Archives
- Today
- Total
개발 알다가도 모르겠네요
삼성 SDS 대학생 알고리즘 특강 1일차 - DFS&BFS 본문
728x90
항상 구현 전에 주석처리하고 시작 할 것.
DFS와 BFS를 구분 짓는 가장 중요한 점 "동시성"
동시에 무언가를 해야한다? BFS!
DFS
방문'한'게 스택에 들어감
1.체크인(방문)
2.목적지인가?
3.연결된 곳을 순회
4.갈 수 있는가?
5.간다.
6.체크아웃
항상 1,6의 뎁스 맞추는 것을 명심해야 한다. 그래야 스택오버플로우 실수를 예방할 수 있음.
BFS
방문'할'게 큐에 들어감
1.큐에서 꺼내옴
2.목적지인가?
3.연결된 곳을 순회
4.갈 수 있는가?
5.체크인
6.큐에 넣음.
1062번: 가르침
import java.util.Scanner;
public class Main {
static int N, K;
static String[] words;
static boolean[] visited = new boolean[26];
static int selectedCount = 0;
static int max = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
words = new String[N];
visited['a' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;
visited['i' - 'a'] = true;
visited['c' - 'a'] = true;
if(K == 26){
System.out.println(N);
} else if(K<5){
System.out.println(0);
} else {
for (int i = 0; i < N; i++) {
String str = sc.next();
//words[i] = str.substring(4,str.length()-4);
words[i] = str.replaceAll("[antic]", "");
}
selectedCount = 5;
max = countWords();
for (int i = 0; i < 26; i++) {
if (visited[i] == false) {
dfs(i);
}
}
System.out.println(max);
}
}
static void dfs(int index){
// 1.체크인(방문)
visited[index] = true;
selectedCount++;
// 2.목적지인가?: selectedCount == K => 읽을 수 있는 단어 개수 계산
if(selectedCount == K){
//계산
max = Math.max(max,countWords());
} else {
// 3.연결된 곳을 순회 : index + 1 ~ 25
for(int i=index+1; i<=25; i++){
// 4.갈 수 있는가? : 방문 여부
if(visited[i]==false){
// 5.간다. : dfs()
dfs(i);
}
}
}
// 6.체크아웃
visited[index] = false;
selectedCount--;
}
static int countWords(){
int count = 0;
for(int n=0; n<N; n++){
boolean isPossible = true;
String word = words[n];
for(int i=0; i<word.length(); i++){
if(visited[word.charAt(i) - 'a']==false) {
isPossible = false;
break;
}
}
if(isPossible){
count++;
}
}
return count;
}
}
1759번: 암호 만들기
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int L, C;
static char[] data;
static List<String> result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
L = sc.nextInt();
C = sc.nextInt();
data = new char[C];
result = new LinkedList<>();
for (int i = 0; i < C; i++) {
data[i] = sc.next().charAt(0);
}
Arrays.sort(data);
dfs(0,0,0,-1,"");
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
static void dfs(int length, int ja, int mo, int current, String pwd){
// 1.체크인 - 생략 가능
// 2.목적지인가?: length == L => ja 개수, mo 개수 확인 암호 가능 판별
if(length == L){
if(ja>=2 && mo>=1){
result.add(pwd);
}
} else {
// 3.연결된 곳을 순회 : current +1 ~ C
for(int i= current +1; i<C; i++){
// 4.갈 수 있는가? : 정렬했기 때문에 다 갈 수 있음
// 5.간다 -> ja, mo
if(data[i]=='a' || data[i]=='e' || data[i]=='i' || data[i]=='o' || data[i]=='u'){
dfs(length+1, ja, mo+1, i, pwd+data[i]);
} else {
dfs(length+1, ja+1, mo, i, pwd+data[i]);
}
}
}
// 6.체크아웃 - 생략 가능
}
}
3055: 탈출
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Node {
int x;
int y;
int type;
public Node(int y, int x, int type){
this.y = y;
this.x = x;
this.type = type;
}
}
// 좌, 우, 위, 아래
static final int[] dx = {-1, 1, 0, 0};
static final int[] dy = {0, 0, -1, 1};
static int R, C;
static char[][] map;
static int[][] dp;
static Queue<Node> queue;
static boolean foundAnswer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
map = new char[R][C];
dp = new int[R][C];
queue = new LinkedList<>();
Node st = null;
for (int r = 0; r < R; r++) {
String str = sc.next();
for (int c = 0; c < C; c++) {
map[r][c] = str.charAt(c);
//물 먼저 넣음. 전제조건에서 다음 턴에 물이 번질 가능성이 있는 위치에는 고슴도치가 이동할 수 없기 때문에
//물이 먼저 범람하도록 하여 이를 쉽게 해결.
if (map[r][c] == '*') {
queue.add(new Node(r, c, '*'));
} else if (map[r][c] == 'S') {
st = new Node(r, c, 'S');
}
}
}
queue.add(st);
while (!queue.isEmpty()) {
// 1.큐에서 꺼내옴(큐에는 이동할 곳이 들어감) -> *, s, ., D
Node n = queue.poll();
// 2.목적지인가? -> D
if (n.type == 'D') {
//답 출력
System.out.println(dp[n.y][n.x]);
foundAnswer = true;
break;
}
// 3.연결된 곳을 순회 -> 좌우위아래
for (int i = 0; i < 4; i++) {
int ty = n.y + dy[i];
int tx = n.x + dx[i];
// 4.갈 수 있는가? (공통) : 맵 안에 들어오는가
if (0 <= ty && ty < R && 0 <= tx && tx < C) {
if (n.type == 'S' || n.type == '.') {
// 4.갈 수 있는가? (도슴도치) : . or D, 방문하지 않은 곳
if ((map[ty][tx] == '.' || map[ty][tx] == 'D') && dp[ty][tx] == 0) {
// 5.체크인 (고슴도치) : dp[][] = 이동거리
dp[ty][tx] = dp[n.y][n.x] + 1;
//6. 큐에 넣음
queue.add(new Node(ty, tx, map[ty][tx]));
}
} else if (n.type == '*') {
// 4.갈 수 있는가? (물) : . (물은 지나가면 알아서 방문체크됨) *물은 S도 방문가능.
if (map[ty][tx] == '.' || map[ty][tx] == 'S') {
// 5.체크인 (물) : map[][] = *
map[ty][tx] = '*';
// 6.큐에 넣음
queue.add(new Node(ty, tx, '*'));
}
}
}
}
}
if(foundAnswer){
} else {
System.out.println("KAKTUS");
}
}
}
'학습일지 > 삼성 SDS 알고리즘 특강' 카테고리의 다른 글
삼성 SDS 대학생 알고리즘 특강 6일차 - 그래프 (0) | 2022.07.25 |
---|---|
삼성 SDS 대학생 알고리즘 특강 5일차 - 조합론 (0) | 2022.07.22 |
삼성 SDS 대학생 알고리즘 특강 4일차 - 트라이 트리, 정수론 (0) | 2022.07.21 |
삼성 SDS 대학생 알고리즘 특강 3일차 - 자료구조 (0) | 2022.07.20 |
삼성 SDS 대학생 알고리즘 특강 2일차 - 정렬 (0) | 2022.07.19 |