목록알고리즘 문제풀이 (29)

매일 매일 성장하는 섭섭군

[Seop's의 코드풀이] 백준 1043 거짓말 - Python

www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 요약 진실을 알고있는 사람과 연관된 파티에서는 거짓말을 하지 못한다. 즉 진실을 알고 있는 사람과 연관되어 있지 않은 그룹이 몇 개 있는지 파악해야 하는 문제이다. 문제의 예제 입력으로는 문제 파악이 힘들 수 있기 때문에 아래 예시를 함께 봐보자! 입력 4 3 1 4 2 1 2 1 3 2 4 3 4명의 사람과 3개의 파티가 존재한다. 진실을 알고 있는 사람은 1명이며 4번이 진실을 알고 있다. 위의 예시에서 4번 사..
알고리즘 문제풀이/백준 2020. 11. 28. 16:59
[Seop's의 코드풀이] 백준 9202 Boggle - Python

www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개�� www.acmicpc.net 문제 요약 이번 문제는 문제를 파악하는데에도 시간이 다소 걸렸다. 필자처럼 문제를 파악하기 힘드신 분들을 위해 사진으로 표현하면 다음과 같다. 단어목록과 보드가 주어지면 이 안에서 단어목록에 있는 단어들을 찾으면 되는 것이다. 주어진 보드에서 단어목록에 있는 단어를 모두 찾았다면 그 이후의 정답을 내는 작업은 매우 간단하다. 문제에서 하라는대로 하면 된다. 문제풀이 IDEA 문제를 해결하기..
알고리즘 문제풀이/백준 2020. 9. 12. 00:55
[Seop's의 코드풀이] 프로그래머스 줄 서는 방법 - Python

programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 문제 요약 서로다른 자연수 n 개를 나열하는 방법의 수 중 k 번째 수는 무엇인지 확인하는 문제이다. 모든 경우를 나열한 후 사전순으로 정렬 할 수 있지만 시간이 너무 오래 걸리는 문제가 발생한다. 그러므로 우리는 바로 K 번째 수를 구할 수 있어야 한다. 문제풀이 아이디어 서로다른 n개의 자연수로 이루어진 수열의 맨 앞자리가 수가 같은 경우는 한정되어 있다. ..
알고리즘 문제풀이/프로그래머스 2020. 8. 19. 20:24
[Seop's의 코드풀이] 프로그래머스 최고의 집합 - Python

programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr 문제요약 이번에 풀어볼 '최고의 집합'이란 문제는 s 라는 자연수를 n개의 자연수를 더해서 만드는 문제이다. 그 중에서 각각의 자연수의 곱이 가장 큰 경우를 찾는것이다. 그냥 단순하게 생각하더라도 모든 경우를 고려한다면 시간이 너무 오래 걸린다는 것을 알 수 있다. 그래서 n개의 자연수 중 합이 s면서 곱이 가장 크게될 값을 한번에 찾아야 한다. 문제풀..
알고리즘 문제풀이/프로그래머스 2020. 8. 19. 13:06
[Seop's의 코드풀이] 백준 1599 민식어 - Python

https://www.acmicpc.net/problem/1599 1599번: 민식어 첫째 줄에 민식어 단어의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄부터 한 줄에 하나씩 단어가 입력으로 들어온다. 단어의 길이는 최대 50자이다. 민식어에 없는 알파벳� www.acmicpc.net 문제 요약 이번 문제는 '민식어' 라는 문제이다. 문제를 요약하자면 다음과 같을것 같다. 민식어의 알파벳 순서는 "a b k d e g h i l m n ng o p r s t u w y" 순이다. 입력으로 들어온 단어를 민식어 알파벳 사전순으로 정렬하여 순서대로 출력한다. 문제풀이 IDEA 민식어 단어를 영어로 변환한다. Dict 테이블에 Key : 민식어 , Value : 영어 로 저장한다..
알고리즘 문제풀이/백준 2020. 8. 11. 17:20
[Leet Coding Challenge] Add and Search Word - Data structure design, 2020.08.01~07

leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3413/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제 요약 이번에 풀어볼 문제는 Add and Search Word - Data structure design 라는 문제입..
알고리즘 문제풀이/LeetCode 2020. 8. 6. 23:51
[Seop's의 코드풀이] 백준 10799 쇠막대기 - Python

백준 10799 쇠막대기 이번에 풀어볼 문제는 쇠막대기라는 문제입니다. 문제의 링크는 다음과 같습니다. 문제 바로가기 이번 문제는 알고리즘 분류가 스택으로 되어있어 스택을 사용하는 방식으로 문제를 해결했습니다. 문제해결 아이디어 기본적인 아이디어는 레이져가 쏴졌을때 몇개의 막대기를 자르는가 입니다. 이를 알아내기 위해 다음과 같은 방법을 사용했습니다. "("가 나올적에는 스택에 index를 저장합니다. "("가 나왔을때 막대기라고 판명되면(다음 문자열이 ")"가 아닐경우) 정답에 1을 추가합니다. "()" 레이져라 판명될 경우 현재 스텍의 크기를 정답에 더해줍니다. ")"가 나왔을 경우 스택에서 pop을 진행해 줍니다. 위와 같은 방식으로 문제를 해결하였으며 전체적인 코드는 다음 GitHub 링크에 있습..
알고리즘 문제풀이/백준 2020. 8. 2. 18:31
[Seop's의 코드풀이] 백준 5397 키로커 - Python

백준 5397 키로커 이번에 풀어볼 문제는 백준 5397번 키로커 라는 문제이다. 스택 알고리즘에 분류되어있고 solved.ac 랭크 실버3 정도의 문제이다. 문제는 다음과 같다.링크 내가 본 문제에서 중점적으로 본 것은 커서의 위치를 어떻게 컨트롤 하는지에 관련된 것이다. 커서의 위치를 기억하고 해당하는 위치에 비밀번호를 입력하고 삭제하게 된다면 굉장히 많은 시간을 낭비하게 될것이다. Python list에서 insert와 특정위치의 pop의 시간복잡도는 O(N)이다. 문제 해결 아이디어 하나가 아닌 두개의 스택을 사용한다.(stack1, stack2) 알파벳이 나왔을 경우 stack1에 쌓는다. "-"가 나올경우 stack1에서 pop을 진행한다. "" 가 나올경우 stack2에서 pop을 진행하고 ..
알고리즘 문제풀이/백준 2020. 8. 2. 17:59
Prev 1 2 3 4 Next