'알고리즘, 자료구조/백준' 카테고리의 글 목록

[백준] 14226. 이모티콘 (Kotlin)

문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 0. 문제 해석 1초에 걸쳐 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 3가지 연산 중 하나를 할 수 있다. 일단 시간의 최솟값을 구하는 문제이므로 3가지 연산에 대한 BFS를 사용한다. 여기서 방문처리를 어떻게 해야하는지가 문제인데, 예를 들어 4의 경우 1 - 2 - 3 ..

알고리즘, 자료구조/백준 2022. 5. 17. 14:55

[백준] 13023. ABCDE (Java)

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 0. 문제 해석 DFS로 깊이를 체크하면 풀 수 있는 문제이다. 인접 리스트로 친구 관계를 생성한다. (양방향) 0번부터 N-1번 사람을 시작으로 하여 DFS 탐색을 진행한다. DFS가 4번이상 진행되었다면 조건을 만족하므로 1 리턴 모든 DFS가 종료되었을 때 4번 이상 진행된 탐색이 없으면 0 리턴 1. 전체 코드 // [백준] 13023. ABCDE (Java) import java.io.BufferedReader; import java.io.IOException; import java..

알고리즘, 자료구조/백준 2022. 5. 15. 19:36

[백준] 14500. 테트로미노 (Java)

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 0. 문제 해석 완전 탐색에서 약간 변형하여 풀 수 있는 문제이다. 5가지 형태의 테트로미노를 잘 보면 상하좌우 완전 탐색으로 1,2,3,4번의 형태는 만들 수 있는 것을 확인할 수 있다. 따라서 회전한 형태의 경우도 완전 탐색으로 전부 구해진다. 문제는 5번 테트로미노인데 위와 같이 탐색의 2번째 칸에서 양쪽으로 하나씩 움직여야 만들 수 있는 형태이기 때문에 상하좌우 탐색으로는 결과를..

알고리즘, 자료구조/백준 2022. 5. 2. 11:00

[백준] 2206. 벽 부수고 이동하기 (Kotlin)

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 0. 문제 해석 일단 가중치가 없는 최단경로를 구하는 문제이므로 BFS를 사용해야 한다. 이제 벽을 한 개까지 부술 수 있다는 조건을 어떻게 활용해야 할지 고민해보아야 하는데 일반적인 BFS 처럼 방문처리를 하게 되면 벽을 부수고 방문한 곳인지, 부수지 않고 방문한 것인지 확인할 수 없다. 따라서 방문배열을 3차원으로 선언하여 두 개의 공간을 만들어줘서 각각 체..

알고리즘, 자료구조/백준 2022. 4. 21. 11:05

[백준] 1149. RGB거리 (Kotlin)

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 0. 문제 해석 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 위 조건을 요약하면 인접한 집과 다른 색으로 칠해야 한다는 뜻이다. 여기서 DP를 사용할 수 있는데 1번째 집부터 n번째 집까지 탐색하면서 현재 위치의 집..

알고리즘, 자료구조/백준 2022. 4. 17. 21:42

[백준] 7562. 나이트의 이동 (Kotlin)

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 0. 문제 해석 위와 같이 8방향에 대하여 BFS 탐색을 진행하면서 목적지에 도달하면 즉시 bfs의 레벨을 리턴한다. 2021.03.21 - [알고리즘, 자료구조/기본] - [알고리즘] 코틀린 BFS(너비우선탐색) 의 level 구하기 [알고리즘] 코틀린 BFS(너비우선탐색) 의 level 구하기 BFS는 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법..

알고리즘, 자료구조/백준 2022. 4. 6. 23:06

[백준] 6593. 상범 빌딩 (Java)

문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 0. 문제 해석 3차원 BFS로 풀면 어렵지 않게 풀 수 있는 문제이다. 처음엔 DFS로 접근했다가 시간초과가 발생하였다. 최단거리 문제이므로 최단거리를 찾았을 때 바로 종료할 수 있는 BFS가 유리하다. 1. 전체 코드 // [백준] 6593. 상범 빌딩 (Java) import java.io.BufferedReader; import java.io.IOException; import jav..

알고리즘, 자료구조/백준 2022. 4. 2. 23:47

[백준] 1922. 네트워크 연결 (Java)

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 0. 문제 해석 2022.02.23 - [알고리즘, 자료구조/기본] - [알고리즘] 자바 최소 신장 트리(MST) 구하기 - 크루스칼, 프림 알고리즘 (백준 1197) [알고리즘] 자바 최소 신장 트리(MST) 구하기 - 크루스칼, 프림 알고리즘 (백준 1197) 최소 신장 트리란? ▶ 그래프의 모든 정점을 사이클 없이 잇는(신장 트리)트리에서 간선의 가중치의 합이 최소가 되는 트리 크루스칼 알고리즘이란? ▶ 간선 중심으로 최소 신장 트리를 구하는 hanyeop.tistory..

알고리즘, 자료구조/백준 2022. 3. 31. 12:29

[백준] 12904. A와 B (Kotlin)

문제 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 0. 문제 해석 처음에는 재귀 방식으로 2가지 케이스에 대해 계속 탐색하도록 풀었는데 시간초과가 발생하였다. 그래서 모든 케이스를 탐색하는 것이 아닌 , 사다리타기를 할때 목적지에서 역순으로 탐색하는 것 처럼 해결하였다. 약간의 발상전환만 하면 쉽게 풀 수 있는 문제이다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 두 가지 ..

알고리즘, 자료구조/백준 2022. 3. 27. 22:59

[백준] 2661. 좋은수열 (Kotlin)

문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 0. 문제 해석 최솟값을 찾아야하므로 1,2,3 순서로 계속 넣어가면서 나쁜 수열일 경우 리턴한다. 길이가 n에 도달했는데 좋은 수열일 경우 그게 최솟값이다. 나쁜수열 판별을 위해 문자열 길이가 홀수/짝수만 신경써주면되는데 예를들어 12345678 이 있으면 (예시이므로 123이 아닌 수도 넣음) 1234 5678 0~3/4~7 345 678 2~4/5~7 56 78 4~5/6~7 7 8 6 / 7..

알고리즘, 자료구조/백준 2022. 3. 24. 21:19

경험의 기록