알고리즘/백준
백준 13901 - (python) 로봇
www.acmicpc.net/problem/13901 13901번: 로봇 첫 번째 줄에는 방의 크기 R, C(3 ≤ R, C ≤ 1,000)가 입력된다. 두 번째 줄에는 장애물의 개수 k(0 ≤ k ≤ 1,000)가 입력된다. 다음 k개의 줄에는 각 장애물 위치 br(0 ≤ br ≤ R – 1), bc(0 ≤ bc ≤ C - 1)가 www.acmicpc.net 유형 구현 자료구조 set 로직 - 무한loop - 다음 좌표 구하기 - 다음 좌표가 장애물, 방문지점, 범위밖인 경우 - 한 자리에서 4가지 방향을 전부 탐색하면 종료 조건 코드 import sys R, C = map(int, sys.stdin.readline().split()) obsNum = int(input()) matrix = [[0]*C..
백준 3190 - (python) 뱀
www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 유형 구현 풀이 현재 파이썬 연습중. 너무~ 편한듯 싶다. 자료구조 - 초마다 다음 방향: 딕셔너리 - 사과의 위치: 2차원 리스트 - 뱀의 꼬리: 덱 코드 from collections import deque N = int(input()) K = int(input()) apple = [] for _ in range(K): r, c = map(int, input().split()) apple.append((r-1, c..
![20055 - [Java]컨베이어 벨트 위의 로봇](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbtrX4k%2Fbtq3bGLZ7IK%2FmDFcsIZJaIYutz6H6ytMsk%2Fimg.png)
20055 - [Java]컨베이어 벨트 위의 로봇
www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 유형 구현 2. 풀이 문제에서 애매한 부분이 있다. 컨베이어가 움직일 때, 로봇도 같이 움직인다는 말이 안 나와 있다. 물론, 상식적으로 생각하면 로봇도 따라 움직이는게 맞긴하지만 그래도 알고리즘 문제에선 상세하게 적어주는 것이 맞다고 본다. 배열 2개 선언(로봇이 위에 있는지, 벨트의 내구도) 단계에 맞게 돌리기 3. 코드 import java.util.*; import java.i..
20057 - 마법사 상어와 토네이도
www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 1. 유형 - 구현 2. 풀이 3. 코드 import java.util.*; import java.io.*; public class Main { static int N; static int map[][]; static int currentR, currentC, sum; static int dir[][] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 ..
백준 - 6087 레이저 통신
www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 1. 유형 bfs, dp, 구현 2. 자료구조 큐 3. 풀이 이 문제는 거울->몇번 꺾이는가 로 해석해야 합니다. 이 문제의 핵심은 bfs입니다. 하지만 일반적인 문제와 다르게 최단 거리가 아닌, 경로가 더 길더라도 더 적게 꺾이는 경로를 찾는게 핵심입니다. 처음 생각은 우선순위큐와 3차원 배열을 사용 입니다. 하지만, 메모리초과가 나와서 실패했습니다. 두번째는 메모리제이션을 사용하는것 입니다. 이부분..
백준 - 2458 키순서
www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 유형 그래프, 구현 2. 자료구조 딱히 쓴거 없음 3. 풀이 그래프 리스트형식으로 구현 조건에 맞게 구현 문제를 보고 맨처음 든 생각은 dfs풀이법 입니다. 플로이드와샬 풀이로 많은 사람이 풀었던데 저는 생각하지 못했습니다. 나보다 작은애들 + 나보다 큰애들 = 사람수-1 위에서 사람수 -1 을 한 이유는 나 자신은 빼야하기 때문입니다. 1) dfs풀이 1번 노드부터 dfs를 돌려서 각 노드에 도착하면 카운..
백준 - 19591 독특한 계산기
www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 1. 유형 스트링 파싱, 구현, 덱 2. 자료구조 리스트, 덱 3. 풀이 기호, 문자열만 덱에 저장 우선순위대로 계산 예외처리(처음 음수값, 의미없는 0) 처음 주어지는 문자열을 파싱해서 기호, 숫자를 나누어 덱에 저장한다. 굳이 덱을 안쓰고 arrayList를 사용해도 될듯 파싱을 할때 주의할점은 첫 숫자가 음수인 경우이다. 이를 주의하자 또한, 0001처럼 무의미 0이 들어..
백준 - 16137 견우와 직녀
www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 1. 유형 구현, BFS 2. 풀이 문제의 설명을 완벽히 이해하는 것이 어려웠습니다. 고려할 사항이 몇가지 있습니다. - 교차로에서는 오작교를 놓지 못한다 - 연속으로 오작교를 건너지 못한다 - 주기가 맞아야지 오작교를 건널 수 있다 위의 3가지 경우를 주의 해야 합니다. 모듈화 input() - 입력함수 bfs() - bfs돌리기 풀이방식은 bfs를 돌리면서 다음에 올 수 있는 값이 0일때, 1일때, 2이..
백준 - 20061 모노미노도미노2
www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 1. 유형 구현 2. 풀이 이번 문제는 구현할 함수가 많습니다. 입력 맨 밑으로 박스를 내리기 1줄 꽉찬 라인이 있는지 1줄 삭제하고 밑으로 1줄 내리기 연한색 부분에 박스 있는지 확인 남아있는 네모칸 갯수 파악 처음에 어려웠던 부분은 blue부분을 어떻게 구현해줄까 하는 부분 입니다. 생각한 결과 blue부분을 따로 구현할 필요가 없습니다. green부분을 대칭 시켜주면 됩니다. 아래 그림은 2 3..
백준 - 2528 사다리(Java)
static class Node { int be, fin, dir; Node(int be, int fin, int dir) { this.be = be; this.fin = fin; this.dir = dir; } } www.acmicpc.net/problem/2528 2528번: 사다리 첫 번째 줄에 층 수 N (1
백준 - 1360 되돌리기(Java)
www.acmicpc.net/problem/1360 1360번: 되돌리기 첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같 www.acmicpc.net 1. 유형 구현 2. 풀이 이 문제의 핵심은 중첩된 undo의 해결법이다. undo, undo, undo 이렇게 3개만 겹쳐도 어려워진다. 처음 풀떄는, undo가 나올때마다 주어진 시간만큼 되돌아가는 식으로 풀려고 했지만 난이도가 너무 노가다이고 어려웠다. 따라서 다시 생각했다. 풀이법은 각 상태를 시간초 마다 저장하는 것이다. 4 type a 1 type b 2 type c 3 undo 3 5 ..
백준 - 3055 탈출(Java)
www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 유형 - BFS 2. 설계 s랑 *를 큐에 넣고시작 현재 좌표가 S일 경우 다음 값이 D이면 종료합니다. 현재 좌표가 S일경우 .으로만 움직입니다 현재가 *인 경우 다음 값이 . 이나 S로 움직입니다. 3. 풀이 4. 디버깅 실수 *인 경우, 즉 물이 한 좌표가 아니라 여러 좌표일 수 있습니다. 따라서 처음 입력값에서 ArrayList형식으로 좌표를 받아야 합니다. 이 점을 조심해야 합니다. import java.io..
백준 9322 - 철벽보안 알고리즘(Java)
www.acmicpc.net/problem/9322 9322번: 철벽 보안 알고리즘 소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키만을 이용하는 암호화 체계를 개발했다. 이를 "철벽 보안 알고리즘"이라고 부르기로 www.acmicpc.net 1. 유형 문자열 2. 구현 자료구조 해쉬맵 기능 공개키1의 자리 구하기 암호문을 평문으로 바꾸기 이 순서로 암호문을 평문으로 재배치 hashmap을 이용해서 공개키1이 공개키2에서 몇번재인지를 구할 수 있음. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util...
백준 6068 - 시간 관리하기(Java)
www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1
백준 17836 - 공주님을 구해라!(Java)
www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 1. 유형 bfs 2. 자료구조 Queue 3. 구현기능 bfs 검을 찾은 곳에서 부터 벽을 뚫기 가능 4. 풀이 전체코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; imp..
백준 2304 - 창고 다각형(Java)
www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. 유형 구현 2. 자료구조 ArrayList 3. 구현기능 가장 긴 높이 찾기 오른쪽, 왼쪽 탐색해서 그 다음 높은 높이를 찾기 4. 풀이 왼쪽 탐색하는 코드. 오른쪽도 아래와 같은 코드를 구현하면 된다. 전체 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
백준 16986 - 인싸들의 가위바위보(Java)
www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 1. 유형 시뮬레이션 2. 구현 자료구조 딱히 없는듯, 2차원 배열정도.. 구현해야 할 기능 지우가 낼 수 있는 모든 손동작(순열) 각 라운드의 승패 판단 다음 플레이어가 누구인지 3. 풀이 코딩이 어렵다기 보다는 문제 이해가 너무 어려웠다. 주의할 점은 2가지 이다. 입력값 20개는 각 라운드의 입력값이 아닙니다. 즉, 만약 경희가 2라운에 대결을 하고 졌을 경우, 3라운드를 넘기고 4라운드에 다시 ..
백준 20207 - 달력(Java)
www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 1. 유형 시뮬레이션, 우선순위큐 2. 자료구조 우선순위큐 3, 구현 기능 - 달력 배열 만들기 - 우선순위큐에 정렬된 순서대로 달력에 표시 - 코딩지 설정 4. 풀이 사격형 구해서 풀이 코드. import java.io.*; import java.util.*; public class Main { static int map[][], N; static class Pair { int start, end; public Pair(..
백준 16722 - 결! 합!
www.acmicpc.net/problem/16722 16722번: 결! 합! 위 입력에서 '합'을 이루는 모든 그림 조합은 (1,5,6), (2,3,5), (2,4,6), (2,7,9), (6,8,9) 5가지가 있다. www.acmicpc.net 1. 유형 구현 2. 자료구조 HashSet, 2차원 클래스 배열 3. 구현 기능 모양,색,배경을 나타내는 map구현 9개중에서 3개 조합 결! 인지 판단하는 함수 점수 계산 코드 4. 풀이 - 모양, 색, 배경색을 필드값으로 하는 2차원 클래스 배열을 생성 String type; String color; String back; public Pair(String type, String color, String back) { super(); this.type =..
백준 6051 - 시간 여행(Java)
www.acmicpc.net/problem/6051 6051번: 시간 여행 모범생 현수는 코딩하는 시간을 늘리기 위해 타임 머신을 구매 했다. 현수는 정상적으로 문제를 코딩하거나 (타임 머신을 사용하지 않고), 과거의 임의의 지점으로 시간여행 할 수 있다. 미 www.acmicpc.net 1. 유형 구현 2. 자료구조 ArrayList 3. 기능 - 각 번호에 따른 리스트 만들기 - 명령어 기능 수행 4. 풀이 - 번호에 따라서 번호를 기록하기 위해 arraylist 배열을 만든다 - 명령어에 따라서 a, t, s를 수행 ArrayList배열만 만들줄 알면 문제가 직관적이라 풀이 할게 없다. 주의 할점은 리스트를 복사 할때 얕은 복사가 아닌 깊은 복사를 해야한다. 즉, list[0] = list[1]을 ..