티스토리

시간이 NullNull

검색하기

블로그 홈

시간이 NullNull

4ngs.tistory.com/m

4NIng 님의 블로그입니다.

구독자: 6

방명록 방문하기

주요 글 목록

[JAVA] [SWEA] 1251. 하나로 ( union & find 설명까지 ) 본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다. 해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다. 이 문제의 경우... 참 애먹인 문제입니다. 처음 접했을때는 어떻게 풀지 몰랐다가 나중가서는 아 그냥 완탐하면 되겠네 했다가.... 그 다음에는 문제 자체를 이해 못하여서 다익스트라로 다 방문도 해봤다가... 최근에 다시 그래프 문제를 공부하면서 크루스칼과 Union Find 알고리즘을 공부하기 시작하면서 문제가 이해되기 시작하고 해결할 수 있게 되었다. Union Find의 개념을 다른 글에 포스팅 하기 보다 여기에 몰아서 한번에 적도록 하겠다. 나는 다른 블로그들을 많이 보면서 이해하였지만 .. 공감수 0 댓글수 0 2020. 8. 12.
[JAVA] [SWEA] 9843. 촛불 이벤트 당신은 프로포즈를 위해 촛불을 삼각형으로 배치하고 있다. 촛불을 K단 크기로 배치하면, 1단에는 K개의 양초, 2단에는 K-1개의 양초, …, K단에는 1개의 양초를 배치해서 총 (K(K+1))/2개의 양초가 필요하다. 당신이 사용할 양초의 개수 N이 주어질 때, 이 양초를 모두 사용하면 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구하여라. 처음에 문제만 읽었을때 만들수 있는 촛불의 단이 최대 몇인지 구하는 것인지 알고 잠깐 고민했으나 각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다. 출력에 이렇게 함정을 놔두어 헷갈리게 해두었다... 나만 그렇게 느끼나 처음에 문제만 보면 최대 몇개 만들 수 .. 공감수 0 댓글수 0 2020. 5. 13.
[JAVA] [SWEA] 9839. 최고의쌍 N개의 양의 정수가 주어졌을 때, 이들 중 정확히 서로 다른 두 개의 정수 쌍을 고르려고 한다. 이 때, 두 정수를 고르는 데 있어서 특별한 제약 조건이 존재한다. 고른 서로 다른 두 정수를 x, y라고 하면, 두 정수의 곱 x*y는 10진수로 읽었을 때 증가하면서도 연속한 숫자들로 이루어져야 한다. 예를 들어 2, 23, 23456, 56789는 제약 조건을 만족하고, 21, 54321, 67890, 89012, 88, 889, 79는 제약 조건을 만족하지 않는다. 이 조건을 만족하는 모든 쌍 중, 두 정수의 곱이 최대화되는 쌍을 “최고의 쌍” 이라고 부른다. 최고의 쌍이 존재하는지, 존재한다면 이 쌍의 곱은 얼마인지 계산하는 프로그램을 작성해보자. 1. 정수 중 중복하지 않게 2개를 뽑는다. 2. 곱.. 공감수 0 댓글수 0 2020. 5. 13.
[JAVA] [SWEA] 9940. 순열1 길이 N의 순열이란, 1부터 N까지의 자연수를 적당한 순서로 섞어서 만든 수열을 의미한다. 예를 들면, (3, 4, 1, 2)는 길이 4의 순열이다. (2, 3, 4, 4, 5)는 길이가 5이지만 1부터 5까지의 자연수를 적당한 순서로 섞어서 만들 수 없기 때문에 순열이 아니다. 어떤 길이 N의 수열이 주어지면, 이것이 길이 N의 순열인지 판단하여라. 너무 간단하다.. 컴파일러 없이도 그냥 메모장에 코딩하고 그대로 붙여서 제출하여도 통과할만큼 이건 D1, D2 문제이라 해도 믿을 것이다.... 사실상 순열이라고 하였지만 N을 입력받으면 1~N까지 숫자가 다 있는지 확인만 해주면 끝나는 문제이다.... 그래서 설명이랄 것도 없다.... 코드를 보세요... import java.io.BufferedReade.. 공감수 0 댓글수 0 2020. 5. 13.
[JAVA] [SWEA] 9480. 민정이와 광직이의 알파벳 공부 아기 광직이는 열심히 받아쓰기를 했지만, 아직 알파벳을 다 떼지 못했다. 아기 민정이는 그런 광직이가 반 친구들에게 놀림 받지 않을까 걱정이 되어 직접 학습지를 만들어 광직이에게 알파벳을 가르쳐 주려고 한다. (아기 민정이는 광직이보다 동생이지만, 알파벳을 잘 알고 있다.) 민정이는 광직이가 따라 적을 수 있도록 알파벳 연습용 단어 세트를 여러 개 만들 것이다. 광직이는 현재 N개의 영어 단어를 알고 있고, 이 중 몇 개를 골라 하나의 세트로 만드는데, 각 세트 안에 포함된 단어의 순서는 중요하지 않다. 광직이가 모든 알파벳을 골고루 공부할 수 있도록, 단어 세트에는 26개의 알파벳 소문자가 모두 포함되어 있어야 한다. 즉, 모든 알파벳 소문자에 대해, 단어 세트 안에 그 문자를 포함하는 단어가 적어도 .. 공감수 0 댓글수 0 2020. 5. 12.
[JAVA] [SWEA] 9700. USB 꽂기의 미스터리 정우는 USB 커넥터를 포트에 꽂고 있다. 정확히 꽂기 까지 다음과 같은 과정을 거친다. - 가장 처음 USB를 꽂을 때, p의 확률로 올바른 면으로 USB를꽂은 것이고 , (1 - p)의 확률로는 뒤집어서 USB를 꽂은 것이다. - 만약 올바른 면으로 USB를 꽂으면 q의 확률로 정상적으로 USB가 꽂히고, (1 - q)의 확률로는 꽂히지 않는다. USB가 뒤집어져 있다면 절대로 꽂히지 않는다. - USB를 꽂는 것을 실패하면 USB를 뒤집은 다음 다시 꽂는 것을 시도한다. 이 때, USB를 정확히 i번 뒤집었을 때 USB가 꽂힐 확률을 si 로 나타낸다. 정우는 지금까지 USB를 두 번이나 뒤집어야 USB가 제대로 꽂히는 놀라운 경험을 너무 많이 했고, 이런 상황이 얼마나 많이 일어날 수 있는지 알고.. 공감수 0 댓글수 0 2020. 5. 12.
[JAVA] [SWEA] 9778. 카드 게임 카드 게임을 좋아하는 승현이는 요즘 블랙잭에 빠져 있다. 잘생긴 승현이와 함께 블랙잭의 규칙을 알아보자! 블랙잭을 처음 시작할 때, 덱에는 2, 3, 4, 5, 6, 7, 8, 9의 가치를 가지는 카드가 각각 4장, 11의 가치를 가지는 카드(Ace) 4장, 10의 가치를 가지는 카드 16장 (Ten, Jack, Queen, King), 총 52장의 카드가 올려져 있다. 지금 승현이는 이미 N장의 카드를 뽑아서 덱에는 52-N장의 카드가 남아 있으며, 승현이는 여기서 카드를 한 장 더 뽑을 지 말지 고민하고 있다. 승현이는 덱에 남아있는 카드 중 하나를 뽑았을 때, "뽑은 모든 카드의 가치의 합이 21보다 크게 만드는 카드의 개수"가 "뽑았을 때 가치의 합을 21 이하로 만드는 카드의 개수"보다 크거나 .. 공감수 0 댓글수 0 2020. 5. 12.
[JAVA] [SWEA] 9317. 석찬이의 받아쓰기 아기 석찬이는 내년에 초등학교에 입학하지만 아직 알파벳을 떼지 못했다. 석찬이의 부모님은 그런 석찬이를 위해 알파벳을 공부할 수 있는 학습지를 구독하였다. 학습지에는 길이 N의 알파벳 대소문자로만 이루어진 문자열이 주어지는데, 석찬이는 대소문자를 제대로 구분해서 이 문자열을 받아 적어야 한다. 석찬이는 N 개의 문자를 받아 적는 데는 성공했지만, 틀리게 적은 문자들이 몇 개 보인다. 석찬이가 몇 개의 문자를 올바르게 받아 적었는지 세어보자. 그대로 비교를 해주면 끝난다! 사실 블로그 포스팅을 위해서 작성하는 것이지만 내 양심이 찔릴 정도로 너무 쉽다.... 아무도 이 글을 봐주지 않을 것이다. 하하하하하하 단 정말 조금이나마 효율?적으로 하기 위해 char로 비교하였다. import java.. 공감수 0 댓글수 0 2020. 2. 23.
[JAVA] [SWEA] 8821. 적고 지우기 진수는 어린 동욱이에게 숫자 공부를 시키고 있다. 진수는 숫자를 여러 번 말한다. 그러면 동욱이는 진수가 부르는 숫자를 공책에 적거나 지운다. 숫자를 적을 때는 공책에 그 숫자가 적혀 있지 않을 때이고, 숫자를 지울 때는 공책에 그 숫자가 적혀 있을 때이다. 처음 공책에는 어떤 숫자도 적혀 있지 않다고 할 때, 마지막에 공책에 적힌 숫자의 개수를 구하는 프로그램을 작성하라. ps. 왜 저렇게 비효율적으로 공부시킬까ㅠㅠ 불쌍한 동욱이 가장 쉽게 생각했을때 그대로 시키는 대로 반복하면 된다. 처음에 쓰여지지 않은 수 = false 이후 쓰여지면 true 다시 진수가 숫자 부르면 false 다시 진수가 숫자 부르면 true 전체 코드는 아래와 같다. import java.io.BufferedReader; im.. 공감수 0 댓글수 0 2020. 2. 23.
[JAVA] [SWEA] 8931. 제로 재현이는 재민이를 도와서 동아리 장부를 관리하고 있다. 재현이는 영수증을 모아서 동아리의 지출 금액을 세고 있고, 재민이는 재현이가 부르는 액수를 순서대로 적고 있다. 재현이는 가끔 잘못된 수를 부르는 실수를 하는데, 이 때마다 0을 외쳐서, 가장 최근에 재민이가 쓰고 지우지 않았던 수를 지우게 시킨다. 재현이가 모든 수를 부른 후 재민이가 받아 적은 수의 합은 무엇일까? ps. 정말 불쌍하게도 쓰고 지우고 쓰고 지우고를 반복하는 재민이를 위로해줍시다.... 이 문제의 경우 그냥 시키는 대로 코드를 작성하면 된다. 다만 최근에 쓴 것을 지우게 되는데 이때 가장 좋은 것이 stack이기 때문에 stack을 활용하여 코드를 작성해 보았다. 들어오는 수를 다 stack에 넣다가 0이 들어오면 pop을 해주면되.. 공감수 0 댓글수 0 2020. 2. 23.
[JAVA] [SWEA] 8457. 알 덴테 스파게티 선표는 가게에서 처음으로 스파게티 면을 샀다. 봉투에 적힌 정보에 따르면, 면을 정확히 B초 동안 삶아야 이상적인 상태의 면이 된다고 한다. 그러나 안타깝게도, 지금 선표집의 모든 시계는 고장이 났다. 그래서 가게에서 모래시계를 하나 사서 집으로 가려고 한다. 가게에는 N개의 모래시계가 있고, i번째 모래시계는 정확히 xi초를 측정할 수 있다. 모래가 다 내려오면 바로 모래시계를 뒤집는 것으로 2xi초, 3xi초, …도 측정할 수 있다. 그러나 나머지 시간은 측정할 수 없다. 선표는 모래시계로는 정확한 시간을 측정할 수 없을 것 같아서, 조금 타협하여 E초 정도의 오차를 허용하려고 한다. 그러므로, 어떤 하나의 모래시계를 구입하여 B – E초에서 B + E초 중 하나를 측정해낼 수 있으면 된다. 구입해도.. 공감수 0 댓글수 0 2020. 2. 23.
[JAVA] [SWEA] 8016. 홀수 피라미드 경표는 아래와 같이 삼각형 모양으로 숫자를 쌓기로 했다. 1층에는 1개, 2층에는 3개, 3층에는 5개, … 와 같이 쌓는다. 위와 같이 경표는 끝도 없이 피라미드를 쌓을 때, N층의 제일 왼쪽, 오른쪽에 쓰게 될 숫자가 무엇일지 예측해보자. 결국 숫자의 규칙을 찾으면 피라미드를 만들 필요도 없이 숫자를 바로 구할 수 있다. 어... 이 문제의 경우 사실 최대한 몇번째 줄인지를 나타내는 N에 대해서 연관지어서 생각한다면 금방 알 수 있다. Tip. 이런 문제의 경우 숫자가 매우 불규칙해 보이므로 1을 더하거나 빼고 그 숫자를 다시 무언가를 해보도록 하자 아래에는 이 문제의 소스 코드이다. import java.io.BufferedReader; import java.io.BufferedWriter; imp.. 공감수 0 댓글수 0 2020. 2. 23.
[JAVA] [SWEA] 9088. 다이아몬드 태영이는 N개의 다이아몬드를 가지고 있다. 각 다이아몬드 크기는 1 이상 10000 이하의 자연수로 나타낼 수 있다. 태영이는 N개의 다이아몬드 중 몇 개를 골라, 애인에게 선물로 주려고 한다. 한편, 태영이는 고른 다이아몬드의 크기가 뒤죽박죽이면 애인이 좋아하지 않을 것이라고 생각하여, 고른 다이아몬드 중 크기 차가 K 이하인 것들을 묶음으로 가져가려고 한다. (단, 묶음은 여러 묶음일 수 있다.) 태영이가 애인에게 선물할 수 있는 다이아몬드의 최대 개수는 얼마인가? 이 문제는 D4 답게 최소한의 효율만 생각하면서 풀었다. 완탐을 하더라도 가능은 할 것 같으나 별다른 좋은 수가 떠오르지 않아 적당히 효율만 챙기면서 하였다. 1. 완탐을 할 것이나 그나마 조금의 효율을 위해 다이아 크기의 min값과 ma.. 공감수 0 댓글수 0 2020. 1. 11.
[JAVA] [SWEA] 5648. 원자 소멸 시뮬레이션 1초에 한번씩 원자들이 움직이는데 충돌할 경우 그대로 에너지를 방출하고 소멸한다 이 때 방출된 에너지의 총합을 구하는 문제이다. 문제의 이름부터 아주 고정관념이 한참 생겨 무조건 시뮬레이션으로 풀어야지! 라는 생각에 여러번 틀렸던 문제이다. 하지만 생각해보면 충돌할 경우만 생각하여 에너지만 구해주고 끝내면 되는 문제이다. ( 시간이 무한히 흐른다면 ( 이 문제의 경우 최대 2000초(문제 내에서 시간) ) 충돌되지 않은 원자들은 밖으로 빠져 나간다. 빠져나간 원자들은 고려하지 않아도 된다. 이 원자들은 평생 만날 일이 없기 때문이다.) 주변에 어떤 친구는 0초부터 2000초 까지 for문을 통해서 모든 경우를 다해준 경우도 있었고 이전 포스트들에서 본 것처럼 또 충돌 나는 것들은 여러개의 Map을 통해서.. 공감수 0 댓글수 0 2019. 9. 4.
[JAVA] [BOJ] 17143. 낚시왕 음 이전의 미생물 격리를 풀고난 뒤 바로 풀었기 때문에 똑같은 조건에서 풀었는데 생각보다 효율이 좋지 않았다. 이러한 방법이 있다는 것을 참고만 하고 보시는 것을 추천드립니다. 1. 낚시꾼은 결국 j가 0일때 부터 j가 c-1일때 까지 잡는다 2. 상어 친구들이 움직인다. 정지한 좌표가 같을 경우 크기가 큰 상어가 작은 상어를 잡아 먹는다. ( 보통 상어가 커지게 하는 데 이 문제의 경우 상어의 크기는 항상 유지 된다.) 3. HashSet을 이용하여 잡아먹힌 상어를 제외하고 다시 list에 넣는다! 이 문제가 살짝 어려운 경우 이전 포스트인 미생물 격리를 한번 보고 온다면 이 설명이 더 편하게 이해가 갈 것이다. 예전과 다르게 왜 Queue가 아닌 list를 썼느냐고 물어본다면 예전에는 움직이고 서로 .. 공감수 0 댓글수 0 2019. 9. 4.
[JAVA] [SWEA] 2382. 미생물 격리 이 문제는 무려 5초를 주었다는 점과 N의 수가 작아 N*N을 하더라도 10000인 점 미생물의 수가 1000개 이하라는 점이 무조건 시뮬레이션이라는 생각이 들어 쉽게 풀게 되었다. 내가 사용한 변수들은 int[][] maxMap, int[][] dirMap, int[][] sumMap 이다 이름만 봐도 어떤 용도인지 알겠으나 나중에 더 자세히 설명하겠다. 1. m일 동안 진행하기 때문에 0~m-1까지 for문 돌기 2. 미생물이 합쳐지기도 죽기도 하기때문에 list가 아닌 Queue 사용 하였는데 하루동안 한칸만 움직여야 하기때문에 Q의 사이즈를 이용하여 그만큼만 for문을 돌아주었다. 3. 문제에 나와있듯이 한칸 움직인 후 배열의 가장 바깥쪽 칸들에 가면 크기를 반으로 줄이고 방향을 반대로 바꿔주었다.. 공감수 0 댓글수 0 2019. 9. 4.
[JAVA] [KAKAO] 셔틀버스 주요 포인트! 1. 09:00 부터 n회 t분 간격으로 역에 도착한다. 나의 경우 09:00 부터라는 것을 제대로 못봐 문제가 이해가 되지 않아 한참동안 고민을 하였다. 2. m명을 태우면 더이상 태울 수 없다 ( 단, 기다리고 있는 줄은 유지된다. ) 이를 기준으로 나는 그냥 단순히 09:00 부터 각 셔틀버스마다 태울 수 있는 만큼 태우자 그리고 끝난 뒤에 1. 마지막 버스에 m명이 가득 차 있다면 마지막에 탄사람보다 1분 일찍오자! 2. 마지막 버스에 자리가 빈다면 마지막 버스가 도착할 시점에 오도록 하자! 이를 구현하기 위해서 우선 크루들이 도착하는 시간을 오름차순으로 정렬해야한다. 그래야 시간 순으로 버스에 태울 수 있기 때문이다. 그리고 시간 계산과 대소관계 비교를 원활하게 하기 위해서 시간 .. 공감수 0 댓글수 0 2019. 9. 4.
[JAVA] [KAKAO] 자동완성 문제를 쉽게 설명하면 1. go, gone, guild 라는 String 배열이 주어지면 이를 학습시킨다. 2. g를 입력하였을때 go와 gone가 나오므로 한번에 자동완성이 안된다. 3. 하지만 go 까지 하면 문자가 다 ( 자동 ) 완성이 되었다. 4. gon까지 입력시 gon으로 시작하는 문자는 gone 뿐이므로 gone을 완성시켜준다. 5. gu까지 입력시 gu로 시작하는 문자는 guild 이기때문에 guild를 완성시켜준다. 따라서 g + o + g + o + n + g + u 가 되어 7번 입력시 문자가 전부 자동완성 된다. 이를 풀기 위해서 지난번에 소개했던 Trie 알고리즘을 썼으며 1. 문자가 주어지면 Trie 트리를 만들고 2. 다음번에 문자 하나씩 읽으면서 ( 자동 ) 완성이 될때까지.. 공감수 0 댓글수 0 2019. 9. 4.
[JAVA] [BOJ] 5052. 전화번호 목록 ver.2 Trie Trie로 검색 혹은 이 글을 보러 오신 분은 전화번호 목록에 대해서 알 것이라고 생각하고 문제 설명은 넘어가겠습니다. 그리고 sort의 경우 본인이 구현하셔도 상관없지만 이 글에서 Point의 경우 Trie 이기에 라이브러리를 활용하였습니다. ( 그리고 sort의 경우 해주지 않으면 9112 다음에 911이 들어오면 문제가 발생하여 sort 해주었습니다. ) Trie의 개념의 경우 제가 이전에 써두었던 글을 참고하시면 더 이해가 잘 가실 것 같습니다. 글 링크 따윈 저는 상남자니까 걸어두지 않을께요 이 문제는 저번 문제와 다르게 번호가 들어왔을때 ( 예를 들어, 911 이 입력되었고 다음줄에 9112가 들어오면 ) 911 때문에 isTerminal이 true 인 상황에서 현재 자식노드의 2번 이 nul.. 공감수 0 댓글수 0 2019. 8. 24.
[JAVA] Trie 알고리즘 java 트라이 알고리즘, Trie 알고리즘 등등으로 검색해서 오신 분들은 귀찮더라도 개념 자체는 다른 분들이 친절하게 그림까지 다 그려가면서 설명을 잘 해놓았기 때문에 다른 분들 글과 그림을 보면서 설명을 듣고 오시길 바랍니다! 사실 저도 엄청 검색을 해보고 많은 글을 보고 했었는데 먼가 진짜 쉽게 짜놓은 트라이 알고리즘은 없어서 이 새벽에 미친 듯이 고민해가며 트라이를 짜왔습니다. 문제는 SW Expert에 문자열 교집합이라는 문제를 참고로 하였고 사실 이 문제는 트라이로 풀면 메모리가 오버되어 절대로 풀 수가 없습니다. ㅎ.... 이거 때문에 왜 런타임 에러일까 하면서 한참을 고민했네요 B형을 준비하시는 분들은 LinkedList를 구현하는 것을 먼저 보고 오시길 추천드리며 LinkedList를 아.. 공감수 0 댓글수 0 2019. 8. 24.
[JAVA] [BOJ] 5525. IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) 문제는 매우 간단하지만 어떻게 확인하느냐를 가지고 매우 고민했다. 처음에 I를 찾으면 내가 원하는 IOIOI 등등이 맞는지 확인하였으나 전체 배열을 돌면서 확인하기때문에 엄청난 횟수를 돌게 된다. ( for문만 돌게되면 충분히 가.. 공감수 0 댓글수 0 2019. 8. 23.
[JAVA] [BOJ] 17406. 배열돌리기 4 문제를 요약을 하면 1. 배열이 입력으로 들어온다. 2. 회전하는 명령어가 입력으로 들어온다. 3. 회전하는 명령어를 순서를 바꾸면서 실행하여 최소값을 찾는다. 참고로 저는 제 코드를 참고하시지 않는 것을 추천드립니다.... 정말 힘들게 짰어요 회전하는 명령어의 경우 중심점의 좌표와 좌표로부터의 거리? 좌표부터의 가로 혹은 세로 길이를 나타내고 무조건 시계방향으로 돌리면 된다. 나의 경우.... 정말 힘들게 생각했는데 문제를 풀 당시 시계방향으로 돌면서 모든 것을 돌리는 방법을 찾지 못했고 따라서 한줄씩 하면 어떨까라는 생각으로 풀었다. 코드를 보면 ( 이해하기 힘들지만....) 중심점을 기준으로 위의 가로줄, 밑의 가로줄, 오른쪽의 세로줄, 왼쪽의 세로줄을 하였고 이 경우 명령어가 (3,4,2) 일때 .. 공감수 0 댓글수 0 2019. 8. 20.
[JAVA] [BOJ] 5052. 전화번호 목록 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 처음에 이 문제를 보고 TRIE 알고리즘을 떠올렸으나... 오늘 더 공부해보면서 약간 느낌만 알았으므로 다른 방법으로 푼 방법을 올리겠습니다. 이 문제의 경우 사실 시간만 충분하다면 모든 경우를 다.. 공감수 0 댓글수 0 2019. 8. 20.
[JAVA] [BOJ] 2468. 안전 영역 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 처음에 그 높이만 물에 잠기는 줄 알고 많이 틀렸었다. 문제를 잘 읽도록 하자... ( 오랜만에 알고리즘 하니까 재미는 있지만 어렵네요 ㅠ ) 1. 생각해보면 비가 내리지 않았을 경우? 혹은 최소 높이보다 비가 작게 내렸을 경우? 안전 영역의 최소 값은 1이 된다. ( Key point) ( 내 생각에는 문제의 오류라고 생각한다. 최소 높이가 1이라면 비가 내리지 않았다가 된다. ) ( 이 생각 때문에 몇번 틀렸다. ) 2. 비는 최소 높이 부터 최고 높이의 - 1 까지만 내리는 것을 확인하면 된다. ( 최고 높이 이상으로 내릴 경우 어차피 안전영역은 0 이다. 최소 안전 영역이 1이 되는 것을 위배한다. ) 3. .. 공감수 0 댓글수 0 2019. 8. 14.
[JAVA] [SWEA] 7584. 자가 복제 문자열 문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다. 복제하는 방법은 다음과 같다. P0 = “0” Pi+1 = Pi + “0” + f(g(Pi)) 여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다. 예를 들어서, f(“10110”) = “01001”이다. g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다. 위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라. P1 = “001” P2 = “0010011” P3 = “001001100011011” 위와 같이 복제가 이루어질 것이다. 따라서 3번째 문자는 1, 7번째 문자는 1, 10번째 문자는 0이다. 이 문제는 문자들의 규칙을 보고 점화식만 세워서 .. 공감수 0 댓글수 0 2019. 6. 4.
[JAVA] [SWEA] 7728. 다양성 측정 숫자는 다양성을 가지고 있다. 다양성이란, 숫자를 구성하는 수의 종류를 의미한다. 예를 들어서 1512 라는 숫자는 ‘1’, ‘5’, ‘2’로 구성되어 있기 때문에 다양성이 3이다. 숫자가 주어졌을 때 그 숫자의 다양성을 구하는 프로그램을 작성하라. 이 문제의 경우 단순하게 다양성이 최소 1 ~ 10이란 것을 알 수 있다. 이를 이용하여 boolean[] 배열 10개를 만들어서 아직 숫자가 나오지 않았을 경우( boolean 배열의 값이 false 인 경우 ) cnt를 증가시키면 된다. 이를 코드로 나타내면 간단하게 다음과 같이 나온다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader.. 공감수 0 댓글수 0 2019. 6. 4.
[JAVA] [SWEA] 4301. 콩 많이 심기 콩을 사랑하는 민석이의 취미는 n*m 크기의 사각형 밭에 콩을 늘어놓는 것이다. 한 칸에 콩 하나씩을 놓을 수 있는데, 2가 싫은 민석이는 콩들 사이의 길이가 2가 되지 않도록 하면서 최대한 많은 콩을 놓으려고 한다. 예를 들어 다음과 같이 콩을 배치할 수 없다. 콩1(x1, y1)과 콩2(x2, y2) 사이의 길이는 이다. 민석이를 도와서 사각형 밭에 최대로 콩을 늘어놓자. 이 문제의 경우 처음에는 콩을 배치하고 규칙을 위반하였는지 확인하여하지 않았다면 모든 경우 중에서 규칙을 위반하지 않고 콩이 최대로 많은 경우가 생길 때 콩의 개수를 세는 것이라 생각하였다. 하지만 밑에 가로와 세로의 길이가 주어지게 되는데 최대가 각각 1000이며 이경우 1000 * 1000 이 되어 결국 모든 경우를 다 보기엔 .. 공감수 0 댓글수 0 2019. 6. 1.
[JAVA] [SWEA] 3234. 준환이의 양팔저울 준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다. 모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고, 여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다. 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. 예를 들어 무게추가 총 3개, 무게가 각각 1, 2, 4 라고 하면 아래 그림처럼 총 15가지 경우가 나올 수 있다. 이런 방법으로 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 이 문제의 경우 앞 문제에서 언급한 DFS에서 static field를 많이 언.. 공감수 0 댓글수 0 2019. 5. 13.
[JAVA] [SWEA] 4613. 러시아 국기 같은 깃발 2016년은 삼성전자가 러시아 현지법인을 설립한지 20주년이 된 해이다. 이를 기념해서 당신은 러시아 국기를 만들기로 했다. 먼저 창고에서 오래된 깃발을 꺼내왔다. 이 깃발은 N행 M열로 나뉘어 있고, 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다. 당신은 몇 개의 칸에 있는 색을 다시 칠해서 이 깃발을 러시아 국기처럼 만들려고 한다. 다음의 조건을 만족해야 한다. 위에서 몇 줄(한 줄 이상)은 모두 흰색으로 칠해져 있어야 한다. 다음 몇 줄(한 줄 이상)은 모두 파란색으로 칠해져 있어야 한다. 나머지 줄(한 줄 이상)은 모두 빨간색으로 칠해져 있어야 한다. 이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라. 첫 번째 예제이다. 왼쪽에 있는 그림이 입.. 공감수 0 댓글수 0 2019. 5. 13.
[JAVA] [SWEA] 4796. 의석이의 우뚝 선 산 의석이는 동서 방향으로 늘어서 있는 산의 N개의 지점에 대한 높이를 측정했다. 서쪽에서 i번째 지점을 i번 지점이라고 하고, 이 지점의 높이는 hi이다. 특이하게도 두 지점이 같은 hi을 가지는 경우는 없었다. 의석이의 친구 상원이가 의석이에게 “우뚝 선 산”이 몇 개인지 찾는 게임을 제안했다. 어떤 두 지점 i,j(1≤i＜j≤N) 사이에 있는 모든 지점을 볼 때, 즉 구간 [i,j]에 대해 이들의 높이의 형태가 “우뚝 선 산”이라는 것을 다음과 같이 정의하기로 했다. 다음을 만족하는 k(i＜k＜j)가 존재해야 한다. i≤l＜k인 모든 l에 대해 hl＜h(l+1)이 성립. k≤l＜j인 모든 l에 대해 hl＞h(l+1)이 성립. 이와 같은 정의에서 두 지점 i와 i+1사이는 우뚝 선 산이 될 수 없음에 주.. 공감수 0 댓글수 0 2019. 5. 11.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.