알고리즘/백준

    백준 13902 - (Java)개업 2
    알고리즘/백준

    백준 13902 - (Java)개업 2

    https://www.acmicpc.net/problem/13902 13902번: 개업 2 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 1. 유형 다이내믹 프로그래밍 2. 문제 분석 사용한 자료구조 set

    백준 16988 - (Java)Baaaaaaaaaduk2
    알고리즘/백준

    백준 16988 - (Java)Baaaaaaaaaduk2

    https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 1. 유형 BFS, 구현 2. 문제 분석 dfs와 bfs를 사용하는 문제였습니다. 1번 돌을 놓을 두 곳을 찾아서 돌 놓기 1번 돌로 둘러싸여 있는지 판단하기 bfs를 시작할 2번 돌 찾기 bfs 돌리기 만약 완전히 둘러싸였으면 2번 돌 카운트 1번 돌 놓을 자리 찾기 2중 for문을 돌려서 아직 돌이 놓아지지 않은 자리를 찾습니다. BFS를 시작할 곳을..

    백준 - 1059 (Java)좋은 구간
    알고리즘/백준

    백준 - 1059 (Java)좋은 구간

    https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 유형 수학, 배열 풀이 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int N =stoi(st.nextTo..

    백준 16985 - (Java) Maaaaaaaaaze
    알고리즘/백준

    백준 16985 - (Java) Maaaaaaaaaze

    https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 유형 구현, 너비우선탐색 문제분석 위 순서대로 구현하시면 됩니다. 회전 먼저 arraycopy라이브러리를 사용하여, 원본을 복사해줍니다. 그리고 map에 시계방향 회전을 합니다. 순열로 판의 위치 재배열 순열에서 중복은 허용하지 않기 때문에, contains라이브러리를 사용했습니다. list에 {0,1,2,3,4} or {0,1,2,4,3} ... 등으로 총 5!만큼 만들어줍..

    백준 18223 - (Java)민준이와 마산 그리고 건우
    알고리즘/백준

    백준 18223 - (Java)민준이와 마산 그리고 건우

    https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 유형 다익스트라 문제분석 플로이드 와샬을 쓰려고 했지만 인풋값이 너무 커서 3중 for문에서 시간초과가 날 것입니다. 따라서 최단거리 알고리즘 중 하나인 다익스트라를 사용 설계를 하자면 코딩화 가장 큰 핵심은 다익스트라 구현입니다. 다익스트라의 핵심 미리 구해놓은 경로보다 현재의 새로운 경로가 더 가까울시 갱신. 위와 같은 상황, 1->3까지 가..

    [devmoon]백준 14938 - 서강그라운드
    알고리즘/백준

    [devmoon]백준 14938 - 서강그라운드

    https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 유형 shotest path 2. 시뮬레이션 최단거리 구하는 문제입니다. 추가적인 조건 없이 정석적인 다익스트라, 플로이드와샬을 구현할 수 있다면 어려울거 없는 문제입니다. 시간복잡도가 100^3이기 때문에 플로이드와샬도 사용가능합니다. 다익스트라 인접리스트 구현 1~N번 노드까지 시작노드 설정하고 다익스트라 돌리기 플로이드 와샬 2차원 배열 구현 플로이드와샬 알고리즘 돌리기 3. 코드 다익스트라..

    [devmoon]백준 18403 - (Java) 무기공학
    알고리즘/백준

    [devmoon]백준 18403 - (Java) 무기공학

    https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 1. 유형 백트래킹, 구현 2. 시뮬레이션 로직 2중 반복문으로 범위 탐색 부메랑 부분 체크 최대값 확인 시뮬레이션을 돌리면 위의 그림처럼 여러가지 경우의 수가 나옵니다. 특히, 노란색 ㄱ모양 부메랑을 만들고, 그 후에 빈칸에 따라 만들수 있는 부메랑을 확인합니다. 즉, 부메랑 한개를 만들때마다 재귀를사용하면 됩니다. 이때 범위지정을 잘 해야합니다. 3*3인 경우 아래같은 범위만..

    [devmoon]백준 15566 - (Java)개구리1
    알고리즘/백준

    [devmoon]백준 15566 - (Java)개구리1

    https://www.acmicpc.net/problem/15566 15566번: 개구리 1 연못 안에 개구리들이 있을 수 있는 연꽃 N개와, 연꽃 사이를 연결하는 다리 역할의 통나무 M개가 있다. 같은 연꽃 쌍을 연결하는 통나무의 개수는 1개 이하이다. 여기에 N마리의 개구리가 각각 www.acmicpc.net 1. 유형 구현, 백트래킹 2. 시뮬레이션 로직 각 연꽃마다 앉을 개구리를 매칭 (재귀사용) 연결된 연꽃의 개구리 끼리 주제가 맞는지 확인 분류는 백트래킹이지만 단순 구현 비중이 더 큰거 같습니다. 우선 재귀를 사용하여 하나의 연꽃에 하나의 개구리를 매칭시켜야 합니다. 이때 재귀를 사용합니다. 모든 개구리가 매칭이 됐으면, 두 연꽃끼리는 하나의 주제가 있습니다. 해당 주제에 대한 개구리들의 관심..

    [devmoon]백준 2504 - (Java) 괄호의 값
    알고리즘/백준

    [devmoon]백준 2504 - (Java) 괄호의 값

    https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 1. 유형 스택, 문자열 2. 시뮬레이션 난이도에 비해 예외케이스가 많아서 까다로웠던 문제. 로직 여는괄호 ( [ 와 닫히는괄호 ) ]가 연속해서 붙어있는 경우에 합을 계산. 예외처리를 신경써야한다. - 맨 앞에 여는괄호가 나오는 경우 )() -> 0 - 길이가 1인 경우 ) -> 0 - 짝이 안 맞는 경우 (() -> 0 3. 코드 import java.io.*; import java.util..

    알고리즘/백준

    [devmoon]백준 - 17609 (Java) 회문

    https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 1. 유형 문자열 2. 시뮬레이션 투포인터 사용 두 문자가 다른 경우 왼쪽을 삭제하는 경우와, 오른쪽을 삭제하는 경우가 존재 두 경우를 모두 탐색하기 위해 재귀사용 3. 코드 import java.io.*; import java.util.*; public class Main { static String s; static int answer; public static void main(String[] args) throws IO..

    [devmoon]백준 1062 골드4 - (Java) 가르침
    알고리즘/백준

    [devmoon]백준 1062 골드4 - (Java) 가르침

    https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 1. 유형 백트래킹, 조합 2. 시뮬레이션 26개 알파벳으로 K개의 조합 구함 만든 조합으로 문자열을 만들수 있는지 체크 위의 예시처럼 'a' 't' 'n' 'c' 'i'는 처음부터 들어있기 때문에 신경쓸 필요가 없다. 따라서 파란색칸만 중복확인을 하면 된다. 필요한 지식 조합구하기 -> 재귀사용 중복체크 -> 비트마스크 / HashSet / 26크기의 배열 사용 가운데 문자열만 슬라이싱 ..

    [devmoon] 골드4 백준 - 2661 좋은 수열
    알고리즘/백준

    [devmoon] 골드4 백준 - 2661 좋은 수열

    https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1. 유형 순열, 백트래킹 2. 시뮬레이션 N자리로 만들 수 있는 수를 순열을 구한다 한자리씩 추가할때마다, 반복하는 부분이 있는지 파악한다 만약 반복이 되면 그 자리에서 return한다 (백트래킹) 3. 코드 import java.io.*; import java.util.*; public class Main { static String ANS; public static void main(String[] ar..

    [devmoon] 백준 1197 - (Java)최소 스패닝 트리
    알고리즘/백준

    [devmoon] 백준 1197 - (Java)최소 스패닝 트리

    https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 유형 프림, 크루스칼, union-find 2. 시뮬레이션 1. 크루스칼 알고리즘 uion-find를 활용한다. 두 노드의 부모가 일치하면 연결됐다는 의미 다르다면 연결이 안 됐다는 의미 3. 코드 1. 크루스칼 import java.io.*; import java.util.*; public class Main { static class Node..

    [devmoon] 백준 1976 - (java)여행 가자
    알고리즘/백준

    [devmoon] 백준 1976 - (java)여행 가자

    https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 유형 union-find 2. 시뮬레이션 하나하나 다음 노드가 연결됐는지 확인하는 문제가 아니다. 경로가 한 덩어리로 이어져 있는지만 확인하면 된다. 따라서 각 노드의 "최고"부모노드가 전부 같으면, 노드가 전부 연결 돼있다는 의미. 부모노드를 구하기 위해 union-find알고리즘을 활용 3. 코드 import java.io.*; import java.util.*; public class ..

    백준 - 1600 말이되고픈 원숭이 (Java)
    알고리즘/백준

    백준 - 1600 말이되고픈 원숭이 (Java)

    https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 유형 DP, BFS 2. 로직 bfs를 돌리면서 조건에 맞는 경우만 큐에 넣어주기 시뮬레이션을 돌리면 위 같은 상황이 나온다. 현재 좌표에서는 이전에 말처럼 이동했는지 알수 없다. 따라서 dp[말처럼 이동 횟수][행][열]인 3차원 배열에 이동거리를 저장하고, 저장한 것 보다 더 작은 이동회수가 있을겨우만 큐에 삽입하면 된다. 3. 코드 import java.io.*; imp..

    백준 21610 - (Java, python) 마법사 상어와 비바라기
    알고리즘/백준

    백준 21610 - (Java, python) 마법사 상어와 비바라기

    https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 1. 유형 시뮬레이션 2. 코드 더보기 import java.io.*; import java.util.*; public class Main { static int N, M, d, s; static int table[][]; static ArrayList clouds; static boolean visit[][]; static int dir[][] = { { 0, -1 }, { -1, -1 ..

    백준 - 1662 압축
    알고리즘/백준

    백준 - 1662 압축

    https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 1. 유형 스택, 재귀 2. 풀이 1) 입력 문자열을 각각 문자로 파싱 2) 맨 끝에서 부터 pop을 하며 (, ), 숫자 경우에 따라 조건을 대입 3) 재귀를 활용 3. 코드 def rec(tmp, stack): while stack: top = stack.pop() if top == ')': tmp += rec(0, stack) elif top == '(': r = int(stack.po..

    알고리즘/백준

    백준 15810 - 풍선 공장

    https://www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 1. 유형 우선순위큐 2. 풀이 1) [누적시간, 개인당 작업 시간] 형식으로 우선순위큐 선언 2) 정해진 갯수를 만들때 까지 반복 3. 풀이 import sys import heapq N, M = map(int, input().split()) list = list(map(int, input().split())) pq = [] for ll in list: he..

    알고리즘/백준

    백준 2910 - (python)빈도 정렬

    www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 1. 알고리즘 유형 정렬, 구현 2. 자료구조 set, 우선순위큐, 딕셔너리 3. 풀이 리스트에서 요소마다 반복횟수를 딕셔너리로 만들기 1) count() 함수 사용 우선순위큐로 정렬 1) 이미 heapq에 넣으면 set에 추가해서 중복 방지 2) 우선순위의 기준 잡기 출력 1) 반복 횟수만큼 출력 코드 import sys import heapq N, C = map(int, sys.stdin.readline().split()) li = list(map(..

    알고리즘/백준

    백준 17609 - (python)회문

    www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 1. 알고리즘 유형 투포인터 2. 자료구조 x 3. 풀이 회문판단 1) 문자열 왼쪽끝, 오른쪽끝 인덱스 잡고 비교 2) 왼쪽끝과 오른쪽끝이 같아지거나, 크로스 될때까지 문자비교 3) 만약 다르다면 유사회문일 수도 있음, 이상없으면 회문 유사회문 판단 1) 왼쪽 인덱스를 한칸 넘겨서 회문인지 판단 2) 오른쪽 인덱스를 한칸 넘겨서 회문인지 판단 3) 1, 2 과정이 둘다 아닌 경우 2를 리턴(아무런 회문이 아니다) 회문과 유사회문 판단은 코드..

티스토리툴바