티스토리

글 쓰는 개발자

검색하기

블로그 홈

글 쓰는 개발자

for-development.tistory.com/m

우리로 님의 블로그입니다.

구독자: 12

방명록 방문하기

주요 글 목록

플로이드의 토끼와 거북이 알고리즘(Floyd's hare and tortoise) 증명 토끼와 거북이 알고리즘은 선형으로 이루어졌거나 링크드리스트 자료구조에서 Cycle 이 존재하는지 찾아내고 그 Cycle 의 시작지점을 알아내는데 유용하다 이 알고리즘을 요약하면 거북이는 한 번에 한 칸을 가고 토끼는 한 번에 두 칸을 보낼때 만약 Cycle 이 존재한다면 둘은 결국 만난다. Cycle 이 존재하지않는다면 토끼가 null 이 된다. 이 알고리즘을 수학적으로 증명해보자 Cycle 이 존재하지 않는 경우 토끼가 리스트의 끝으로 가서 결국 null 을 가리키게되는 건 자명하므로 생략한다. 토끼가 두 칸을 가고 거북이가 한 칸을 갈 때 둘은 무조건 만난다. 용어를 정의하자 토끼가 움직이는 거리를 h(hare 의 줄임말) 거북이가 움직이는 거리를 t(tortoise 의 줄임말) 라고 하자 그러면 h.. 공감수 0 댓글수 0 2023. 9. 5.
Leetcode 2359. Find Closest Node to Given Two Nodes - kotlin https://leetcode.com/problems/find-closest-node-to-given-two-nodes/ Find Closest Node to Given Two Nodes - LeetCode Find Closest Node to Given Two Nodes - You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a dire leetcode.com class Soluti.. 공감수 0 댓글수 0 2023. 1. 25.
leetcode snake and ladders - kotlin https://leetcode.com/problems/snakes-and-ladders Snakes and Ladders - LeetCode Snakes and Ladders - You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style [https://en.wikipedia.org/wiki/Boustrophedon] starting from the bottom left of the board (i.e. board[n - 1][0]) and alternati leetcode.com class Solution { fun snakesAndLadders(board: Arra.. 공감수 0 댓글수 0 2023. 1. 24.
Leetcode 127 Word Letter https://leetcode.com/problems/word-ladder/ Word Ladder - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Solving this, I got so many things. First, if we go BFS, we can use only one Queue. val q:Queue = LinkedList(0 while(q.isNotEmpty()){ var size = q.size() while(size--){ ... } } .. 공감수 0 댓글수 0 2022. 2. 12.
백준 2098 외판원 순회문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net import kotlin.math.min class Solution { val IMPOSSIBLE = 100000000 var nOfCity: Int = 0 lateinit var city: Array lateinit var dp: Array fun input() { nOfCity = readLine()!!.toInt() city = Array(nOfCity).. 공감수 0 댓글수 0 2022. 2. 6.
[LeetCode] 13. Roman to Integer https://leetcode.com/problems/roman-to-integer/ Roman to Integer - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이거보다 좋은 코드를 잘 모르겠다 ㅋㅋ object Solution { def romanToInt(s:String): Int = { if(s.isEmpty) 0 else if (s.startsWith("CM")) 900 + romanToInt(s.substring(2)) else if (s.star.. 공감수 1 댓글수 0 2021. 7. 10.
백준 20055 컨베이어 벨트 위의 로봇(Java) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부�� www.acmicpc.net 삼성 기출문제다.(2021년 상반기용) 주어진 조건대로 구현하면 된다! import java.io.*; import java.lang.*; import java.util.*; public class boj20055 { static int N, K, turn; static int[] conveyor; static ArrayList robots = new ArrayList().. 공감수 0 댓글수 0 2020. 10. 20.
백준 15653 구슬 탈출 4(JAVA) https://www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 면접 준비때문에 너무 바쁜걸... 간만에 한 문제 풀었다 ㅠㅠ 이 문제는 주어진 조건대로 풀면된다! 간단함! import java.io.*; import java.util.Arrays; import java.util.Objects; import java.util.StringTokenizer; public class boj15653 { static .. 공감수 0 댓글수 0 2020. 10. 17.
백준 13334 철로(JAVA) https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 끝점을 기준으로 정렬하고 우선순위 큐를 활용한다. 끝점을 기준으로 오름차순 정렬을 하면 아래 그림처럼 된다. 이 상태에서 집과 회사 중 더 작은 값을 기준으로 정렬한다. 여기서 유의해야하는게, 무조건 집이 회사보다 왼쪽에 있다고 생각하기 쉬운데 그렇지 않다. 그림으로 보자면 이렇게 두 가지 경우가 가능하다. 그러므로 입력값을 받을 때 대소 비교를.. 공감수 1 댓글수 0 2020. 10. 12.
백준 1938 통나무 옮기기 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 공감수 0 댓글수 0 2020. 10. 8.
백준 1670 정상회담 2 https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net 다이나믹 프로그래밍 문제 점화식은 f(n) = { f(n-2) * f(0) } + { f(n-4) * f(2) } + ... + { f(k - m) * f(m-2) } + ... + { f(0) * f(n-2) }다. 예를 들어서 f(4) = f(2) * f(0) + f(0) * f(2) f(6) = f(4) * f(0) + f(2) * f(2) + f(0) * f(4) 이다. 그림을 보며 이해해보자 . 여섯명짜리 악수를 대표로 살펴보자 이렇게 세 가지 경우가 나올 수 있다. 8개.. 공감수 1 댓글수 0 2020. 10. 5.
백준 1219 오민식의 고민(Java) https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착�� www.acmicpc.net 벨만 포드 알고리즘을 활용한다. 코드를 보면 이해할 수 있을 것 같다. import java.io.*; import java.util.*; public class Main { private static int N; private static int startCity; private static int arriveCity; private static int nTransport; private .. 공감수 0 댓글수 0 2020. 10. 3.
백준 9661 : 돌 게임 7 https://www.acmicpc.net/problem/9661 9661번: 돌 게임 7 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 시뮬레이션을 해보면 승패승승패가 반복되는 걸 확인할 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReade.. 공감수 0 댓글수 0 2020. 10. 2.
백준 1111 IQ Test(Java) https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 내 아이큐를 테스트하는 것 같은 문제.. arr[i+1] - arr[i]를 arr[i] - arr[i-1] 로 나누면 a를 구할 수 있다. 점화식을 세워보면 금방 알 수 있당 a를 구하면 b를 구하는 건 껌이다. A를 출력해야하는 상황과 B를 출력해야하는 상황을 잘 구별하는 게 이 문제의 핵심이다. 둘 모두 "주어진 배열의 다음 숫자"에 대한 것임을 명심하자! 만약 배열의 크기가 1이라면 그 다음에 어떤 숫자든 올 수 있다. --> A 예를 들어서 [3] 그 숫자.. 공감수 0 댓글수 0 2020. 10. 1.
백준 16946 벽 부수고 이동하기4(JAVA) https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 간만에 알고리즘을 푸려니까 잘 안된다 이 문제는 벽이 없는 구간들을 그룹화 하는게 중요하다. 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 위와 같은 인풋이 들어오면 다음과 같이 그룹화해준다. 1 10 10 1 11 1 1 12 11 11 1 12 11 11 1 12 각각을 그룹화 한 다음 Map에 그 그룹이 몇개인지 저장한다. 그룹 10 : 2 그룹 11 : .. 공감수 0 댓글수 0 2020. 9. 30.
백준 14867 물통(JAVA) https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최� www.acmicpc.net 모든 경우의 수를 탐색하는 BFS... DFS로 하면 시간초과 뜬다. import java.io.*; import java.util.*; import java.util.concurrent.LinkedBlockingDeque; public class boj14867 { static class Pair { int n ,m; Pair(int a, int .. 공감수 0 댓글수 0 2020. 9. 22.
백준 1377 버블 소트 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 버블 소트를 몇 번이나 해야하는지 출력하는 문제다. 각 원소가 정렬되기 위해 움직여야하는 최대 횟수 + 1을 출력하면 된다. 왜 + 1을 하냐면, 정렬이 끝난 후에도 한번 훑어야 하기 때문이다. import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTo.. 공감수 0 댓글수 0 2020. 9. 21.
백준 11779 최소 거리 구하기2(Java) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스� www.acmicpc.net 다익스트라 알고리즘을 활용한 문제. 최소 거리를 구하면서 각 노드의 바로 직전 노드를 저장한다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Pair im.. 공감수 0 댓글수 0 2020. 9. 17.
백준 2613 숫자구슬(자바) https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 �� www.acmicpc.net 이분탐색을 활용한 문제다. 뭔가 모든 걸 선택해야 하는 문제같은데, 백트랙킹을 쓰기에는 시간복잡도가 부담스럽다면 이분탐색이 답인 것 같다. import java.io.*; import java.util.StringTokenizer; public class boj2613 { static int N, M, upperBound, lowerBound; static int[] nArr; sta.. 공감수 2 댓글수 0 2020. 9. 16.
백준 2143 두 배열의 합(JAVA) https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 자바는 코드가 너무 길다... 이 코드 길이 볼 때마다 파이썬으로 갈아타고 싶어진다 ㅠㅠ 투 포인터를 활용한 문제 import java.io.*; import java.nio.Buffer; import java.util.ArrayList; import java.util.Collections; import java.util.. 공감수 0 댓글수 0 2020. 9. 16.
백준 2515 전시장 (java) https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 공감수 0 댓글수 0 2020. 9. 15.
백준 2632 피자 판매 https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n� www.acmicpc.net 구현하는 문제! A피자에서 나올 수 있는 모든 경우의 합을 저장하고 B피자에서 나올 수 있는 모든 경우의 합을 저장 한 후 각각의 합을 비교해가면 된다. import java.io.*; import java.lang.reflect.Array; import java.util.*; public class Main { static BufferedReader br = new Buffe.. 공감수 0 댓글수 0 2020. 9. 11.
백준 16933 벽 부수고 이동하기 3 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net -1을 까먹었다가 계속 틀린 문제 ㅠㅠㅠㅠㅠ import java.io.*; import java.util.*; class Move implements Comparable { int r, c, k, dist; boolean day; Move(int a, int b, int cc, int d, boolean day) { r = a; c = b; k = cc; di.. 공감수 0 댓글수 0 2020. 9. 10.
백준 4991 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net bfs와 dfs를 결합한 문제... 처음에 Input 때문에 아주 고생했다. 로봇청소기가 있는 위치는 소문자 o 이다. 벽은 소문자 x이다. 처음에 이걸 안했다가 아주 애먹었다. 가장 가까운 방법만 골라서 가는 그리디 알고리즘은 얼핏 생각하면 최적일 것 같지만 최적이 아닐 수 있다. 증명이 안된다. 그러므로 사용할 수 없다. 이 문제의 Input의 크기가 몹시 작기 때문에 모든 경우의 수를 무작정 계산하는.. 공감수 0 댓글수 0 2020. 9. 10.
백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 플로이드 워셜을 응용한 문제다. 어렵지않다! 대신 문제 설명이 좀 이상하다. 분명 최소 거리쌍을 주었다고 했는데... -1이 나오는 케이스는 '현재 주어진 거리쌍이 최소 거리쌍이 아닌 경우'다. 문제가 좀 이상하지 않은가 싶긴한데... 암튼 그렇다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import jav.. 공감수 0 댓글수 0 2020. 9. 8.
백준 9370 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 변형이 있다. 다익스트라 알고리즘은 분명 한 점(시작점)에서 다른 모든 점까지의 최단 거리를 구할 수 있는 알고리즘이다. 하지만 그 최단 거리의 경로 자체는 유일하지 않을 수도 있다. 그걸 잘 지적한 문제라고 생각한다. import java.awt.image.AreaAveragingScaleFilter; import java.io.*; import java.util.*; .. 공감수 0 댓글수 0 2020. 9. 8.
백준18809 Gaaaaaaarden https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 구현 문제가 그렇듯 시간과의 싸움이었다... 보통의 bfs 구현문제가 방문 체크만 요구한다면 이 문제는 구현방법에 따라 2~3가지의 방문체크를 요구한다. 여러 배열을 쓰는 게 머리 아파서 flag 값을 나눠서 풀었다. 힘들다! import java.io.*; import java.util.*; class Pair { int r, c; Pa.. 공감수 0 댓글수 0 2020. 9. 6.
백준 1053 팰린드롬 공장 https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. � www.acmicpc.net 다이나믹 프로그래밍 문제다. 즉, 점화식을 세워야 한다. dp[i][j] = i 부터 j까지의 문자열을 팰린드롬으로 만들 수 있는 최소 연산 횟수. dp[i][j] = min(dp[i+1][j] , dp[i][j-1], if(s[i] == s[j]) dp[i+1][j-1] else dp[i+1][j-2]+1) 문제는 4번 연산이다. 두 문자를 교환하는 연산을 최대 한 번 사용할 수 있는데... 언제 .. 공감수 0 댓글수 0 2020. 9. 6.
백준 1958 LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 삼중배열을 이용한 LCS 문제 요구하는 알고리즘이 선명한 문제는 상대적으로 쉬운 것 같다. import java.io.*; public class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static BufferedReader br = new BufferedReader(new InputStreamReader(System.i.. 공감수 0 댓글수 0 2020. 9. 6.
백준 14444, 13275 가장 긴 팰린드롬 부분 문자열 https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net https://www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 두 개가 같은 문제다. 자바로 풀면 시간초과뜬다. 마나허 알고리즘을 사용하는 '전형적인' 문제다. /* 가장 긴 팰린드롬 부분 문자열 */ #.. 공감수 0 댓글수 0 2020. 9. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.