전체 글

전체 글

    [java] 백준 7576 (토마토1) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 7576 (토마토1) Silver 1

    Problem : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Approach 시작점이 여러개인 최단경로 문제이다. 문제에서 배열의 요소가 1인 모든 곳이 시작점이다. (따라서 요소가 1인 모든 좌표를 큐에 넣고 BFS를 수행한다.) 벽이 -1 로 막혀있지 않고, 범위를 벗어나지 않으며, 방문하지 않았다면, 방문하면서 직전 위치의 값 + 1을 방문하는 곳에 저장한다. BFS가 완전히 모두 수행된 후, 최단경로 배열을 검사하여..

    [java] 프로그래머스 (가장 큰 수) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (가장 큰 수) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr Approach 처음엔 사전정렬을 생각했었다. 그런데 사전검색으로는 반례가 생긴다. 사전 순 정렬이면 공통된 부분이 같으면 짧은 것이 먼저다. 예를들어, 333과 33같은 경우 33이 333보다 우선이다. 그러나 문제의 요구대로라면 33, 332는 33+332가 되어야하고, 33,..

    [java] 프로그래머스 (괄호 변환) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (괄호 변환) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제이다. 딱히 접근법이 없다. 문제에 나와있는 조건들을 순서대로 구현하면 된다. 주의할 점은 4-4 의 괄호방향을 뒤집는다 이다. 단지 괄호방향만 뒤집을 뿐 문자열의 역순을 취하면 안된다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열..

    [java] 백준 2178 (미로 탐색) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2178 (미로 탐색) Silver 1

    Problem : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Approach (1, 1)에서 (n, n)까지의 최소 이동거리를 구하는 문제이다. BFS를 사용하여, 범위를 벗어나지 않고, 요소가 1이며, 방문하지 않았다면, 큐에 집어넣는 식으로 진행하였다. 방문할 곳에 직전 곳에 있는 값+1 을 저장해주면 (n, n)에 최소 비용이 저장될 것이다. BFS를 구현만 할줄 안다면, 쉬운 문제가 될 것이다. Code import java.io.*; import java.uti..

    [java] 백준 2667 (단지번호붙이기) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2667 (단지번호붙이기) Silver 1

    Problem : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Approach 보통 지도 형식의 배열이 나오면 BFS로 푸는게 더 나은 것 같다...(필자 생각) BFS, DFS 모두 풀이가 가능해도 더 좋은 풀이가 있는 문제처럼, 지도를 통한 탐색의 경우 필자는 BFS를 더 선호한다. (더 간단하기 때문 ㅎㅎ) 이 문제는 감을 익히기 위해서 두 방법 모두로 풀어봤다. 또한 이 문제는 프로그래머스에도 유사한 문제가 있다. 밑의 링크는 그 문제..

    [java] 백준 2606 (바이러스) Silver 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2606 (바이러스) Silver 3

    Problem : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net Approach 여러 노드가 있을 때, X 라는 노드와 연결된 모든 노드의 개수를 구하면 되는 문제이다. -> 따라서 순회 문제라는 것을 빠르게 알아내어, 접근해야한다. DFS, BFS 중 아무거나 사용해도 되지만, 필자는 인접리슽으를 이용한 DFS 재귀 방식으로 풀이하였다. Code import java.io.*; import java.util.*; /** * no.2606: 바이러..

    [java] 백준 1260 (DFS와 BFS) Silver 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 1260 (DFS와 BFS) Silver 2

    Problem : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net Approach BFS(Breadth-First Search), DFS(Depth-First Search) 의 기본 문제이다. 일단 BFS, DFS 가 어떤 방식으로 돌아가는지를 알아야 한다. 사전적 정의는 DFS는 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다는 방식이고..

    [java] 백준 10942 (팰린드롬) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 10942 (팰린드롬) Gold 2

    Problem : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Approach 팰린드롬은 주어진 문자열을 거꾸로해도 원래의 문자열과 같은 경우를 말한다. 일반적으로 팰린드롬은 DP 문제가 아니지만, 하나의 문자열으로 범위를 나누어 팰린드롬인지를 검사할 때에는 DP를 써서 상태를 저장한다면 시간을 조금 단축시킬 수 있다. 일단 범위 (s, e) 가 팰린드롬이라면, 시작인덱스와 끝인덱스에 같은 수를 더하고 뺀 범위는 항상 팰린드롬이다. 예를 들어, (s, e) 가 팰린드롬이면, (s..

    [java] 백준 7579 (앱) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 7579 (앱) Gold 3

    Problem : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Approach DP 문제로 냅색(KnapSack) 문제와 유사하다. N cost로 최대 몇 M size를 비활성화 할 수 있는지를 고민해서 풀어야 한다. DP[i][j] = i개의 앱이 있을 때, j cost로 비활성화 할 수 있는 최대 사이즈이다. 그런 후, X개 앱이 있을 때, Y size를 처음으로 넘기는 cost를 찾으면 된다. Code import java.io.*; impo..

    [java] 백준 1520 (내리막 길) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 1520 (내리막 길) Gold 4

    Problem : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net Approach 최단거리 문제가 아니므로 미로문제 처럼 갈 수 있는 모든 곳을 방문해 봐야 한다. DP[i][j] = (i, j) 위치에서 최종 목적지까지 갈 수 있는 방법의 수라고 정의한다. DP[i][j] == 0 은 방문했음을 표시한 것이고, -1은 도달할 수 없는 곳이다. 현재 위치를 방문 했음을 표시하고, 상하좌우로 갈 수있는지 검사하여 갈 수 있다면 재귀를 돌리면서 리턴 값..

티스토리툴바