분류 전체보기

    백준 20365 - (Java) 블로그2
    알고리즘/백준

    백준 20365 - (Java) 블로그2

    https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 1. 유형 그리디 2. 문제 접근 아래와 같은 예시를 들어봅시다. 연속하는 색끼리 묶음을 만듭니다. B는 3개, R은 2개가 됩니다 더 개수가 많은 것이 기준이 됩니다. 즉 B로 전체를 한번 색칠하고, R을 부분 색칠해주면 됩니다. 그래서 B의 전체 색칠(1번) + R의 부분색칠(2번) = 3번이 정답이 됩니다. 3. 코드 import java.util.*; import java.io.*; pu..

    백준 16926 - (Java) 배열 돌리기1
    알고리즘/백준

    백준 16926 - (Java) 배열 돌리기1

    https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 1. 유형 구현 2. 문제 접근 사격형의 4개의 귀퉁이를 설정해 줍니다 사각형의 크기가 줄어들 때, 4개의 좌표를 다시 설정해줍니다 저것을 R번만큼 반복하면 종료 2번째 풀이. 저는 위처럼 사각형의 4개의 좌표를 구해서 해결했지만, 변수가 4개가 필요하고 각 방향마다 for문을 써줘서 코드가 더럽습니다...

    백준 15565 - (Java) 귀여운 라이언
    알고리즘/백준

    백준 15565 - (Java) 귀여운 라이언

    https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 1. 유형 투포인터 2. 문제 분석 시뮬레이션 위와 같이 시뮬레이션을 돌리면 푸는것이 가능합니다. 오른쪽이 증가하는 중(rflag == true)이면, 합을 감소시키고, 길이를 갱신 그리고 왼쪽 포인터를 증가시키기 위해 lflag=true를 시켜줍니다. 2번째 풀이 위 처럼 구하면 코드도 더럽고, 변수도 많이 필요합니다. 그래서 라이언의 인덱스만 따로 리스트에 저장. 그러면 {0, 4, 6,..

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

    백준 13902 - (Java)개업 2

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

    프로그래머스 - 메뉴 리뉴얼
    알고리즘/프로그래머스

    프로그래머스 - 메뉴 리뉴얼

    https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 유형 브루트포스, 부분집합 문제분석 orders의 요소별로 모든 조합의 갯수를 구해줍니다. 1번 태스트케이스를 예시로 보면, ABCFG에서 course의 길이가 2, 3, 4니깐 각 길이에 맞는 조합을 모두 구해줍니다. 그리고 HashMap자료구조를 통해 {문자열: 갯수} 형태로 넣어줍니다. 코드를 보면 현재 인덱스를 선택하고, 인덱스+1로 재귀를 호출함으로써 중..

    백준 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까지 가..

    [Java] 스프링 컨테이너와 싱글톤 컨테이너
    웹/백엔드, Spring

    [Java] 스프링 컨테이너와 싱글톤 컨테이너

    이전 시간에 이어서 DI, IoC컨테이너를 스프링 컨테이너로 바꿔봅시다. 목차 컨테이너 생성 과정 컨테이너 생성 방법 싱글톤 패턴 스프링 컨테이너란? 프레임워크를 사용해서 빈을 생성하고 관리하는 저장소 종류 스프링 컨테이너는 BeanFactory와 ApplicationContext가 있습니다. 둘의 구분은 상속관계를 보면 알 수 있듯이 ApplicationContext가 더 기능이 많습니다. 생성 방법 컨테이너 생성 빈 등록 먼저 컨테이너를 생성해봅시다. ApplicationContext ac = new AnotationConfigApplicationContext(AppConfig.class); //AppConfig클래스를 스프링 컨테이너로 등록하겠다. 그러면 빈 이름과 객체로 구성된 저장소가 생성됩니다..

    [Java] IoC, DI, 컨테이너
    웹/백엔드, Spring

    [Java] IoC, DI, 컨테이너

    IoC(Inversion of Control)란? 제어의 역전이라는 뜻입니다. 프로그램의 흐름을 개발자가 아닌 프레임워크가 제한하는 것을 말합니다. 말로는 잘 이해가 안되니 코드로 설명하겠습니다. 주문 시스템 클래스 다이어그램 OrderServiceImpl 클래스 public class OrderServiceImpl implements OrderService { private final DiscountPolicy discountPolicy; public OrderServiceImpl(DiscountPolicy iscountPolicy) { this.discountPolicy = discountPolicy; } ... } AppConfig 클래스 public class AppConfig { public O..

    [Java] Spring과 SOLID - 2편
    웹/백엔드, Spring

    [Java] Spring과 SOLID - 2편

    이전 게시글에 이어서 OCP와 DIP에 대해서 설명하겠습니다. 목차 OCP, DIP정의 위반 사례 해결방안 정의 OCP(Open/closed priciple) : 확장에는 열려있으며 변경에는 닫혀있습니다. DIP(Dependency inversion priciple) : 추상화에만 의존해야지, 구체화에 의존하면 안 됩니다. 이 정의만 봐서는 잘 이해가 안 됩니다. 따라서 코드를 가지고 설명하겠습니다. 회원 도메인입니다. 기능은 보시는 대로고, 회원 정보를 메모리에 저장 할 수도 있고, DB나 외부 시스템을 사용할 수 있기 때문에 미확정입니다. 클래스 다이어그램입니다. 그럼 위의 클래스 다이어그램의 MemberServiceImpl을 구현해봅시다. public class MemberServiceImple i..

    [Java] Spring과 SOLID - 1편
    웹/백엔드, Spring

    [Java] Spring과 SOLID - 1편

    이번에는 스프링과 SOLID에 대해서 알아봅시다. 목차 스프링이란? 객체지향이란? SOLID란? 서론 저는 엔테크서비스 인턴 면접중 이런 질문을 받았습니다. "스프링에 대해서 설명해주세요." 스프링에 대해서 잘 안다고 할 순 없지만 그래도 관련 플젝 경험이 몇 번 있기 때문에, 자신있게 대답했죠. "웹 서버를 만들기 쉽게 하기위한 라이브러리들의 집합이며, DB 연결도 편리하게 해주는 역할을 합니다. 또한 유지보수 측면에서 효과적이고, 기본적인 구조는 동일하기 때문에 개발자들 끼리 의견공유가 쉬워집니다..." 틀린 말은 아닙니다. 그 당시엔 정답이라고 생각했지만, 지금 생각해보면 면접관이 원하는 답은 아니라고 생각합니다. 결정적으로 면접관 얼굴표정도 그닥 만족스럽지 않았구요. 그래서 이번 기회에 다시 한번..

    [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..

티스토리툴바