본문 바로가기
환영합니다. 이 블로그 번째 방문자입니다.

JAVA/알고리즘 서브 노트

  (15)
[Programmers: JAVA] 단어 변환 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 쉬운 문제이기는 했지만 나중에 이 문제를 봤을 때 BFS로 풀 생각을 할 수 있을지는 모르겠다 경로 탐색에서는 DFS를 더 많이 쓰는 스타일이라 BFS도 함께 구현해 보아야 겠다 import java.util.LinkedList; import java.util.Queue; // 단어 변환 public class Solution { static class Word{ String word; int d..
[Programmers: JAVA] 네트워크 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 위 문제와 유사하다는 생각이 들었다 위 문제는 플로이드-워샬 알고리즘으로 풀었는데 이번에는 DFS/BFS 연습을 위해 다르게 풀어보도록 하겠다 DFS - 추후 개선해야 할 코드이긴 하나 일단 올림 public class Solution { static int answer; static boolean visited[]; public int solution(int n, int[][] computers) { visited ..
[백준 19640: JAVA] 화장실의 규칙 https://www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net [1회차] 11월 13일, 킹받는다고 추천받은 문제 문제 접근 방법 (사용 자료구조, 알고리즘) 입력 (1) 사원 N명, 회장이 지시한 줄 수 M, 데카 앞에 있는 사원 수 K (2) Employee 객체( 사원번호, 근무일수, 화장실 급한 정도, 서 있는 열) 생성해서 객체 배열을 만들어 준다. 객체 배열은 Line[M][N%M == 0? N/M : N/M + 1] 로 선언..
[프로그래머스: JAVA] 문자열 압축 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [1회차] 11월 8일, 문제 추천받음 문제 접근 방법 (사용 자료구조, 알고리즘) 일단 스토리라인을 적어보자면 다음과 같다, 사실 반복문으로 풀어야 하는 문제인거 알고 있었는데(6개월 전에 파이썬으로 품) 도전해보고 싶었음... 도전 정신 쯤으로 봐주길... [조건과 출력] 문자열은 제일 앞에서부터 잘라야… ⇒ 가장 짧은 길이 출력하기 주어지는 문자열을 자를 수 있는 경우들 (1 ~ N)개 이지..
[백준 14503: JAVA] 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [1회차] 11월 12일, 랜덤 문제 돌리기 문제 접근 방법 (사용 자료구조, 알고리즘) 로직(쌉구현) (0) 현재 칸 청소 ( map에 2로 표현) (1) 현재 방향을 기준으로 왼쪽 방향의 칸부터 탐색하며 해당 칸이 0인(청소가 가능한 구역) 칸이 존재하는지 확인 - 존재한다면 2-1 의 조건에 부합하므로 방향과 칸만 이동시키고 청소기 클래스에 있는 isFind를 true 로 설정 후 반복문 ..
[프로그래머스: JAVA] 양궁대회 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [1회차] 11월 11일, 문제 추천받음 문제 접근 방법 (사용 자료구조, 알고리즘) 일단 스토리라인을 적어보자면 다음과 같다 라이언이 이겨야 함, 라이언이 못 이기는 경우는 -1 출력 이기려면 ? 총합 점수가 많아야 해 -> 점수 어떻게 내는데? k 점을 어피지랑 똑같은 갯수로 맞추면 점수는 어피치꺼 k 점을 어피치보다 많이 맞추면 점수는 라이언꺼 k 점을 둘 다 못 맞추면 0점 -- 일단 점수..
[백준 : JAVA] 움직이는 미로 탈출하기 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net [1회차] 11월 10일, 문제 추천받음 문제 접근 방법 (사용 자료구조, 알고리즘) 입력 (1) 8개 줄에 걸쳐서 주어지는 체스판의 상태를 walls[8][8][8](3차원 int 배열)로 저장 (2) 가장 처음에 나온 벽('#')이 가장 위에 있으므로 이것을 찾으면 firstIdx를 해당 열로 변경해준다.(1번만) 로직 (0) 만약 firstIdx가 변하지 않았다면(-1) 벽이 없으..
[백준 17837: JAVA] 새로운 게임2 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net [1회차] 10월 31일, 스터디 문제 접근 방법 (사용 자료구조, 알고리즘) 입력 (1) N, K, int map[N][N] : 게임판에 대한 정보, int move[N][N][K+1] : 게임판에 말들의 이동에 대한 정보 저장, Horse horses[K+1] : 말에 대한 정보 저장 (2) Horse 클래스 : x(세로), y(가로), dir(이동 방향), idx(move 배열에서의 해당..
[백준 15684 : JAVA] 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [1회차] 10월 29일 ~ 10월 30일 : 거드름의 결과랄까...^^ 문제 접근 방법 (사용 자료구조, 알고리즘) 이 문제는 시행착오가 많았어서 차례로 한번 보여줄까 한다 (1) 자료구조 (List + HashMap) + 조합 입력 (1) {N, M, H} (2) 연결할 수 있는 사다리의 후보군들을 저장해 놓는 candidates(Point 리스트)에 (N) * (H + 1)개의 사다리를 넣..
[BJ 17406] 배열 돌리기4 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net [1회차] 8월 11일 강의 시간 이 문제 너무 기억이 남. 수업 시간에 처음 풀었는데 그냥 무지성으로 배열 돌렸다가 매우X1000 헤깔려서 결국은 사망해버렸다는 전설이 깃든 문제였음. 배열 대신 내가 돌아감. 문제 로직 따위는 없이 문제 조건에 따라 전부 for 문으로 옮겨버렸다. 그 때 어거지로 풀었던 코드를 공개합니다 뚜둔 더보기 import java.io.Bu..
[SWEA 1952] 수영장 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [1회차] 8월 24일 스터디 문제 이 때, 문제 접근 방법을 몰라서 (이런 문제 스타일을 처음 풀어봤다) 아마 인터넷 해설을 보고 풀었던 것 같다. 생각치도 못했던 방법이라(그 때는 dfs, bfs 적용 따위는 하지 못했음) 나를 충격에 빠뜨렸던 문제였다. 코드 더보기 import java.io.BufferedReader; import java.io.FileInputStream; import ja..
[SWEA 2115] 벌꿀채취 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [1회차] 10월 2일날 풀었어서 코드만 첨부 더보기 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Solution { static int N, M, C, ans, max; static int map[][], honeys[]; static boolean isVisit..
[백준 17472] 다리만들기2 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 접근 방법 1. 입력받기 : 입력을 받아서 2차원 배열에 지도 정보 저장 2. 섬의 개수 카운팅 & 섬 리스트에 저장 & 섬 구별 라벨링 섬 : 1이 뭉쳐있는 곳 -> dfs, bfs 로 찾기 섬 리스트에 저장 : Island 클래스를 만들어서 Point 객체 리스트를 변수로 넣어줌 섬 구별 라벨링 : dfs를 돌면서 섬마다 1부터 라벨링(인덱싱)을 해줌 3. 섬 간의 ..
[SWEA 2805] 농작물 수확하기 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2차원 배열에서 마름모꼴 영역의 합을 구하는 문제 나...솔직히 이 문제보고 BFS로 해보려고 했는데...접근 방법이 틀렸으니 맞을리가 있나... 예전에 다룬 포스팅 중 BFS 순회가 빠르다는 뭐 그런 얘기를 하면서 있던 그림을 보고 어떻게 해보려고 했지만 실패! 지금 생각해보니 풀려면 풀 수 있을지도 모른다..ㅎ (거짓말) 코드 import java.io.BufferedReader; impo..
[프로그래머스: JAVA] 키패드 누르기 문제 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4-1...

티스토리툴바