본문 바로가기
728x90

알고리즘

 (72)
[프로그래머스] lv1 달리기 경주 java [해시][엄탱] 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" ..
[백준] 2309번 일곱 난쟁이 java [브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 설명 백설공주는 일곱 난쟁이와 같이 사는데, 어디 갔다 오니 두 명이 추가되어 아홉 난쟁이가 되었다. 여기서 진짜 일곱 난쟁이를 찾는 문제다. 단, 진짜 일곱 난쟁이 키의 합은 100이다. 해설 단순하게 아홉 난쟁이 키에서 두명을 뺐을 경우 키의 합이 100이 되는 경우를 찾아서 일곱 명의 키를 출력하면 된다. 여기서 두명의 난쟁이를 찾을 때 브루트포스 알고리즘을 사용하면 된다. 코드 im..
[백준] 14502번 연구소 java[브루트포스, 탐색][엄탱] 문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 백준 14502번 연구소 문제는 두 가지만 어떤 방식으로 풀지 알면 그 뒤로는 금방 풀 수 있다. 3개의 벽을 어떻게 설치할지, 바이러스 퍼지는 영역을 어떻게 찾을지만 생각해보고 코드를 보면 이해하기 쉽다. 브루트포스 알고리즘(직접구현 또는 DFS): 3개의 벽을 설치할 때 사용 너비 우선 탐색(BFS): 바이러스가 퍼지는 영역을 찾는 데 사용 시간복잡도를 생각해보자 지도의 최대 크기 =..
[자바]백준 3085번 사탕게임[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 설명 해당 문제는 아래와 같은데 잘 이해가 안 되었다. N x N 크기의 보드에 사탕을 채워 놓았고 사탕의 4가지 색상 중 어느 것이든 놓일 수 있다. 이때, 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 여기서 파란색으로 칠한..
[자바]백준 정수 a를 k로 만들기 [탐색] [엄탱] 문제 입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다. 연산 1: 정수 A에 1을 더한다. 연산 2: 정수 A에 2를 곱한다. 정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자. 입력 첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다. 출력 첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다. 제한 1 ≤ A x[1] - y[1]); boolean[] visited = new boolean[K + 1]; pq.offer(new int[]{A, 0}); while(!pq.isEmpty()) { int[] cur = pq...
[자바] 백준 16173번 점프왕 쩰리(Small)[탐색][엄탱] 문제 ‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 ..
[자바]백준 1476번 날짜 계산[브루트포스][엄탱] 문제 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. ..
[자바]백준 1018번 체스판 다시 칠하기[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 간단하게 설명해서 W와 B가 칠해져 있는 M x N 크기의 보드에서 8 x 8 크기로 잘라서 체스판을 만들려고 한다. 체스판은 W와 B가 교차해야 하는데 M x N 크기의 보드에서 8 x 8을 잘랐을 때 W와 B가 교차하는 체스판을 만들기 위해서 W 혹은 B를 다시 칠해야 하는 정사각형 개수의 최솟값을 구하는 문제이다. 예를 들어서, 9x9 크기의 보드에서는 8x8 크..
728x90

티스토리툴바