Algorithm

    [Java] 프로그래머스 (거리두기 확인하기) Level 2
    Algorithm/Programmers

    [Java] 프로그래머스 (거리두기 확인하기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr Approach Greedy 한 BFS 문제이다. 2021 카카오 채용연..

    [Java] 프로그래머스 (게임 맵 최단거리) Level 2
    Algorithm/Programmers

    [Java] 프로그래머스 (게임 맵 최단거리) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr Approach 아주 기본적인 BFS 문제이다. BFS를 구현할 줄 안다면 풀 수 있는 문제이다. 추가적인 스킬은 필요하지 않은 것 같다. Code import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; impo..

    [Java] 프로그래머스 (다단계 칫솔 판매) Dev-Matching 3
    Algorithm/Programmers

    [Java] 프로그래머스 (다단계 칫솔 판매) Dev-Matching 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr Approach 트리 를 구성할 수 있는지, 특정 노드를 시작으로 부모 노드들을 순회할 수 있는지가 핵심인 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 트리를 구성하는 전처리 과정이 필요하다. 이 과정에서 트리를 구성함은 물론, 현재 노드 i에 대하여 부모 노드가 무엇인지도 저장해주어야 한다. 각 seller에 대하여 반복문을 돌린다..

    [Java] 프로그래머스 (행렬 테두리 회전하기) Dev-Matching 2
    Algorithm/Programmers

    [Java] 프로그래머스 (행렬 테두리 회전하기) Dev-Matching 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr Approach 행렬의 특정 부분을 회전시킴과 동시에, 그 영역에 있는 최솟값을 찾는 문제이다. 행렬 회전을 구현할 수 있어야 한다. 행렬 회전만 구현할 줄 안다면, 약간의 조건을 걸어 쉽게 풀이가 가능하다. 문제 풀이의 주요 로직은 아래와 같다. 좌상단과 우하단의 위치를 찾고, 그 영역의 테두리 부분을 시계방향 90도 회전 ..

    [Java] 프로그래머스 (로또의 최고 순위와 최저 순위) Dev-Matching 1
    Algorithm/Programmers

    [Java] 프로그래머스 (로또의 최고 순위와 최저 순위) Dev-Matching 1

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr Approach 먼저 주어진 입력에서 0의 개수를 센다. 최고 순위는 0이 모두 당첨번호와 같다는 것을 가정하여 계산하고, 최저 순위는 0이 모두 당첨번호와 다르다는 것을 가정하여 계산한다. 그리고 난 뒤, 일치하는 번호의 개수를 가지고 등수를 계산하여 반환하면 되는 간단한 문제이다. Code im..

    [Java] 백준 정규표현식(Regular Expression) 문제 모음 및 풀이
    Algorithm/Baekjoon Online Judge

    [Java] 백준 정규표현식(Regular Expression) 문제 모음 및 풀이

    Problem 15881: Pen Pineapple Apple Pen (Bronze 2) code: https://github.com/PaengE/AlgorithmPractice/blob/master/BaekJoon_java/src/BOJ15881.java Problem 10173: 니모를 찾아서 (Bronze 2) 10173번: 니모를 찾아서 여러 문장이 각 줄로 입력되며, 입력의 마지막에는 "EOI" 입력된다. 한 줄은 최대 80개의 글자로 이루어져 있다. www.acmicpc.net code: https://github.com/PaengE/AlgorithmPractice/blob/master/BaekJoon_java/src/BOJ10173.java Problem 1264: 모음의 개수 (Bronze..

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 18809 (Gaaaaaaaaaarden) Gold 2

    Problem : https://www.acmicpc.net/problem/18809 Approach 조합을 이용한 BruteForce 와 BFS + 구현 이 필요한 문제이다. 천천히 생각하고 필요한 부분을 캡슐화하여 메소드를 작성하면 된다. 코드에 사용된 변수 설명은 다음과 같다. availableLands: 배양액을 뿌릴 수 있는 Land를 저장한 리스트 selectedAvailableLands: availableLands에서 g + r개의 Land 를 뽑는 조합에 이용할 boolean 배열 selectedLands: 배양액을 뿌릴 곳으로 선택된 g + r 크기의 배열 selectedGreen: selectedLands 중 초록색 배양액을 뿌릴 곳으로 선택한 boolean 배열 time: 해당 영역에..

    [Java] 백준 3197 (백조의 호수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3197 (백조의 호수) Gold 1

    Problem : https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net Approach BinarySearch 를 이용한 BFS + 구현 문제였다. 먼저, 얼음이 며칠 뒤에 녹는지에 대한 전처리가 필요하다. (코드에서는 iceberg라고 표현했다.) 얼음에 대한 전처리는 다음 과정으로 처리하였다. findIcebergNearWater(): 물과 인접한 얼음들을 구하였다. icebergsNearWater 큐 : 이 변수는 ..

    [Java] 백준 17071 (숨바꼭질 5) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17071 (숨바꼭질 5) Gold 1

    Problem : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net Approach 숨바꼭질 시리즈에서 동생이 움직인 버전 이다. 일반적인 BFS로는 시간초과(TLE)가 발생한다. 규칙을 찾아 시간을 단축시켜야 한다. 처음엔 일반적인 BFS를 하여 시간초과를 받았다. 시간초과 코드 또한 아래에 기록했다. 규칙은 다음과 같다. 수빈이가 A초에 X지점을 도착했다고 한다면, A+2초에도 X지점을 도착할 수 있다. ..

    [Java] 백준 16920 (확장 게임) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16920 (확장 게임) Gold 2

    Problem : https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net Approach BFS + 구현이 필요한 문제이다. 먼저 사용된 변수 설명을 하겠다. starts[i] : 플레이어 i 의 BFS 시작점들. s[i] : 플레이어 i 가 한번에 이동할 수 있는 거리. visited[i][j] : (i, j) 위치를 방문했는지를 표시. cnt[i] : 플레이어 i 의 땅 개수. 위 변수들을 사용한 문제 풀이 주요 로직은 다음과 같다. 플레이어의 ..

티스토리툴바