Algorithm

    다익스트라(Dijkstra) 알고리즘
    Algorithm/개념 정리

    다익스트라(Dijkstra) 알고리즘

    다익스트라(Dijkstra) 알고리즘 DP를 활용한 최단 경로 탐색 알고리즘 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다. 다익스트라를 구현하기 위해 두 가지를 저장해야 한다. 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다. 다익스트라의 알고리즘 순서는 아래와 같다. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i

    Algorithm

    [Algorithm] 카페 주문처리 시스템

    손님이 주문한 음료를 우선순위에 맞춰서 저장하여 처리하는 문제 (보안상 링크 및 자세한 설명 생략) 커피 종류는 최대 50개, 서로 다른 난이도를 가짐 하루에 최대 10,000명 손님이 한 명당 최대 10개 주문 가능 (커피 종류 중복 가능) 손님 번호는 1 ~ 100,000 커피 별로 주문 처리 시 우선순위 : 손님 주문 中 가장 높은 난이도 + 주문시각 오름차순 (같으면 주문 시각 오름차순) 주문 최대 호출 1만, 커피 만듬 호출 10만, 취소 호출 1만, 수량 체크 1만 함수 void init( ... ) : 음료 난이도 초기화 void order( ... ) : 손님이 주문한 음료 전송 (시간 포함) int supply(int kind) : kind 음료에서 가장 우선순위 높은 것 제조 (해당 손..

    삼성 소프트웨어 역량테스트 PRO등급 준비
    Algorithm

    삼성 소프트웨어 역량테스트 PRO등급 준비

    SAMSUNG Software PRO등급 준비 역량 테스트 단계 Advanced Professional Expert 시험 시간 및 문제 수 : 4시간 1문제 Professional 단계부터는 라이브러리를 사용할 수 없다. C/Cpp 경우, 동적할당 라이브러리인 malloc.h까지만 허용 또한 전체적인 로직은 구현이 되어있는 상태이며, 사용자가 필수적으로 구현해야 할 메소드 부분이 빈칸으로 제공된다. (main.cpp와 user.cpp가 주어지며, 우리는 user.cpp를 구현하면 된다) 크게 두 가지 유형으로 출제되고 있다. 실행 시간을 최대한 감소시켜 문제를 해결하라 쿼리 함수를 최소한 실행시켜 문제를 해결하라 결국, 최대한 효율적인 코드를 작성하여 시간, 메모리를 절약하는 것이 Professinal ..

    [알고리즘] 비트마스크(BitMask)
    Algorithm/개념 정리

    [알고리즘] 비트마스크(BitMask)

    비트마스크(BitMask) - 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉 왜 비트마스크를 사용하는가? - DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제 - 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함) - 집합을 배열의 인덱스로 표현할 수 있음 - 코드가 간결해짐 비트(Bit)란? 컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1) 2진법을 생각하면 편하다. 우리가 흔히 사용하는 10진수를 2진수로 바꾸면? 9(10진수) → 1001(2진수) 비트마스킹 활용해보기 - 0과 1로, flag 활용하기 [1, 2, 3, 4 ,5] 라는 집합이 있다고 가정해보자. 여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의..

    [알고리즘] 퀵소트(QuickSort) 구현 (C)
    Algorithm/개념 정리

    [알고리즘] 퀵소트(QuickSort) 구현 (C)

    수, 문자열 등 정렬이 필요한 상황에 퀵소트를 라이브러리 없이 구현하기 위함 정렬 조건 자체가 많더라도, while문 안에서 모두 해결이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include int arr[] = { 1, 10, 6, 9, 8, 2 }; void quickSort(int *, int start, int end); int main(void) { int size = sizeof(arr) / 4; printf("Before : "); for (i..

    [백준 1012] 유기농 배추 (C, DFS)
    Algorithm/백준(BOJ)

    [백준 1012] 유기농 배추 (C, DFS)

    문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 전형적인 DFS, BFS 기본 문제. C로 리마인드할겸.. 가로, 세로 입력은 순서 헷갈리지 않게 항상 주의하자~ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

    [백준 4963] 섬의 개수 (C)
    Algorithm/백준(BOJ)

    [백준 4963] 섬의 개수 (C)

    문제 링크 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net C언어로 연습할 겸 푼 문제. 새롭다 다시 익혀야겠다;; 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

    [프로그래머스] 베스트앨범 (Java)
    Algorithm

    [프로그래머스] 베스트앨범 (Java)

    문제 출처 : 링크 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play programmers.co.kr 장르와 노래는 해시 테이블을 직접 구현해 관리하고, 베스트앨범에 넣을 인덱스는 퀵소트를 만들어 뽑아냈다. 라이브러리 안쓰고 푸는 연습에 매우매우 좋은 문제..

    [백준 1197] 최소 스패닝 트리 (Java)
    Algorithm/백준(BOJ)

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

    MST를 통해 풀어야 하는 문제다. MST에는 크루스칼과 프림 두가지 방법이 있다. dense가 많을 때는 프림이 더 효율적이다. 10만개의 간선이 들어오므로 프림으로 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer..

    [알고리즘] LCA(Lowest Common Ancestor)
    Algorithm/개념 정리

    [알고리즘] LCA(Lowest Common Ancestor)

    [알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..

    [CodeForce Beta Round #4] C. Registration system
    Algorithm/CodeForce

    [CodeForce Beta Round #4] C. Registration system

    문제 출처 : 링크 Problem - C - Codeforces codeforces.com 문제 자체는 어렵지 않다. 처음으로 등록되는 문자열은 "OK"로 출력하고, 만약 똑같은 문자열이 또 입력되면 숫자를 붙여서 출력해야한다. ex) Input 4 abacaba acaba abacaba acab output OK OK abacaba1 OK abacaba가 3번째에 또 들어오면서 abacaba1로 출력하는 모습을 볼 수 있다. 만약 한번더 들어오면 abacaba2를 출력하면 된다. 이 문제는 시간초과에 빠지기 쉬운 문제다. 왜냐하면 N의 값이 1~100000이다. 만약 브루트포스로 진행하면 N^2으로 100억번의 연산을 해야하는데 문제에 주어진 제한 시간 5초로는 불가능하다. 이 문제는 따라서 해시 테이..

    [CodeForce Beta Round #4] B. Before an Exam
    Algorithm/CodeForce

    [CodeForce Beta Round #4] B. Before an Exam

    문제 출처 : 링크 Input으로 요일 수(d)와 최대 시간(sumTime)이 주어진다. 그리고 d만큼 하루에 공부할 수 있는 최소 시간과 최대 시간이 각각 한 줄씩 들어온다. 모든 요일에 주어진 최소 시간만큼은 공부를 해야 하고, 최대 시간과 일치하는 공부 시간을 출력해야 한다. 주어진 요일의 공부시간동안 최대 시간만큼 할 수 없으면 "NO"를 출력하고, 가능하면 "YES"와 함께 요일별 공부시간을 출력해야 한다. 예) 2 5 0 1 3 5 d = 2고, sumTime = 5다. 이틀동안 5시간의 공부를 해야한다. 첫째날은 0~1시간 공부를 할 수 있고, 둘째날은 3~5시간을 공부할 수 있다. 첫째날에 1시간 공부 & 둘째날에 4시간 공부 or 첫째날 0시간 공부 & 둘째날에 5시간 공부 두가지 경우로..

    [CodeForce Beta Round #4] A. Watermelon
    Algorithm/CodeForce

    [CodeForce Beta Round #4] A. Watermelon

    문제 출처 : 링크 아주 간단한 문제다. input 값이 들어오면, 2명이서 나눠가질 때 둘다 짝수 값으로 가질 수 있으면 'YES' 아니면 'NO'를 출력해야한다. 예를 들면 2는 1과 1로 밖에 못나눠서 NO 6은 2와 4로 나누면 짝수라 YES 7은 짝수로 나눌 수 없어서 NO N이 1~100 사이에 수가 들어오므로, 1이 아닌 경우에 둘로 나눈 값이 모두 짝수로 나오는 경우가 있는지 판단하면 된다. 나는 N이 들어오면, for문에서 N을 2로 나누고 1씩 감소하며 두 수가 짝수인지 체크하는 방식으로 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 package CodeForces; impor..

    [알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기
    Algorithm/개념 정리

    [알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기

    [알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기 사이클을 찾기 위해서는 DFS를 활용한다. (정점 : v, 간선 : e) - visited[] : 점들의 방문여부가 저장된 배열 - recur[] : v가 지금까지 방문한 점이 저장된 배열 for(v 수 만큼) { dfs(v, visited, recur) } DFS 수도코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 boolean dfs(v(a), visited, recur) { visited[v(a)] = true recur[v(a)] = true for(v(a)와 연결된 점의 수만큼) { b = 연결된 점 if(!visited[b] && dfs(v(b), visited, recur){ // b가 방문상태..

    [알고리즘] XOR 비트 연산을 활용하기
    Algorithm/개념 정리

    [알고리즘] XOR 비트 연산을 활용하기

    [알고리즘] XOR 비트 연산을 활용하기 비트 연산을 활용해서 문제에 적용하면 상당히 효율적으로 코딩이 가능한 경우가 있다. 특히 코딩테스트와 같이 문제를 풀 때 비트 연산을 활용하면 좋다. 이번에 살펴볼 예시는 보통 네이버나 카카오 등 프로그래머스를 이용해 코딩테스트를 보게 되는데, 테스트 환경에서 연습해보는 1번 문제로 등장하는 유형이다. 직사각형의 3개 점이 주어진다. 나머지 하나의 점의 좌표를 구하라. (직사각형은 항상 평행한 상태) ex) (2, 0) (6, 0) (6, 6) 정답 : (2, 6) 다양한 방법을 이용해 푸는 것이 가능하지만, 가장 신박했던 방법은 비트연산을 활용해 푸는 것이었다. XOR은 입력 값 중 하나만 true일 때 true를 리턴해준다. 따라서 주어진 3점의 x좌표와 y좌..

    [백준 3425] 고스택 (Java, 시뮬레이션)
    Algorithm/백준(BOJ)

    [백준 3425] 고스택 (Java, 시뮬레이션)

    [백준 3425] 고스택 (Java, 시뮬레이션) B형 역량테스트를 보기 하루 전이다. 인터넷 상에 추천문제로 나온 고스택 문제를 풀었다. 시뮬레이션이라 문제푸는 감을 익히기에 좋을 것 같다. 문제 : 출처 3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하 www.acmicpc.ne..

    [자료구조/Java] 이진탐색트리 (Binary Search Tree)
    Algorithm/개념 정리

    [자료구조/Java] 이진탐색트리 (Binary Search Tree)

    [자료구조/Java] 이진탐색트리 (Binary Search Tree) - 각 노드의 자식이 2개 이하인 트리 - 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 노드 삽입 시간 균등 트리 : 노드 개수 N개일 때 O(logN) 편향 트리 : 노드 개수 N개일 때 O(N) 삽입,검색,삭제의 시간복잡도는 트리 높이에 비례함 삭제가 조금 까다로움 (3가지 case) 1. 자식이 없는 leaf 노드면? → 그냥 지우면 끝 2. 자식이 1개인 노드면? → 지워진 노드에 자식을 올리면 끝 3. 자식이 2개인 노드면? - 자식 노드 중에서 삭제할 노드보다 크면서 가장 작은 값 - 자식 노드 중에서 삭제할 노드보다 작으면서 가장 큰 값 편향된 트리(ex. 정렬된 상태인 값을 트리로 만들면 한쪽으로 뻗는다)에서..

    [자료구조/Java] 힙(Heap) 구현
    Algorithm/개념 정리

    [자료구조/Java] 힙(Heap) 구현

    시간이 지나면 자꾸 까먹는다.. 그래서 다시 정리해봐야겠다 자료구조의 핵심 중 하나인 힙(Heap)에 대해 알아보자 힙(Heap) 완전 이진트리의 일종이다. 반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이기 때문이다. 힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다. 이를 통해 여러 값 중에서 최소 값이나 최대 값을 빨리 찾을 때 유용하게 이용할 수 있다. 힙 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다. 1번째 인..

    [백준 14889] 스타트와 링크 (Java)
    Algorithm/백준(BOJ)

    [백준 14889] 스타트와 링크 (Java)

    [백준 14889] 스타트와 링크 (Java) 문제 출처 : 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 SW역량테스트 기출 문제다. 정답률도 매우 높고, 실제로 다른 기출문제에 비해 상당히 쉬운편이다. 짝수로 주어진 사람 수를 2팀으로 나누고, 문제에 주어진 능력치 값을 구해 두 팀의 최소차를 출력해주면 된다. 조합을 짤 수만 있다면 간단히 해결이 가능하다. 조합에서 팀이 나누어지는 상황마다 각 팀의 능력치 값을 구하고 절대값을 구한다. 이 절대값 중 가장 작은 값을 출력하면 끝! 1 2 3 4 5 6 7 8 9 1..

    [백준 17140] 이차원 배열과 연산 (Java)
    Algorithm/백준(BOJ)

    [백준 17140] 이차원 배열과 연산 (Java)

    [백준 17140] 이차원 배열과 연산 (Java) 문제 출처 : 링크 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 올해 삼성 상반기 오후 기출 문제다. 처음에 글만 보고 문제를 이해하기 힘들었는데 테스트케이스 밑에 자세한 설명이 나와있었다. 실제로 역량테스트를 볼 때는 너무너무 자세한 예시가 나와있으니 문제 이해를 못할 걱정은 크게 걱정하지 않아두 된다ㅎㅎ 이처럼 행과 열의 사이즈를 비교해 숫자의 수만큼 배열을 확장해나가는 방식이다. 행의 길이가 열보다 더 크거나 같으면 → 방향으로 열의 길이..

    [백준 17142] 연구소3 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 17142] 연구소3 (Java, BFS)

    [백준 17142] 연구소3 (Java, BFS) 문제 출처 : 링크 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 올해 상반기 삼성전자 역량테스트 문제다. 예전에 나온 삼성 기출 '연구소'에서 조건만 좀 더 추가된 문제 3가지 조건만 잘 기억하고..

    [백준 17143] 낚시왕 (Java)
    Algorithm/백준(BOJ)

    [백준 17143] 낚시왕 (Java)

    [백준 17143] 낚시왕 (Java) 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 www.acmicpc.net 올해 상반기 삼성전자 SW역량테스트 기출문제다. 시뮬레이션으로, 주어진 문제를 잘 읽으면서 코드로 옮겨야 한다. 큰 진행 방향은 아래와 같다. 낚시왕이 오른쪽으로 한..

    Algorithm/개념 정리

    [Java] HashSet을 ArrayList로 변환하기

    [Java] HashSet을 ArrayList로 변환하기 HashSet set = new HashSet(); for (int i = 0; i < T; i++) { set.add(br.readLine()); } ArrayList list = new ArrayList(set); 중복되는 값을 제외하고 저장하고 싶은 경우가 존재한다. 이때 HashSet을 통해 저장한 뒤 ArrayList로 변환해주면 값을 뽑을 때 매우 유용하다

    [백준 11559] Puyo Puyo (Java, DFS)
    Algorithm/백준(BOJ)

    [백준 11559] Puyo Puyo (Java, DFS)

    [백준 11559] Puyo Puyo (Java, DFS) 문제 출처 : 링크 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 약간의 DFS와 시뮬레이션이 합쳐진 문제다. 이런 문제 또한 약간의 제한조건만 달라지면서 많이 출제된다. 가장 중요한 건, 문제를 잘 이해하고 제한 조건을 하나라도 놓치지 않고 구현해야 한다는 점. 코드를 짜기 전에 먼저 종이에 확실히 조건을 모두 이해하며 로직을 간단하게 짜고 진행하자. 1. 맨 아래부터 블럭이 쌓여있기 때문에, 배열에서 아래부터 체크하며 빈칸이 아닌 것(알파벳인 곳)을 list에 담는다. 2. list에 담은 걸 하나씩 뽑아 해당 위치에서 DFS를 돌리..

    [백준 2206] 벽 부수고 이동하기 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 2206] 벽 부수고 이동하기 (Java, BFS)

    [백준 2206] 벽 부수고 이동하기 (Java, BFS) 문제 출처 : 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 지난번에 포스팅한 미로만들기와 유사한 방법으로 접근해야하는 문제다. 이 문제의 정답률은 훨씬 낮은데, N과 M의 ..

    [백준 17135] 캐슬 디펜스 (Java)
    Algorithm/백준(BOJ)

    [백준 17135] 캐슬 디펜스 (Java)

    [백준 17135] 캐슬 디펜스 (Java) 문제 출처 : 링크 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 최근에 나온 따끈따끈한 문제 이 문제 또한 주어진 제한 조건을 잘 확인하고, 구현으로 옮기면 된다. 진행 방식을 요약하면 다음과 같다. 1. 궁수 3명을 배치하고 사정거리 안에 있는 가장 가까운 적병을 사격 2. 사격 진행 후 남은 적병들 아래로 한칸 전진 3. 적병이 모두 죽거나, 궁수 칸으로 이동해서 사라질 때까지 1~2번 반복 - 주의할 점 1. 만약 궁수에게 가장 가까운 적병이 2개 이상이면, 가장 왼쪽..

    [백준 16236] 아기 상어 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 16236] 아기 상어 (Java, BFS)

    [백준 16236] 아기 상어 (Java, BFS) 문제 출처 : 링크 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 삼성 코딩테스트 기출 문제인 아기 상어 문제를 읽고 이해할 때 여러 제한 조건을 잘 고려해서 구현해야 한다. 하나라도 놓치면 디..

    [백준 2665] 미로만들기 (Java, BFS)
    Algorithm/백준(BOJ)

    [백준 2665] 미로만들기 (Java, BFS)

    [백준 2665] 미로만들기 (Java, BFS) 문제 출처 : 링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 시작부터 끝이 정해져 있고, 시작 방부터 끝 방까지 방의 색을 최소로 바꿔서 이동시켜야 하는 문제다. BFS라는거는 바로 알 수 있지만, 단순하게 생각하면 까다로울 수 있는 문제다. 평소처럼 boolean으로 visit 배열을 만들어 체크하는 것이 아닌, int형으로 각 위치마다 방을 바꾼 횟수를 저장시키며 나아가는 방법을 익힌 문제..! 시작할 때 visit 배열을 모두 무한대 값으로 초기화 해두고..

    Algorithm/SWEA

    [SWEA 2117] 홈 방범 서비스 (Java)

    [SWEA 2117] 홈 방범 서비스 (Java) 문제 출처 : 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소프트웨어 모의 테스트 문제다. 시뮬레이션 문제로, 마름모를 구현할 수만 있으면 잘 풀 수 있다. (잘 생각이 안나서 더럽게 구현했음ㅜㅜ) 이익이 0 이상일 때를 체크해서 가장 많은 집의 수를 출력하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858..

    Algorithm/SWEA

    [SWEA 4050] 재관이의 대량할인 (Java)

    [SWEA 4050] 재관이의 대량할인 (Java) 문제 : 링크 입력 받은 수를 sort하면 작은 수부터 큰 수로 정렬된다. 뒤에서부터 3개씩 묶어서 할인을 받으면 가장 큰 할인 금액을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Solution_4050_재관이의대량할인 { static int N; static int[] arr; publ..

티스토리툴바