막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 귀요미 아기상어 문제입니다. 옛날에 나중에 풀어야지 했다가 이번에 solved 클래스에 있길래 풀어봤습니다. 처음에 잘 푼줄 알고 테케돌려보는데 4,5,6 만 틀려서 디버깅 하나하나 다 돌려보며 확인했는데도 맞아서 삽질을 좀 했는데 원인은 모든 물고기 상대로 지나갈 수 있는 건지 알았는데 자신보다 작거나 같은 크기의 물고기만 지나갈 수 있던 거였습니다. 문제를 잘못읽는 습관이 많은데 조심해야겠습니다. ㅠ..

www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 백준 3248 양 문제입니다. 저번에 풀고서 분명 맞았는데 계속 틀리게 나와서 이상하다 싶어 버린 문젠데 재채점 되서 맞았다고 알림이 왔습니다. 이거랑 거의 똑같은 문제는 다음과 같습니다. youngest-programming.tistory.com/424 [알고리즘] 백준 3187 양치기 꿍 -bfs- 자바 www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 ..

www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 기본적인 BFS를 살짝 응용한 문제입니다. BFS를 돌며 한 영역에서 양과 늑대의 수를 비교해주고 결과를 도출해주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { private static boolean[][] isVisited; pri..

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 브루트포스 분류별 풀기에 있는 백준 1759 암호 만들기를 풀어봤습니다. ㅎㅎ 정렬순 + 모음1개 이상 자음 2개이상인지 체크 해서 완전탐색하여 풀었습니다. 브루트포스 분류라 비효울적이여도 통과한 것 같습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { private static String[] arr; pr..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 주석에 풀이를 적어놓았습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { static int[] nums; static int[] arr; static boolean[] isVisited; static int N; static int M; static StringBuilder sb = new StringBuilder()..

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 분류별풀기에서 백트랙킹을 보다 N과 M 시리즈가 더있길래 풀어봤습니다. 순서대로 출력해야하므로 정렬하고 백트랙킹 써주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; class Main { static int[] nums; static int[] arr; static boolean[] isVisited; stat..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 백준 7562 나이트의 이동을 풀어봤습니다. 방향만 잘 설정해주면됩니다. 평소 map크기를 size+2 해서 index out of error를 해결했는데 여기서는 불편해서 비교문으로 처리를 했는데 이게 더 간편한거같아서 애용하려합니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 백준 10026 적록색약 문제입니다. 일반인이 보았을때의 구분되있는 색의 개수 초록색과 빨간색이 같은색으로 취급하는 적록색약인이 보았을때 구분되는 색의 개수를 각각 구해야합니다. 적록색약인은 R과 G를 같은색 취급하므로 map에서 G를 R로 치환한뒤 일반인과 똑같이 bfs()를 돌려주었습니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java...

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502 연구소를 풀었습니다. 벽을 3개 세우고 바이러스를 퍼트리고 안전지역을 구하는 문제입니다. 다음과 같이 로직으로 풀었습니다. 1. 안전지역(0)에 모든 경우의 수로 벽을 3개 세운다 -백트랙킹- 2. 벽 3개를 세운 후 바이러스를 퍼트립니다. -bfs- 3. 안전구역의 최댓값을 구합니다. 문제를풀며 삽질했던 부분은 copy()가 깊은 복사가 안된다는 점입니다. 평소 1차원 배열은 깊은 복사가 되었던것같은데 2..

programmers.co.kr/learn/courses/30/lessons/42895?language=kotlin 코딩테스트 연습 - N으로 표현 programmers.co.kr 프로그래머스 N으로 표현 문제입니다. DP 유형 문제라 생각이 안나 풀이를 봤는데 DFS 로 푼 사람도 많았습니다. 저도 DFS로 풀었고 DP 로 푼 예제는 다음을 보시면 될 것 같습니다. gurumee92.tistory.com/164 프로그래머스 문제 풀이 N으로 표현 이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다. 문제 URL N으로 표현 Contents 문제 지문 파악하기 강사님의 알고리즘 풀� gurumee92.tistory.com 풀이 방법은 주석..

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백준 14889 스타트와 링크 문제를 풀어봤습니다. 주어진 인원 수와 그 인원들끼리의 시너지 점수가 담긴 2차원 배열을 보고 가장 격차가 적게 스타트팀, 링크팀 두 개의 팀을 짜는게 목표인 문제입니다. 처음 풀이는 시간초과가 났는데 원인은 조합이 아닌 순열로 탐색을 했기 때문이었습니다. 주의해야겠습니다. 1. 두 개의 팀을 나누니까 인원수의 1/2 만큼 탐색을 하면 탐색을 종료합니다. 2. 1번을 위해 isVisted[] boole..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백준 백트랙킹 단계별풀기의 14888번 연산자 끼워넣기를 풀어봤습니다. 숫자 리스트와(n) 숫자를 연산할 만큼의(n-1) 사칙연산자의 개수가 주어집니다. 가장 큰 경우와 작은 경우를 구하는 문제입니다. 1. 먼저 탐색은 입력 숫자만큼일 때 까지 재귀를 돌립니다. 2. 연산자는 총 4개입니다. 4크기의 연산자 배열을 만듭니다. 3. 모든 연산자의 경우를..

www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 백트랙킹 단계별풀기의 2580 스도쿠 문제를 풀어봤습니다. 1. 처음 입력받는 값을 map에 세팅시 0(빈칸)인 값을 리스트에 넣어줍니다. 2. 첫줄(depth)부터 dfs를 채워주고 조건은 빈값을 모두 채운 경우 끝내줍니다. 3. 빈값의 좌표를 불러오고 해당 좌표에 1~9 모두 넣어서 되는값인지 check 해줍니다. 4. check를 통과하면 해당 빈 좌표에 해당 값이 들어가고 dfs를 이어서 돌려줍니다..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 백준 dfs,bfs 단계별 풀이의 마지막 문제를 풀어봤습니다. ㅎㅎ 풀다가 모르겠어서 밑에 분의 풀이를 참고해서 풀었습니다. velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%802206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-java [Algorithm] 백준..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 백준 dfs, bfs 단계별 풀기에 있는 1697번 숨바꼭질 문제입니다. 총 1초가 걸리는 3가지 이동 방법이 있으며 누나가 동생에게 가장 빨리 도착하는 시간초를 구하는 문제입니다. 1. 길을 나타낼 1차원 배열 선언, 값은 그 지점까지 도착한 시간초를 담아놀 예정 2. 처음 수빈이 위치를 큐에 넣음 3. bfs 탐색 시작 4. 수빈이 위치가 동생 위치와 같다면 break 5. ..