알고리즘

[백준] 11724번 연결 요소의 개수

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net [풀이 방법] 하나의 선으로 이어진 덩어리(?)가 몇 개 있는지 구하는 문제이다. 이 문제에서 방문 순서는 영향을 미치지 않기 때문에 dfs, bfs 상관없이 탐색을 하면된다! 1. 1~N개의 정점 중 아직 방문하지 않은 정점을 시작 정점으로 탐색 시작 2. 한 번의 탐색이 끝나면 연결 요소의 개수 증가 -> 한 번의 탐색이 끝났다는것..

[백준] 2606번: 바이러스

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이 방법] 1. 키(정수) : 값(배열)을 갖는 HashMap 자료구조를 사용하여 컴퓨터의 연결을 저장 (그래프) 2. 방문한 노드는 더 이상 방문하지 않아도 되므로 방문기록을 표시 할 boolean 배열 visited를 선언 3. 연결되어 있는 컴퓨터부터 순차적으로 반복(bfs) 하기 위해 다음에 방문 할 노드를 담아 둘 Queue 자료구조 q 사용 여기서 부터 bfs 시작 ⤵ 4. 첫 시작점 1..

[백준] 17265번 나의 인생에는 수학과 함께

https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 보통의 dfs문제는 방문한 위치를 다시 방문하지 않기 위해 boolean 2차원 배열을 사용해서 방문기록을 남겼다. 하지만 이번 문제는 오른쪽과 아래로만 이동하기 때문에 따로 방문기록을 남기지 않아도 된다!! (재밌는 문제였다) [풀이 방법] 1. 우선 이때까지 지나온 길의 값들을 모두 저장할 ArrayList구조를 갖는 클래스 변수 exp 선언 2. exp에 현재 위치(집)의 값을..

[백준] 2178번 미로탐색

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 지난번에 이어 탐색문제에 도전했다!! 호기롭게 dfs로 풀었지만....실패 (시간초과 💢) [DFS 실패한 코드] import java.util.Scanner; public class Main { static int N, M, min = Integer.MAX_VALUE; static int[][] miro; static boolean[][] visited; static int[] dx = {-1, 1, 0, 0}; static ..

[백준] 14500번 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [풀이에 앞서...😮‍💨] 나는 이런 탐색문제 유형에 젬병이다(ㅠㅠ) 그래서 다른 분의 풀이코드를 이해한 뒤 내 방식대로 풀어봤다! (해당 코드가 없었다면 중요한 포인트를 절대 생각해내지 못했을꺼다 https://hanyeop.tistory.com/416 감사합니다..!) 탐색문제 풀면 재밌는데 풀기가 너무 싫어 하,,, 앞으로 당분간 풀이를 보고 풀더라도 탐색문제를 많이 풀어봐야겠다!! 마지막으..

[프로그래머스] [1차] 캐시

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3 cache에는 참조한 순서대로 city가 저장된다. (가장 최근에 참조한 city는 맨 뒤에 존재!) 2. 다음과 같은 과정을 cities배열에 돌며 반복한다. 2-1) cache에 현재 city의 값이 존재 하는 경우 -> 실행시간 1 증가 -> cache에서 가장 최근에 참조한 city는 cache의 마지막 위치에 존재해야 함 따라서 cache에서 참조한 city를 제거하고 다시 마지막 위치에 추가 2-2) cache에 현재 city의 값이 존재 하지 않는 경우 -> 실행시간 5 증가 -> cache에 city 추가 -> cache의 크기가 허용된 크기보다 크다면 cac..

[리트코드] 41. First Missing Positive

[문제 간단 설명] 시간복잡도 O(n) 이하로, 정렬되지 않은 정수 배열 nums가 주어졌을 때, nums에 존재하지 않는 가장 작은 양의 정수 구하기 [풀이 방법] 1. 주어진 nums배열 정렬 2. answer = 1로 선언 및 초기화 3. nums의 원소값들을 반복하며 answer과 값이 같을 경우 answer을 1증가, 양수이고 answer보다 큰 값을 가질 경우 반복문을 빠져나감 4. answer 반환 * 3의 조건 중 "양수이고 answer보다 큰 값을 가질 경우 반복문을 빠져나감"의 조건이 없어도 정답을 반환한다. 하지만 [1, 2, 3, 5, 6, 7]과 같은 상황에서 해당 조건을 추가하면 전체를 반복하지 않고 정답을 찾을 수 있기 때문에 시간측면에서 유리하다. [코드_Java] impor..

[프로그래머스] 오픈채팅방

풀이 방법 1. HashMap을 사용하여 아이디별 최종닉네임을 저장할 변수 nickname 선언 (HashMap은 key, value로 이루어진 자료구조) 2. record의 모든 값들을 반복하며 들어오는 경우와 닉네임을 변경하는 경우, 각 아이디별 닉네임을 갱신 3. 메세지를 작성할 ArrayList 선언 이때, 배열이 아닌 ArrayList를 사용한 이유는 나갈경우에는 메세지를 작성하지 않아 record 의 길이와 메세지가 들어갈 배열의 길이가 같지 않기 때문임 사실 변수를 사용하면 해결 될 문제지만 코드가 길어지고 가독성이 좋지 않을것으로 판단되어 ArrayList사용 4. record의 모든 값들을 반복하며 들어오는 경우와 나가는 경우, 닉네임 변수에서 키로 값을 가져와 닉네임 + 메세지를 작성 ..