알고리즘

    [백준 - 20055] 실버1 - 컨베이어 벨트 위의 로봇
    알고리즘/백준

    [백준 - 20055] 실버1 - 컨베이어 벨트 위의 로봇

    www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 유형 구현 2. 풀이 로봇 배열, 내구도 배열 지정 규칙 순서대로 진행 규칙에는 안나와 있는거 같은데, 상식적으로 처음에 컨베이어 벨트 한칸 이동시 벨트 위에 있는 로봇 또한 같이 움직이는 걸 생각해 주자. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..

    [SWEA - 1812] D5 - 수정이의 타일 자르기
    알고리즘/SW Expert Academy

    [SWEA - 1812] D5 - 수정이의 타일 자르기

    swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yGVsKC0YDFAUx&categoryId=AV4yGVsKC0YDFAUx&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 유형 우선순위큐, 구현 2. 풀이 크기가 가장 큰 타일부터 만들기 타일을 만들고 남은 짜투리들은 우선순위큐에 넣기 우선순위큐 때문에 크기가 가장 큰 타일이 먼저 나옴 위 과정을 반복 입력되는 값들을 내림차순을 만든다 문제를 풀때 자투리 타일을 우선순위큐에 저장해야 하는데 아래처럼 타일을 만들고 남은 파란색과 초록색을 저장..

    [SWEA - 2112] - [모의 SW 역량테스트] 보호 필름
    알고리즘/SW Expert Academy

    [SWEA - 2112] - [모의 SW 역량테스트] 보호 필름

    swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 유형 부분집합, 구현 2. 풀이 행 하나를 선택한 후, 아무것도 안하기, A약 투입, B약 투입 인 경우로 나눈다 위의 경우를 부분집합을 구한다 K개 만큼 연속하는지 판단 또한, 잘 구현하더라도 효율성 체크에서 걸릴 것이다. 이때, K==1인 경우 바로 0출력 재귀에서 cnt가 더 큰 경우 빽트래킹 연속을 판단할때 col하나라..

    [SWEA - 2814] D3 - 최장경로
    알고리즘/SW Expert Academy

    [SWEA - 2814] D3 - 최장경로

    swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 유형 dfs, 인접리스트 2. 풀이 연결리스트를 만든다 visit배열로 방문지점을 체크하며 재귀를 돌린다 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayLis..

    [백준 - 20166] 골드5 - 문자열 지옥에 빠진 호석
    알고리즘/백준

    [백준 - 20166] 골드5 - 문자열 지옥에 빠진 호석

    www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 1. 유형 시뮬레이션, bfs, 해쉬맵 2. 풀이 시간 복잡도는 10*10* 8^5 이다 한 칸당 8방향으로 최대 5의 길이만큼 이동 할 수 있어서이다. 해쉬맵을 사용 맨 마지막으로 주의할 점은 신이 좋아하는 문자열은 중복될 수도 있다 부분이다. 이 조건을 못 읽고 풀어서 시간 낭비를 많이 했다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

    [백준 - 19952] 골드4 - 인성 문제 있어??
    알고리즘/백준

    [백준 - 19952] 골드4 - 인성 문제 있어??

    www.acmicpc.net/problem/19952 19952번: 인성 문제 있어?? 인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 www.acmicpc.net 1. 유형 시뮬레이션 2. 풀이 이 문제의 핵심은 3차원 배열을 사용해서 bfs를 사용할 수 있는가 이다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util...

    [백준 - 20165] 골드5 - 인내의 도미노 장인 호석(java)
    알고리즘/백준

    [백준 - 20165] 골드5 - 인내의 도미노 장인 호석(java)

    www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 1. 유형 시뮬레이션 2. 풀이 푼 시간: 1시간 00분 1. 도미노 높이를 저장한 map, 도미노 상태를 저장한 map 설정 2. 주어진 조건대로 풀이 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..

    [백준 - 19640] 골드5 - 화장실의 규칙
    알고리즘/백준

    [백준 - 19640] 골드5 - 화장실의 규칙

    www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 1. 유형 우선순위큐 2. 풀이 우선순위큐에 들어갈 클래스를 만든다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Que..

    [백준 - 2841] 실버2- 외계인의 기타 연주
    알고리즘/백준

    [백준 - 2841] 실버2- 외계인의 기타 연주

    www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 1. 유형 스택 2. 풀이 위의 조건 처럼 입력을 받을때 기존의 스택의 peek()보다 더큰 플랫을 입력 받을 경우 추가를 해준다. 하지만 더 작은 플랫을 입력 받을 시, 스택에서 입력값보다 더 큰 플랫이 나올 때까지 pop을 해야한다. 위와 같은 경우가 나오면 3, 2를 빼고 마지막에 1은 이미 존재 하기 때문에 push를 하면 안된다 그렇기 때문에 while문을 빠져나..

    [백준 - 1238] 골드3 - 파티
    알고리즘/백준

    [백준 - 1238] 골드3 - 파티

    www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 유형 다익스트라, 그래프 2. 풀이 1) 모든 점에서 다익스트라를 돌려서 X까지의 거리를 구한다. 2) X에서 다익스트라를 돌려서 각 마을까지의 최단거리를 구한다. 3) X까지 간거리와 본인 마을로 돌아온 거리를 더한 후, 최대값을 구한다 자료구조: 인접리스트, 우선순위큐 인접리스트 구한다 우선순위큐 사용을 위해 클래스 구현 X마을 까지의 최단거리를 구한다 3. 코드 pack..

    [백준 - 14698] 골드4 - 전생했더니 슬라임 연구자였던 건에 대하여(Hard)
    알고리즘/백준

    [백준 - 14698] 골드4 - 전생했더니 슬라임 연구자였던 건에 대하여(Hard)

    www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 1. 유형 그리디, 우선순위큐 2. 풀이 문제에서 요구하는 값이 가장 작으려면 매 상황마다 가장 작은 슬라임 2개를 합성하면 가장 작은 결과를 얻는게 가능하다. 이때 사용하는 자료구조가 우선순위큐이다. 문제에서 가장 어려운 부분은 숫자의 범위 초과이다. 아래처럼 mod연산을 통해서 long타입을 넘길거 같으면 나머지 연산을 해야한다. java를 쓰면 시간초과가 날 수 있..

    [백준 - 15922] 골드5 - 아우으 우아으이야!!
    알고리즘/백준

    [백준 - 15922] 골드5 - 아우으 우아으이야!!

    1. 유형 구현 2. 풀이 visit배열을 써서 방문한 곳과 방문 안 한 곳을 나눠서 풀 수도 있지만, 그랬다간 시간초과가 날것이다. 때문에 가능한 경우를 나누어서 생각 해야한다. 아래처럼 나오는 숫자가 3가지의 경우가 있다. 즉, 겹치는 부분이 있기때문에 끝 점을 계속 갱신 하면서, (끝점 - 처음점)을 빼는 식으로 총 길이를 구해야 한다. 3. 코드 package 구현; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Beak_15922아우으우아으이야 { public static void main(St..

    [백준 - 2931] 골드3 - 가스관 (구현)
    알고리즘/백준

    [백준 - 2931] 골드3 - 가스관 (구현)

    1. 유형 구현, dfs 2. 풀이 1) M부터 4방 탐색 2) 가스관 별로 방향을 바꾼다 3) '.' 이 나왔을 때, 7가지의 가스관을 다 넣어본다 4) 탐색한 가스관의 갯수가 필요한 가스관의 수하고 같다면 종료한다 M부터 4방향을 탐색해서 시작 방향을 정한다. 현재 좌표에서 가스관의 종류별로 방향을 바꿔줘야 한다. 다음 좌표가 '.'이면 7가지의 가스관을 넣어서 완전 탐색한다 예외적으로 생각해야할 점은, 밑에 파란색 칸은 두번 세어주면 안된다. 그렇기 때문에 아래와 같은 코드가 필요하다. 방문한 지점이라면 cnt증가가 없다. 미방문 지점은 cnt+1을 한다 3. 코드 package 구현; import java.io.BufferedReader; import java.io.IOException; impo..

    [백준 - 17281] 골드4 - ⚾ (구현)
    알고리즘/백준

    [백준 - 17281] 골드4 - ⚾ (구현)

    1. 유형 구현, 순열 2. 풀이 타자의 순서를 정해줘야 한다. 그러기 위해서 순열을 이용한다. 9번째의 타자의 순서를 정해줄 때, 1번 선수는 무조건 4번째에 놓아야한다. 그러기 위해 아래 네모칸 코드를 넣어줬다. 게임을 진행 할때의 예외 처리는, 9번 타자까지 다 쳤을때, 다시 1번 타자로 넘어와야한다 그리고 아웃이 3번인 경우 베이스를 초기화 하고, out카운트를 0으로 만든다. 베이스를 끝 부터 탐색해서, 몇루타를 쳤는지 만큼 뛴다. 베이스는 3번까지만 있으니깐 3번을 초과하면 arr[4]에 초과한 횟수를 저장한다. 베이스를 3번부터 0번까지 탐색후 arr[4]에 저장된 값이, 방금 선수의 득점이 된다. 예를들어서 초기 베이스가 아래의 상태였다면, 위에서 2루타를 쳤다면 아래처럼 베이스가 그려지는..

    [백준 - 15685] 골드4 - 드래곤 커브
    알고리즘/백준

    [백준 - 15685] 골드4 - 드래곤 커브

    1. 유형 그리디, 시뮬레이션 2. 풀이법 예를 들어서 0 1 2 1 방향으로 움직일 때, 다음 세대의 방향은 전 방향(0 1 2 1) + (2 3 2 1)가 된다 2 3 2 1 구하는 방법은 0 1 2 1의 끝부터 반대방향-1을 해주면 된다 1 -> 3(반대방향) -> 2(-1을 해줌) 2 -> 0(반대방향) -> 3(-1을 해줌, -1은 3으로 치환) 이런 식으로 시뮬레이션을 돌린다. 아래는 이와 관련된 코드이다 그런 다음 visit 배열에 방문 처리를 한다음 4개의 꼭지점이 true인 것의 갯수를 세주면 된다. 3. 코드 package 삼성역태; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

    [Swea - 1868] 파핑파핑 지뢰찾기
    알고리즘/SW Expert Academy

    [Swea - 1868] 파핑파핑 지뢰찾기

    1. 유형 구현, bfs 2. 풀이 완전탐색을 하면서 8방향에 지뢰가 없는 칸을 찾는다. 찾은 칸에서도 똑같이 8방향에 지뢰가 없으면 큐에 넣고 bfs를 돌린다 3. 코드 현재 좌표에서 8방향을 탐색해서 지뢰가 없어야지 bfs를 돌리는게 가능하다 bfs를 돌릴때도 8방향에 지뢰가 없어야 다음 좌표를 탐색할 수 있다. 위의 과정이 다 끝난 후 아직 true로 바뀌지 않은 곳은 무조건 선택을 해야 하는 곳이다. 전체코드 package swea; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; imp..

    [Swea - 5643] 키 순서
    알고리즘/SW Expert Academy

    [Swea - 5643] 키 순서

    swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 유형 그래프 2. 풀이 인접리스트를 만든다. 이때, 주어진 그래프대로 인접리스트를 만들고, 그 반대 방향 인접리스트를 만든다. 이런 식으로 주어진 입력값과 반대 방향 리스트를 만든다. 4번 노드를 예를 들어보면, 나보다 작은 값은 3개가 있고, 큰 값은 2개가 있다. 3+2 =5 즉, 5는 전체 사이즈에서 나를 뺀 값이다. 그러므로 1부터 N번 노드를 돌면서 그래프를 탐색해서 나보다 큰값과 작은 값들의 합..

    알고리즘/SW Expert Academy

    [Swea - 1953] 탈주범 검거

    swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 유형 시뮬레이션 2. 풀이 현제 파이프가 위로 뚫려 있다면 다음 좌표의 파이프가 아래로 뚫려 있어야 한다. 3. 코드 package swea; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; imp..

    [백준 - 2457] 골드4 - 공주님의 정원(그리디)
    알고리즘/백준

    [백준 - 2457] 골드4 - 공주님의 정원(그리디)

    www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1

    [백준 - 1276] 골드5 - 교각 놓기
    알고리즘/백준

    [백준 - 1276] 골드5 - 교각 놓기

    www.acmicpc.net/problem/1276 1276번: 교각 놓기 첫째 줄에 다리의 개수를 나타내는 정수 N(1≤N≤100)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 다리의 위치를 나타내는 세 정수 Y, X1, X2가 주어지는 이는 (X1, Y)부터 (X2, Y)까지 다리가 놓여 www.acmicpc.net 1. 유형 그리디, 정렬 2. 풀이 입력값 전처리 높이가 낮은 순으로 우선순위 정렬 메모리제이션 전처리 과정 문제를 풀기 위해서 입력값을 한번 전처리 과정을 거쳐야 합니다. 1 5 10 값이 들어오면 배열의 index로는 5 ~ 9 까지만 차지합니다 3 1 5 값이 들어오면 index로는 1 ~ 4 까지만 들어옵니다. 즉, 입력값을 배열로 전처리 하고 싶으면 끝값(10, 5 등....

티스토리툴바