내맘대로블로그

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net gold 3 bfs 두번 사용해서 풀었다. 1. 여러 섬들을 구분한다. (dfs나 bfs이용해서 구분, 나의 경우엔 어차피 다 연결되어있는 거라 판단해서 bfs를 사용하였다.) 2. 바다이며(0인 경우), 주변에 섬인 경우(1인 경우) 다른 섬과의 거리를 파악한다.(최단 거리를 파악해야하기에 bfs를 이용한다.) 거리 배열을 따로 두어 거리를 파악하였다.(예전엔 무턱대고 cnt로 하였는데 이렇게하면 값이 어마어마하게..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net silver 4. 백트래킹으로 모든 경우의 수를 구해서 풀이하였다. 내가 헷갈려했던 것은 날짜 계산이었는데, 스케줄을 짜는 시점에서 마지막 날은 현재 날짜 + 기간이었는데 이 부분이 헷갈렸다. import java.io.*; import java.util.*; class Main { static int N, max; static int[][] works; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new B..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net Gold 5 문제 상황대로 풀이하면 되는 문제. 뱀이 성장한 만큼 이동인지 머리만 한칸씩 이동인지가 헷갈려서 시간이 오래걸렸다. 방향 전환과 문제의 종료 조건만 잘 구분해주면 됨. 방향 전환은 시간을 기록하고 그 시간에 방향을 바꿔주면 된다. 벽을 만나는 경우는 일반적인 bfs처럼 풀이하면 되고(해당 문제가 bfs 풀이는 아님) 뱀이 자신의 몸을 만나는지에 대한 풀이는, 나의 경우엔 뱀의 경로를 전부다 기록하고 뱀의 ..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 1. BFS로 풀이 2. 주어진 사항에 맞게 풀이하면 금방 풀 수 있음. import java.io.*; import java.util.*; class Main { static boolean[] visit = new boolean[10000]; public static void main(String[] args) throws Exception { BufferedReader br = new Buffe..

다익스트라 알고리즘을 공부하며 풀었던 문제! 왜 힘들어했는지 모르지만 공부 후 스스로 구현해 보며 상당히 어려워했었다. 1. PriorityQueue에 형식의 자료형을 넣어야 하는지를 제대로 이해하지 못했다. -> 속도를 위해 PriorityQueue를 써야하고 가중치를 기준으로 정렬되어야 한다. 2. 최단 경로를 저장하는 부분에서 프로세스에 대한 이해가 미흡.(뭔가에 씌였던 것인지 이해 불가임) while(!pQueue.isEmpty()) { Node cur = pQueue.poll(); visit[cur.v] = true; for (int i = 0; i < arrList[cur.v].size(); i++) { Node next = arrList[cur.v].get(i); //nextWeight : ..

programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr DFS를 이용해서 제일 작은 부분(길이가 1이 될 때)까지 쪼개가며 들어가야한다. 사각형을 절반씩 나누어 4개의 칸으로 만들면 시작점이 (0,0) (0, 0 + length/2), (0 +..

programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 나의 풀이 1. 먼저 불량사용자에 해당하는 사용자를 찾아 arrayList bannedList 형태로 만든다. 2. 불량사용자 순열을 만든다. 3. 이전에 만든 bannedList의 순서에 있는지 확인 후 resutlSet에 만든다. 4. 순열이기 때문에 겹칠 수 있어서 resultSet을 이용하여 중복을 제거한다. package com.example.demo; import ..

programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 요구 사항 대로 풀면 되는 방식. 두 번째 풀이인데 이전에 어떻게 풀었는지 잘 기억은 안나고 stack을 이용한 것 같다. 요구 사항상 이전의 값을 기억해야하는 부분이 있어서 계산한 결과 바로바로 풀이를 하기보다, 미리 각 항목들의 값을 구해놓고 나중에 더하는 방식으로 풀이하였다. 풀이 상에 문제 될 수 있는 요인은 중첩이나 10에 대한 처리일 것 같다. 그 부분만 잘 처리해준다면 문제 풀이를 잘 할 수 있다. import java.util.*; class Solution { public int solution(String dartResult) {..

2018 KAKAO BLIND RECRUITMENT 였던 문제! programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 단순 구현 문제였다. for문 여러 개 써서 해결! 처음 이 문제를 풀 때는 감이 도저히 안 오고 푸는 내내 힘겨웠던 기억이 있는데 지금도 다시 블록을 채우는 과정에서 약간 고생하긴 했지만 수월하게 풀었다. bfs나 dfs이런거 없이 그냥 stack이나 for문 이용해서 풀어도 잘 풀리고 ..

programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 1. boolean array 2개를 만들어서 하나는 유니폼이 있는 학생, 하나는 여유분이 있는 학생으로 나눴다. 2. 먼저 여유분이 있지만 도난당한 학생을 먼저 처리해주고, 이후엔 앞의 번호의 학생에게 우선 빌려주는 방식으로 처리하였다. 풀이 과정에서 11번이 안 되었는데 배열을 쓰는 과정에서 제일 끝 값에 대한 처리가 미흡했던 것으로 추측 된다. 예시의 테스트케이스를 이용하..