알고리즘
백준 - 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
2021 카카오공채 - 신규 아이디 추천
programmers.co.kr/learn/courses/30/lessons/72410?language=java 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 1. 유형 문자열 2. 풀이 이 문제는 모듈화가 중요합니다. 그래야 나중에 실수했을 때, 디버깅이 편합니다. 각 단계별로 함수를 만들어서 시키는대로 구현합니다. 딱히, 특별한 구현법이 없는거 같습니다. 문자열을 수정하기 편하게 ArrayList 자료구조를 사용하고, 끝 부분부터 탐색하며 remove를 해줬습니다. 3. 디버깅 실수 case4부분..
백준 - 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]을 ..
백준 5587 - 카드 캡터 상근(Java)
www.acmicpc.net/problem/5587 5587번: 카드 캡터 상근이 1번째 줄에 상근이의 점수를 출력하고, 2번째 줄에 근상이의 점수를 출력한다. www.acmicpc.net 1. 유형 구현 2. 자료구조 우선순위큐 3. 기능 - 상근카드, 근상카드 나누기 - 타겟카드 보다 큰지 작은지 판단하는 함수 4. 풀이 조건에서 가장 작은 카드부터 출력해야하기 때문에 우선순위큐를 선언 그 다음은 큐에서 하나씩 수를 빼와서 타깃과 비교하면 끝. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Pri..
백준 18428 - 감시 피하기(Java)
www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 1. 유형 시뮬레이션 2. 자료구조 어레이리스트 3. 기능 - 2차원 배열에서 3개 선택 (조합) - 한 방향으로 끝까지 탐색하기 4. 풀이 N*N의 맵에서 3개를 선택하는 경우의 수는 8000 아래다. 즉 브루트포스로 푸는 것이 가능. 2차원 배열에서 조합을 구하는 방법은 순서대로 0~N*N-1까지의 수를 한칸마다 할당. 이때 row는 k/N, col는 k%N 공식이 나온다. k가 2, N이 5라고 ..
백준 18249 - 근손실(java)
www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 1. 유형 구현, 백트래킹 2. 자료구조 없음 3. 기능 - 순열 4. 풀이 - 재귀를 사용해서 순열을 구한다. 다음 재귀를 호출할 때, 500미만이면 백트래킹 코트. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..
백준 2310 - 어드벤처 게임(Java)
www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 1. 유형 그래프, 구현, 재귀 2. 자료구조 - 어레이리스트 3. 기능 - 인접리스트 만들기 - E,L,T 조건에 맞게 통과시키기 4. 풀이 재귀의 매개변수로 소지금, 현재노드를 주고 ELT 조건에 맞게 소지금을 변경해 주면 된다. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..