이 글은 Vision-Language-Action Models 논문을 읽으며, VLA가 왜 등장했고, 기존 Vision-Language Model과 무엇이 다른지를 정리하기 위해 작성되었습니다. 논문을 보며 메모한 내용들을 나열한 것이기에 다소 거친 면이 있으며 실제 논문과 같이 보면 더 따라가기 쉽습니다.

AI가 ‘보고 이해하는 것’을 넘어 실제 행동으로 연결되기 위해 어떤 구조가 필요한지를 중심으로 살펴보고자 하며 VLA 분야에 대해 처음 접하는 사람들을 위해 최대한 관련 개념들도 풀어서 작성했습니다.

부정확한 내용이 있다면 댓글로 비판해주시면 감사하겠습니다.

Paper Information

Title: Vision-Language-Action Models: Concepts, Progress, Applications and Challenges Authors: Ranjan Sapkota, Yang Cao, Konstantinos I. Roumeliotis, Manoj Karkee arXiv ID: 2505.04769
Topic: Vision-Language-Action Models, Robotics, Embodied AI, AI Agents

최근 Vision-Language Model (VLM)은 기계가 이미지와 텍스트를 함께 이해하게끔 하는 방향으로 기여를 했지만, 실제 세계에서 움직이고 상호작용해야 하는 로봇이나 embodied agent에게는 단순한 이해만으로는 부족했습니다.

예를 들어, 모델이 “빨간 사과”를 인식하고 “사과를 집어라”라는 문장을 이해하더라도, 그 사과를 향해 팔을 움직이고, 적절한 힘으로 잡고, 상황 변화에 따라 동작을 수정할 수 없다면 실제 행동을 수행하는 agent라고 보기는 어렵습니다.

이러한 문제의식에서 등장한 개념이 바로 Vision-Language-Action Model(VLA)입니다.

1. Introduction

VLA가 발전되기 전 robotics와 AI 분야의 발전 양상

각각의 시스템은 잘 작동하지만 정작 시스템을 통합하려니 안되고 새롭거나 예측할 수 없는 상황이 벌어지면 작동을 못함

1.1. 각자 따로 놀던 시대

1. VIsion System : See and recognize images
   • extensive labeled datasets
   • cumbersome retraining for even slight shifts in environment or objectives
   • Lacked any understanding of language
   • Lacked the ability to convert visual insifgts into purposeful actions
2. Language System : understand and generate text
   • restricted to processing language without tcapability to perceive or reason about world
3. Action System : control movement
   • relying heavily on hand-crafted policies or reinforcement learning
   • demaned painstaking engineering
   • failed to generalize beyond narrowly scripted scenarios

1.2. 통합을 시도한 시대

• VLM (Vision-Language Model): Vision + Language
  • inability to generate or execute coherent actions based on umltimodal input

Vision-Language, Language-Action, Vision-Action 처럼 두개의 요소에 대한 System에 대한 통합이 다였음

→ Fragmented Pipeline architecture에 그침 → brittle generalization and labor-intensive engineering efforts

이게 문제인 이유가 embodied AI같은 분야에서 인지와 이해 그리고 액션이 통합되어 작동하는 시스템이 없다보니 발전 측면에서 병목현상을 발생시킴

→ VLA의 필요성 대두됨

VLA라는 컨셉 자체는 이미 2021년 - 2022년에 대두된 주제로 Google DeepMind’s Robotic Transformer 2 (RT-2)와 같은 모습으로 연구되어온 주제로 연구되어왔음 그래서 VLA는 결론적으로 vision inputs, language comprehension, moto control capabilities를 통합하여 embodied agent의 상황과 복잡한 지시에 대한 이해 및 실행을 가능하게 함

[224] Zitkovich, B., Yu, T., Xu, S., Xu, P., Xiao, T., Xia, F., Wu, J., Wohlhart, P., Welker, S., Wahid, A., et al., 2023. Rt-2: Vision-language-action models transfer web knowledge to robotic control, in: Conference on Robot Learning, PMLR. pp. 2165–2183.

1.3. Early VLA Approaches

1. Extending vision-language models to include action tokens — numerical or symbolic representations of robot motor commands
   • 모델이 서로 대응되어 묶여 있는 시각 데이터, 언어 데이터, 궤적 데이터로부터 학습할 수 있게 했다.
   • 학습 과정에서 못본 객체에 대한 일반화 (Generalize to unseen objects),
   • 새로운 명령어에 대한 변환 (interpret novel language commands),
   • 비구조화된 환경에서의 다중 단계 추론이 가능하게 됨 (perform multi-step reasoning in unstructured environments)

2. Concepts of Vision-Language-Action Models

What constitutes a VLA model, its historical evolution, multimodal integration mechanisms, and language-based tokenization and encoding strategies

VLA =

• Vision Encoders (e.g. CNNs, ViTs) +
• Language models (e.g. LLMs, Transformers) +
• Policy modules or planners to achieve task-conditioned control

⇒ multimodal fusion techniques를 활용한 결합 (e.g. cross-attention, concatenated embeddings, token unification)

VLA는 traditional visuomotor pipelines와는 다르게 sematic grounding , context-aware reasoning, affordance detection, temporal planning 이 가능했음

❓ traditional visuomotor pipeline

: 시각 인식과 행동 제어가 모듈별로 나뉜 로봇 제어 방식

이미지 입력 → 물체 인식/위치 추정 → 계획 수립 → 제어 명령 생성 → 로봇 실행

2.1. 발전 양상 (Evolution and Timeline)

2.1.1. Foundational Integration (2022-2023)

1. basic visuomotor coordination을 modal fusion architectures를 통해 Early VLA를 구현함

   • CLIP embedding을 motion primitives와 함께 결합

     [141] Reed, S., Zolna, K., Parisotto, E., Colmenarejo, S.G., Novikov, A., Barth-Maron, G., Gimenez, M., Sulsky, Y., Kay, J., Springenberg, J.T., et al., 2022. A generalist agent. arXiv preprint arXiv:2205.06175 .

     → 604개의 다양한 작업에서 범용적으로 작동할 수 있는 능력을 보였다. (Generalist Capabilities)

     → Transformer-based planner를 통해 시간적 추론(temporal reasoning)능력을 보여줌

     Temperal reasoning : 작업을 시간 순서에 따라 이해하고, 여러 행동을 단계적으로 연결하는 능력

2. 2023년에는 visual chain-of-though reasoning을 구현하고

   visual chain-of-though reasoning: 이미지/장면을 보고, 바로 행동하지 않고, 중간 추론 단계를 거쳐 행동을 결정하는 능력

   → vision을 기반으로 한 단계적 reasoning

   [224] Zitkovich, B., Yu, T., Xu, S., Xu, P., Xiao, T., Xia, F., Wu, J., Wohlhart, P., Welker, S., Wahid, A., et al., 2023. Rt-2: Vision-language-action models transfer web knowledge to robotic control, in: Conference on Robot Learning, PMLR. pp. 2165–2183.

3. stochastic action prediction을 diffusion process를 통해 발전시켰다

   stochastic action prediction: 행동을 하나의 정답처럼 고정해서 예측하는 것이 아니라, 가능한 여러 행동 분포에서 샘플링하거나 생성하는 방식

   diffusion process: 처음에는 노이즈에 가까운 상태에서 시작해서, 점점 의미 있는 결과로 정제해 나가는 방식

   이상한 움직임 후보 (무작위 행동 궤적)

   → 장애물 피하기 → 손목 방향 조정

   → 컵을 안정적으로 잡는 경로 (자연스러운 로봇 동작 궤적)

   [34] Chi, C., Xu, Z., Feng, S., Cousineau, E., Du, Y., Burchfiel, B., Tedrake, R., Song, S., 2023. Diffusion policy: Visuomotor policy learning via action diffusion. The International Journal of Robotics Research , 02783649241273668.

• 최종적으로 low-level control을 해결했지만, Lacked compositional reasoning 문제가 있었음

  ❓ lacked compositional reasoning

  개별 개념은 알아도 그것들을 조합해 새로운 복합 작업을 해결하지 못하는 문제
  → 실제 로봇 환경의 명령과 상황이 대부분 조합적이고 매번 조금씩 다르다.

3.1.2. Specialization and Embodied Reasoning (2024)

Second-generation VLA는 domain-specific inductive biases를 활용했다.

→ 범용 모델 하나로 다 해결하기 보다는, 특정 도메인에서 잘 작동하도록 구조적 힌트(inductive bias)를 넣기 시작했다

• Enhanced few-shot adaptation through retrieval-augmented traing

  retrieval-augmented는 모델이 모든 것을 내부 파라미터에 기억하는 대신, 비슷한 예시나 지식을 외부 데이터베이스에서 찾아와 참고한다

  Inductive Bia: “로봇 작업은 과거의 유사한 조작 경험이 새 작업에 도움이 된다”

• optmized navigation via 3D scene-graph integration

  공간을 노드와 관계(edge)로 표현

  Inductive Bia: “내비게이션에서는 픽셀 자체보다 “어디에 무엇이 있고, 어떤 공간이 연결되어 있는가”가 중요하다”

• introduced reversible architectures for memory efficency

  중간 계산값을 전부 저장하지 않고도 역방향 계산을 할 수 있게 만든 구조

  → backpropagation시 메모리 사용량 감소 → 더 큰 모델이나 긴 sequence 처리 가능

  Inductive Bia: “긴 시간 흐름과 여러 모달리티를 처리하려면 메모리 효율성이 중요하다”

• addressed partial observability with physics-informed attention

• improved disentanglement

  “빨간 컵”을 볼 때 → 빨간색 = color, 컵 = object category, 잡을 수 있음 = affordance, 테이블 위 = spatial relation → 하나의 물체를 개념에 따라 분리해서 다각화 이해 (뭉뚱그려 이해하지 않는다)

• extended applications to autonomous driving via multi-modal sensor fusion

⇒ required new benchmarking methodologies (기존 평가 방식으로는 VLA의 성능을 제대로 평가할 수 없게 되었다)

2024년 VLA는 단순히 vision-language-action을 연결하는 수준을 넘어서, 로봇 조작, 내비게이션, 물리 환경, 자율주행 같은 특정 도메인의 구조적 지식을 모델에 반영하면서 더 잘 일반화하고 더 안정적으로 행동하도록 발전

3.1.3. Generalization and Safety-Critical Deployment (2025)

2025년부터는 robustness와 human alignment를 중요시하고 있음

• human alignment는 모델이 명령을 수행하는 것을 넘어서, 사람이 의도한 바와 안전 기준에 맞게 행동하도록 조정되는 것

• Integrated Formal verification for risk-aware decisions
• Demostrate Whole-body control을 hierachical VLA로 구현

[42] Ding, P., Ma, J., Tong, X., Zou, B., Luo, X., Fan, Y., Wang, T., Lu, H., Mo, P., Liu, J., et al., 2025b. Humanoid-vla: Towards universal humanoid control with visual integration. arXiv preprint arXiv:2502.14795 .

Effect

• embedded 개발 환경에서 계산 효율성을 최적화하기도 함

• Affordance chaing과 sim-to-real transfer learning과 같은 paradigm이 제시되면서 cross-embodiment challenge를 해결함

  • affordance는 어떤 물체가 제공하는 행동 가능성

  • affordance chaining은 복잡한 행동을 “무엇을 어떻게 사용할 수 있는가”의 연쇄로 나누어 수행하는 방법

    e.g. 문을 열고 방에 들어가라 : 문손잡이를 찾는다 → 손잡이를 잡는다 → 돌린다 → 문을 민다 → 열린 공간으로 이동한다

  • sim-to-real transfer learning은 시뮬레이션에서 학습한 능력을 실제 로봇 환경으로 옮기는 학습 방식

  • cross-embodiment challenge는 한 로봇에서 배운 능력을 다른 로봇에 옮기기 어렵다는 문제

• Natural Language Grounding을 통해 VLA와 Human-in-the-loop interfaces를 연결

  • human-in-the-loop는 사람이 시스템의 판단이나 실행 과정에 중간에 개입하는 구조

2.2. 멀티모달은 어떻게 하나가 되었나

이전에 언급되었듯 Vision, Language, Action을 하나의 Achitecture로 만드려는 시도는 있어왔음

e.g. Traditional Robotics → Perception + Natural Language Process + Control = Discrete Modules linked with manual defined interfaces and data transofmation

이를 극복하기 위해 Large-scale Pretrained Encoders와 Transfromer Based Architectures를 통해 end-to-end module을 구현함

→ 이제 모델이 interpret visual observations and linguistic instructions within the same computational space, allowing flexible, context-aware reasoning할 수 있게됨 e.g. CLIPort, VIMA

최근에는 이를 더 발전시켜 temporal, spatial grounding을 활용해 더 발전해왔음 e.g. RT-2, Octo

2.3. VLA는 어떻게 세상을 이해하는가 (Tokenization and Representation)

위와 같이 VLA가 발전할 수 있었던 이유는 token-based representation framework 덕분이었음

→ semantic reasoning (What needs to be done) 뿐만 아니라 Control policy execution (How to do it)을 learnable하며 compositional 한 방식으로 구현함

2.3.1. Prefix Tokens — Encoding Context and Instruction

Contextual Backbone of VLA Models

• These tokens encode the environmental scene (via images or video) and the accompanying natural language instruction into compact embeddings that prime the model’s internal representations

2.3.2. State Tokens — Embedding the Robot’s Configuration

be aware of their internal physical state

• State tokens, which encode real-time information about the agent’s configuration—joint positions, force-torque readings, gripper status, end-effector pose, and even the locations of nearby objects

• state tokens encapsulate spatial features
• The transformer model integrates this state representation with environmental and instructional context to generate navigation actions that dynamically adapt to changing surroundings.

2.3.3. Action Tokens — Autogressive Control Generation

autoregressively generated by the model to represent the next step in motor control

→ Each token corresponds to a low-level control signal, such as joint angle updates, torque values, wheel velocities, or high-level movement primitives

• Training VLA model을 위해서는 hybrid learning paradigm 이 요구됨

  • Web-based semantic knowledge
  • task-grounded information from robotics datasets

• 그래서 어떤 데이터 소스를 사용해야하는가?

  1. Large-scale internet-derived corpora form the backbone of the model’s semantic prior.

     e.g. Image-caption pairs, instruction-following datasets, visual questioning-answering corpora

     • Vision encoder와 language encoder의 pretaining을 가능하게 한다
     • contrastive나 masked modeling objectives를 사용하는데 (e.g. CLIP-style contrastive learning or language modeling losses) 이는 vision modalities와 language modalities를 shared embedding space에 놓기 위함이다.
     • semantic understanding alone is insufficient for physical task execution

  2. Grounding the model in embodied experience

     • Robot trajectory datasets—collected either from realworld robots or high-fidelity simulators
       • to teach the model how language and perception translate into action
       • e.g. RoboNet [37], BridgeData [50], and RT-X

  • 최근 동향에서는 multistage or multitask training strategies를 활용하고 있다고 한다

    • pretrained on vision-language datasets

      1. using masked language modeling
         • fine-tuned on ronot demostration data using token level autogressive loss
      2. using curriculum learning
         • simpler tasks (e.g. object pushing)→ more complex tasks (e.g.multistep manipulation)
      3. Domain Adaptation으로 접근하기도 함
         • Open-VLA or sim-to-real transfer to bridge gap between synthetic and real-work distributions

      By unifying semantic priors with task execution data, these learning paradigms allow VLA models to generalize across tasks, domains, and embodiments—forming the backbone of scalable, instructionfollowing agents capable of robust real-world operation.

2.5. Adaptive Control and Real-Time Execution

• This training paradigm not only helps

  1. the model understand object affordances (e.g., apples can be grasped) and action outcomes (e.g., lifting requires force and trajectory)

  2. promotes generalization to novel scenarios

     e.g. Google DepMind’s RT-2 (Robot Transformer 2)

     Action generation as a form of text generation where each action token corresponds to a discrete command in a robot’s control space

Another strength of VLAs lies in their ability to perform adaptive control, using real-time feedback from sensors to adjust behavior on the fly

[153] Serpiva, V., Lykov, A., Myshlyaev, A., Khan, M.H., Abdulkarim, A.A., Sautenkov, O., Tsetserukou, D., 2025. Racevla: Vla-based racing drone navigation with human-like behaviour. arXiv preprint arXiv:2503.02572

execution이 진행되는 동안 state token이 실시간으로 업데이트되며 (e.g. seonsor inputs, joint feedback) action plan을 수정할 수있게 된다

→ human-like adaptability and core advantage of VLA systems over pipeline-based robots

3. Notes

이번 논문을 읽고 정리한 VLA의 핵심은 다음과 같습니다.

VLA는 시각 정보와 언어 지시를 실제 행동으로 변환하는 embodied AI 모델

기존의 Vision-Language Model이 “무엇이 보이고, 그것이 무엇을 의미하는가”를 다뤘다면, VLA는 한 단계 더 나아가 “그렇다면 지금 무엇을 해야 하는가”를 다룹니다.

이 점에서 VLA는 로봇, 자율주행, embodied agent, physical AI와 강하게 연결됩니다.

특히 제가 관심 있는 animal behavior analysis나 embodied interaction 관점에서도 VLA는 단순히 행동을 분류하는 모델을 넘어 환경을 보고, 행동 맥락을 이해하고, 다음 행동을 예측하거나 상호작용하는 agent 구조로 확장될 가능성이 있다고 느꼈습니다.

오늘은 Vision-Language-Action Model의 Concept 파트를 중심으로 정리해보았습니다. 부정확한 내용이나 더 궁금한 점이 있다면 댓글로 남겨주시면 감사하겠습니다.

개발 계기, 방향성, 그리고 지금 어디까지 왔는지

BMO에서 오리까지

시작은 유튜브 영상 하나였습니다.

!youtube[l5ggH-YhuAw?si=DsvleeSHJ7Jy7cn4]

BMO local agent를 라즈베리파이로 구현하는 영상을 보고, *"이거 재밌겠다"* 싶어서 그 뒤에는 매일 당근마켓에서 중고 라즈베리파이를 찾아보다 결국 구매까지 해버렸습니다.

하지만 생각보다 비쌌다는..

이전에 핀과 제이크의 어드벤처 타임을 재밌게 보기도 했고 BMO처럼 말 걸면 반응하는 로컬 AI가 가슴을 설레게 했었습니다.

그런데 막상 따라 만들다 보니 질문이 생겼습니다.

단순히 재현하는 것 이상으로, 어떤 가치를 더할 수 있을까?

그 고민을 하던 차에 이전에 실험을 진행했던 카메라 트랩 이미지 처리가 생각났습니다.

이 프로젝트 자체는 Animal Classification에 지나지 않았지만 어떻게 하면 단순 분류에서 더 나아가 연구를 할 수 있을까하고 생각을 하게 되었고, 여기서 Vision-Language Model이 "이게 어떤 동물이다"를 넘어서 "어떤 동물이 어떤 상황에서 이런 행동을 한다"라고 설명을 더 풍부하게 해줄 수 있다는 점을 배웠기 때문입니다.

그때부터 라즈베리파이 + 비전 + 행동 인식 으로 실제 구현을 해보고 싶다라는 개발 방향이 잡혔습니다.

그 뒤 그럼 어떤 영상을 대상으로 진행을 할까 생각했고 이전에 영국에 갔을때 공원에서 흔히 볼 수 있었던 오리가 생각나 유튜브 오리 영상을 보며 영상이 풍부하게 있다는 점, 사람들에게 낯설지 않은 동물이라는 점을 근거로 오리 영상을 선정하게 되었습니다.

*"오리가 지금 뭘 하는지 알아채고, 행동이 바뀌면 반응하고, 세션이 끝나면 요약까지 해주는 걸 만들면 어떨까?"*

기존 행동 분류 시스템은 대부분 "이게 A다, B다"를 판단하는 데서 끝납니다. 하지만 제가 만들고 싶었던 것은 단순 분류 결과를 출력하는 시스템이 아니라, 관찰 결과에 반응하고 세션 단위로 요약해주는 작은 인터페이스였습니다.

물론 실제로 만드는 경험 자체가 저에게 도움이 될거라 생각하기도 했습니다.

무엇을 만드는가

깃허브 링크: https://github.com/MelonChicken/be-more-agent-duck

BMOD는 오리 영상을 입력받아 행동을 분류하고, 행동 변화에 반응하며, 세션이 끝나면 리포트를 생성하는 lightweight behaviour observation system입니다.

파이프라인을 한 줄로 정리하면 이렇습니다:

입력 영상
  → 5초 구간 분할
  → 구간당 10프레임 샘플링
  → CLIP 임베딩 평균
  → Logistic Regression 분류
  → 이벤트 감지
  → 반응 생성
  → 세션 리포트 (CSV + JSON)

행동 클래스는 세 가지입니다: resting, feeding, exploring. 그리고 분류 신뢰도가 낮을 때를 위한 uncertain 상태도 따로 두었습니다.

왜 이 스택인가

처음엔 성능만 따지면 훨씬 좋은 end-to-end video model도 고려했습니다. 그런데 이 프로젝트의 최종 목표는 Raspberry Pi 5 위에서 오프라인으로 돌아가는 것이었기에 무거운 모델은 선택지가 될 수 없었습니다.

CLIP 임베딩 + Logistic Regression 조합은 다음 이유로 선택했습니다:

• Pi에 이식하기 충분히 가볍다
• 노트북에서 개발하고 Pi로 옮기기 쉽다
• 행동 분류에 필요한 visual feature를 CLIP이 이미 잘 뽑아준다

물론 리스크도 있습니다. CLIP feature가 행동 자체보다 장면 특성 (배경, 조명 등)에 반응할 수 있다는 점. 그래서 초기 라벨링은 클래스당 20구간씩, 대표 구간만 먼저 구성해서 threshold validation을 꼼꼼히 할 계획입니다.

지금 어디까지 왔나

현재는 핵심 파이프라인 구현을 진행 중입니다.

• ✅ 전체 아키텍처 설계 완료
• ✅ ffmpeg 기반 프레임 추출 (5초 구간, 10프레임)
• ✅ CLIP 임베딩 추출 및 구간 평균
• ✅ Logistic Regression 분류기 (dummy fallback 포함)
• ▢ 행동 전환 기반 이벤트 감지 로직
• ▢ SessionLogger 클래스 설계 (CSV + JSON 듀얼 출력)
• ▢ tkinter GUI 연동
• ▢ 실제 오리 데이터셋 라벨링 (클래스당 20구간 목표)
• ▢ Pi 이식 및 오프라인 실행 검증

몇 가지 설계 결정을 공유하면:

행동 전환 반응은 최소 3구간(15초) 유지 후에만 발생합니다. 5초 단위 분류가 짧게 흔들릴 수 있어서, 노이즈 반응을 막기 위한 smoothing 규칙입니다. (MIN_STABLE_SEGMENTS = 3으로 상수화)

uncertain 처리도 신중하게 설계하는 중입니다. CONFIDENCE_THRESHOLD = 0.55 미만이면 uncertain으로 처리하는데, 연속 uncertain이 일정 횟수 이상 발생할 때만 별도 반응을 보여줍니다. 시연 중 uncertain이 너무 자주 뜨면 몰입감이 깨지기 때문입니다.

앞으로의 계획

단기적으로는 이렇게 진행합니다:

• 2주 내: 데이터셋 구성 완료 + notebook 기반 baseline 검증
• 이후: Pi 이식 → 오프라인 시연 가능한 형태로 완성
• 더 나아가: 날짜별 행동 패턴 분석 파이프라인, 다른 동물로 확장

리포트 포맷도 이미 정해놨습니다. 세션이 끝나면 행동 타임라인 + 대표 이벤트 5개 + 2~3문장 요약이 나옵니다. 연구자나 학생이 오리를 오래 관찰한 뒤 "오늘 뭐가 있었지?"를 바로 파악할 수 있습니다.

마치며

아직 데모와 실험 결과는 완성되지 않았지만, 프로젝트의 구조와 방향성은 어느 정도 잡혔고 코드는 조금씩 쌓이고 있습니다.

다음 글에서는 데이터셋 라벨링 기준과 CLIP feature가 행동을 얼마나 잘 구분하는지 초기 실험 결과를 들고 와보겠습니다.

오리를 관찰하는 AI를 만드는 일이 생각보다 재미있습니다.

난이도: ★★☆☆☆ • solved on: 2026-01-20

문제 요약

• 문제 유형: 백트래킹(Backtracking), 순열
• 요구사항: 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 모든 순열을 출력해야 한다.

사용 개념

1. 자료구조

   • int[] : 현재 선택된 수열을 저장
   • boolean[] : 숫자 사용 여부(중복 방지) 체크
   • StringBuilder : 출력 성능 최적화

2. 알고리즘/기법

   • 재귀 (recursion)
   • 백트래킹 (backtracking)

3. 핵심 키워드

   • 순열 (permutation)
   • 깊이 (depth)
   • 상태 복원 (backtracking)

풀이 아이디어

1. 문제 분해

• 길이가 M인 수열을 만든다.
• 각 자리에 1부터 N까지의 숫자를 하나씩 시도한다.
• 이미 사용한 숫자는 다시 사용할 수 없다.
• 길이가 M이 되면 하나의 완성된 순열로 출력한다.

2. 재귀 함수의 목적 정의 (핵심)

sequence(n, depth)의 역할

• depth == M → 길이 M의 수열이 완성되었으므로 출력하고 종료한다.
• 그렇지 않으면 → 1부터 N까지 순회하면서 아직 사용하지 않은 숫자를 선택한다.

3. 핵심 로직 흐름

sequence(depth):
    if depth == M:
        수열 출력
        return
>
    for i = 1 to N:
        if i가 아직 사용되지 않았다면:
            i를 선택
            sequence(depth + 1)
            i 선택 취소 (상태 복원)

4. 백트래킹의 본질

• 선택: visited[i] = true, tempArr[depth] = i
• 재귀 호출: 다음 자리로 이동
• 복원: visited[i] = false

코드

import java.util.*;

class Main {
    public static int[] tempArr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();

        tempArr = new int[r];
        visited = new boolean[n + 1];

        sequence(n, 0);
        System.out.println(sb);
    }

    public static void sequence(int n, int depth) {
        if (depth == tempArr.length) {
            for (int i = 0; i < tempArr.length; i++) {
                sb.append(tempArr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tempArr[depth] = i;
                sequence(n, depth + 1);
                visited[i] = false; // 상태 복원
            }
        }
    }
}

시간·공간 복잡도

• 시간 복잡도: O(N! / (N−M)!)
• 공간 복잡도: O(N + M)

어려웠던 점

• 재귀를 사용해야 한다는 것은 알았지만 재귀 함수 하나가 정확히 무엇을 책임지는지를 정의하지 못해 접근이 어려웠다.
• “이 함수가 한 번 호출될 때 정확히 무엇을 결정하는가”를 잡지 못해 로직을 외부 설명에 의존하게 되었다.

배운 점 및 팁

• 재귀 문제에서는 반드시 “이 함수는 어떤 단위의 문제를 해결하는가”를 먼저 문장으로 정의해야 한다.
• 백트래킹은 선택 → 재귀 → 복원 이 3단계가 항상 세트로 움직인다.
• 순열/조합 문제에서 depth는 현재까지 몇 개를 골랐는지를 의미하는 지표로 이해하면 훨씬 명확해진다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/15649
• 참고 자료: https://velog.io/@gayeong39/백트래킹-알고리즘-BackTracking

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 15650번 N과 M (2)
  • 백준 - 15651번 N과 M (3)

• 확장 문제 (GPT 추천)

  • 백준 - 9742번 순열
  • 백준 - 6603번 중복 없는 조합

난이도: ★★★☆☆ • solved on: 2026-01-19

문제 요약

• 문제 유형: 재귀, 분할 정복
• 요구사항: 크기 N의 정사각형에 대해 중앙이 비어 있는 별 패턴을 재귀적으로 출력해야 한다.

사용 개념

1. 자료구조

   • List<String> : 각 줄을 문자열 단위로 관리

2. 알고리즘/기법

   • 재귀 (Recursion)
   • 분할 정복 (Divide and Conquer)

3. 핵심 키워드

   • 패턴 생성 (pattern generation)
   • 재귀적 구조 (recursive structure)

풀이 아이디어

1. 문제 분해

• N이 1일 때는 "*" 하나로 종료되는 기저 조건을 둔다.
• N이 1보다 클 경우, 크기 n/3의 별 패턴을 먼저 만든다.
• 만들어진 작은 패턴을 이용해
  • 위: ***
  • 중간: * *
  • 아래: *** 형태로 결합한다.

2. 핵심 로직 흐름

   getStars(n):
       if n == 1:
           return ["*"]
   >
       small = getStars(n / 3)
   >
       for s in small:
           add s + s + s
   >
       for s in small:
           add s + blank + s
   >
       for s in small:
           add s + s + s

3. 예외 처리
   • n == 1 인 경우 바로 리스트를 반환하여 재귀를 종료한다.

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> result = getStars(n);
        StringBuilder sb = new StringBuilder();
        for(String s : result) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }

    public static List<String> getStars(int n) {

        List<String> result = new ArrayList<>();

        if(n == 1) {
            result.add("*");
            return result;
        }

        List<String> smallStars = getStars(n / 3);
        for(String s : smallStars) {
            result.add(s + s + s);
        }

        String blank = "";
        for(int i = 0; i < n / 3; i++){
            blank += " ";
        }

        for(String s : smallStars) {
            result.add(s + blank + s);
        }

        for(String s : smallStars) {
            result.add(s + s + s);
        }
        return result;
    }
}

시간·공간 복잡도

• 시간 복잡도: O(N²)

  • 최종적으로 N×N 크기의 별 패턴을 생성해야 하므로 출력량 자체가 O(N²)이다.

• 공간 복잡도: O(N²)

  • 모든 줄을 문자열로 저장하는 리스트 때문이며, 재귀 호출 스택은 O(log₃N) 수준이다.

어려웠던 점

• 처음에 접근 자체가 되지 않았다.
• 재귀를 쓰는 것은 알겠지만, 반환 타입을 String, List<String>, String[][] 중에서 무엇으로 할지 결정하지 못해 설계 단계에서 막혔다.
• 결국 재귀 함수의 역할을 n 크기의 패턴 전체를 반환한다로 명확히 정의하면서 해결할 수 있었다. (int로 받고 List<String>으로 리턴하기)

배운 점 및 팁

• 재귀 문제에서는 함수의 역할을 한 문장으로 정의하는 것이 매우 중요하다.

  • 재귀 함수는 유닛 단위로 반복하는 것이기 때문

  • 예: getStars(n)은 n 크기의 별 패턴을 문자열 리스트로 반환한다

• 출력 형태가 줄 단위로 고정되어 있다면 List<String>이 매우 자연스럽다.

• 중앙을 비우는 문제는 대부분 3등분 구조를 가지므로, 먼저 작은 패턴을 만든 뒤 조합하는 방식이 핵심이다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2447
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 4779번 칸토어 집합
  • 백준 - 10993번 별 찍기 - 18

• 확장 문제 (GPT 추천)

  • 백준 - 10991번 별 찍기 - 16
  • 백준 - 10997번 별 찍기 - 22

난이도: ★★☆☆☆ • solved on: 2026-01-17

문제 요약

• 문제 유형: 문자열 처리, 정렬, 해시

• 요구사항:

  • 길이가 M 이상인 단어만 대상으로 한다

  • 단어를 다음 기준으로 정렬해야 한다

    1. 자주 나오는 단어일수록 앞에 온다
    2. 길이가 긴 단어일수록 앞에 온다
    3. 사전 순으로 앞서는 단어일수록 앞에 온다

사용 개념

1. 자료구조

   • HashMap<String, EnglishWord> : 단어별 등장 횟수 저장
   • List<EnglishWord> : 정렬을 위한 리스트

2. 알고리즘/기법

   • 해시를 이용한 빈도 카운팅
   • Comparable 구현을 통한 커스텀 정렬
   • 스트림 정렬 (stream().sorted())

3. 핵심 키워드

   • 빈도 기반 정렬 (frequency sort)
   • 다중 조건 정렬 (multi-level sort)

풀이 아이디어 및 코드

방법 1 : Custom Comparator

1. 문제 분해

• 단어를 입력받으며 길이가 M 미만이면 무시한다
• HashMap에 단어를 key로, 등장 정보를 value로 저장한다
• 이미 등장한 단어면 횟수만 증가시킨다

2. 정렬 전략
   • EnglishWord 클래스에서 Comparable을 구현한다
   • 정렬 기준
     1. 등장 횟수 오름차순
     2. 단어 길이 오름차순
     3. 사전 역순

   • Collections.reverseOrder()로 전체 정렬 결과를 뒤집는다
3. 출력
   • 정렬된 리스트를 순회하며 단어만 출력한다

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] cmds = br.readLine().split(" ");
        int n = Integer.parseInt(cmds[0]);
        int m = Integer.parseInt(cmds[1]);

        HashMap<String, EnglishWord> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;

            if(!map.containsKey(word)) {
                map.put(word, new EnglishWord(word));
            } else {
                map.get(word).updateCnt();
            }
        }

        List<EnglishWord> list = map.values().stream()
                .sorted(Collections.reverseOrder())
                .toList();

        StringBuilder sb = new StringBuilder();
        for(EnglishWord word : list) {
            sb.append(word.word).append("\n");
        }

        System.out.println(sb);
    }

    static class EnglishWord implements Comparable<EnglishWord> {
        String word;
        int cnt;

        public EnglishWord(String word) {
            this.word = word;
            this.cnt = 1;
        }

        @Override
        public int compareTo(EnglishWord anotherWord){
            if(cnt - anotherWord.cnt != 0){
                return cnt - anotherWord.cnt;
            }
            if(word.length() - anotherWord.word.length() != 0){
                return word.length() - anotherWord.word.length();
            }
            return -1 * word.compareTo(anotherWord.word);
        }

        public void updateCnt(){
            cnt++;
        }
    }
}

방법 2 : Custom Class 없이 Comparator 활용

1. 개선 포인트

• 별도의 클래스를 만들지 않는다
• 정렬 기준을 Comparator 체이닝으로 한눈에 드러낸다
• reverseOrder()를 쓰지 않아도 된다

2. 정렬 기준 명시
   • 빈도 내림차순
   • 길이 내림차순
   • 사전 오름차순

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        List<String> result = map.keySet().stream()
                .sorted((a, b) -> {
                    if(map.get(a) != map.get(b))
                        return map.get(b) - map.get(a);
                    if(a.length() != b.length())
                        return b.length() - a.length();
                    return a.compareTo(b);
                })
                .toList();

        StringBuilder sb = new StringBuilder();
        for(String w : result) sb.append(w).append("\n");
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

어려웠던 점

• HashMap의 value 객체들을 기준에 맞게 정렬하려다 보니 클래스를 만들고 Comparable을 구현하는 과정이 길어졌다

배운 점 및 팁

• 정렬 기준이 명확한 문제는 Comparator가 가독성이 더 좋다
• Comparable + reverseOrder() 방식은 기준이 많아질수록 직관성이 떨어질 수 있다
• 단순 빈도 문제는 Map<String, Integer> 구조만으로도 충분하다

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/20920
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1302반 베스트셀러
  • 백준 - 11536번 줄 세우기

• 확장 문제 (GPT 추천):

  • 백준 - 1181번 단어 정렬

난이도: ★★☆☆☆ • solved on: 2026-01-17

문제 요약

• 문제 유형: 정렬, 구현, 해시/카운팅
• 요구사항: N개의 정수에 대해 산술평균(반올림), 중앙값, 최빈값, 범위를 출력해야 한다.

사용 개념

1. 자료구조

   • 방법 1: int[], HashMap<Integer,Integer>, ArrayList<Integer>
   • 방법 2: int[] count (8001) 카운팅 배열

2. 알고리즘/기법

   • 방법 1: 정렬 + 해시맵 빈도
   • 방법 2: 카운팅 (Counting) + 누적합 스캔

3. 핵심 키워드

   • 반올림 (rounding)
   • 최빈값 tie-breaking (동률 시 두 번째로 작은 값)
   • 값 범위 고정 (-4000~4000)

풀이 아이디어 및 코드

방법 1 : HashMap + 정렬

1. 문제 분해

• 입력을 받으면서 min, max, total을 갱신한다.
• HashMap으로 각 수의 빈도를 센다.
• 최빈값 후보를 ArrayList에 모은 뒤 정렬로 규칙(두 번째로 작은 값)을 맞춘다.
• arr를 정렬해 중앙값을 구한다.

2. 핵심 로직 흐름

   입력:
       min/max/total 갱신
       map[num]++
   >
   map 순회:
       최대 빈도 cnt 갱신
       cnt와 같으면 후보 추가
       cnt보다 크면 후보 초기화 후 추가
   >
   arr 정렬 -> 중앙값
   후보 정렬 -> 최빈값 결정(두 번째로 작은 값)

3. 예외 처리
   • 평균은 Math.round(1.0 * total / n) 형태로 반올림한다.

import java.util.*; 
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =  Integer.parseInt(br.readLine());

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int total = 0;
        int freq = 4001;
        int cnt = 0;
        ArrayList<Integer> arrayList = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] arr = new int[n];
        map.put(freq, -1);

        for(int i = 0; i < n; i++){
            int temp =  Integer.parseInt(br.readLine());
            if(temp < min) min = temp;
            if(temp > max) max = temp;

            total += temp;

            if(map.containsKey(temp)){
                map.put(temp,map.get(temp)+1);
            } else {
                map.put(temp,1);
            }
            arr[i] = temp;
        }
        for(Integer key : map.keySet()){
            if(map.get(key).equals(-1)){
                continue;
            }
            if(map.get(key).equals(cnt)){
                arrayList.add(key);
            }
            if(map.get(key).compareTo(cnt)>0){
                arrayList.clear();
                arrayList.add(key);
                cnt = map.get(key);
            }
        }
        Arrays.sort(arr);
        arrayList.sort(Collections.reverseOrder());
        System.out.println(Math.round(1.0 * total / n));
        System.out.println(arr[n/2]);
        if(arrayList.size() == 1){
            System.out.println(arrayList.get(0));
        } else {
            System.out.println(arrayList.get(arrayList.size()-2));
        }
        System.out.println(max-min);
    }
}

방법 2 : 카운팅 배열로 동시 처리

1. 문제 분해

• 값 범위가 -4000 ~ 4000으로 고정이므로 count[8001]로 빈도를 센다(인덱스는 x + 4000).
• 평균: sum / n을 Math.round로 반올림한다.
• 중앙값: 누적 빈도가 (n+1)/2 이상이 되는 지점을 찾는다(문제에서 N은 홀수).
• 최빈값: 최대 빈도를 찾은 뒤, 오름차순 스캔 중 최빈값을 만나는 두 번째 값을 답으로 한다(동률 규칙 충족).
• 범위: max - min을 출력한다.

2. 핵심 로직 흐름

   입력:
       sum, min, max 갱신
       count[x+4000]++
   >
   median:
       누적합 >= (n+1)/2 되는 최초 값
   >
   mode:
       maxFreq 구함
       i=0..8000 오름차순으로 스캔하며
           count[i]==maxFreq 인 값을 발견할 때마다 found++
           found==1이면 mode=값
           found==2이면 mode=값(두 번째로 작은 값)로 확정

3. 예외 처리
   • 평균 반올림은 음수도 포함하므로 Math.round((double)sum / n)으로 처리한다.

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] count = new int[8001]; // -4000~4000 => +4000 shift
        long sum = 0;

        int min = 4001;
        int max = -4001;

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            sum += x;
            if (x < min) min = x;
            if (x > max) max = x;
            count[x + 4000]++;
        }

        // 1) 산술평균
        int mean = (int) Math.round((double) sum / n);

        // 2) 중앙값 (N은 홀수)
        int target = (n + 1) / 2;
        int cumulative = 0;
        int median = 0;
        for (int i = 0; i < 8001; i++) {
            cumulative += count[i];
            if (cumulative >= target) {
                median = i - 4000;
                break;
            }
        }

        // 3) 최빈값 (여러 개면 두 번째로 작은 값)
        int maxFreq = 0;
        for (int i = 0; i < 8001; i++) {
            if (count[i] > maxFreq) maxFreq = count[i];
        }

        int mode = 0;
        int found = 0;
        for (int i = 0; i < 8001; i++) {
            if (count[i] == maxFreq) {
                mode = i - 4000;
                found++;
                if (found == 2) break; // 두 번째로 작은 최빈값 확정
            }
        }

        // 4) 범위
        int range = max - min;

        StringBuilder sb = new StringBuilder();
        sb.append(mean).append('\n');
        sb.append(median).append('\n');
        sb.append(mode).append('\n');
        sb.append(range).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N) (정렬)
• 공간 복잡도: O(N) (배열 + 맵/리스트)

방법 2

• 시간 복잡도: O(N + K) (K=8001 고정) → 사실상 O(N)
• 공간 복잡도: O(K) → 사실상 O(1)

어려웠던 점

• 최빈값을 어떻게 저장하고 찾아낼지에 대해 골머리를 앓았다 처음 접근 (방법1)에서는 따로 HashMap을 저장하여 cnt를 확인했는데 나중 접근을 통해 카운팅 배열을 활용해볼 수 있다는 걸 확인했다.

배운 점 및 팁

• 값의 범위가 작고 고정이면 HashMap정렬보다 카운팅 배열이 구현도 단순하고 성능도 안정적이다.
• 최빈값 동률 규칙은 정렬 후 두 번째를 요구하므로, 오름차순 스캔 중 두 번째로 만나는 최빈값을 고르는 방식이 가장 안전하다. (시간 복잡도는 증가하나, 공간복잡도는 간결하다)
• 평균 반올림은 음수도 포함하므로 Math.round((double)sum / n)처럼 double로 변환해 처리하는 편이 명확하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2108
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 10989번 수 정렬하기 3
  • 백준 - 2587번 대표값2
  • 백준 - 2592번 최빈수 구하기

• 확장 문제 (GPT 추천):

  • 백준 - 11650번 좌표 정렬하기
  • Hackerrank - Day 0: Mean, Median, and Mode

난이도: ★☆☆☆☆ • solved on: 2026-01-15

문제 요약

• 문제 유형: 수학, 약수 성질
• 요구사항: 어떤 수 (N)의 진짜 약수들(1과 (N) 제외)이 주어질 때, (N)을 구해야 한다.

사용 개념

1. 자료구조

   • 입력 순회(최솟값/최댓값 갱신)

2. 알고리즘/기법

   • 약수의 짝(pair) 성질 이용

3. 핵심 키워드

   • 약수 쌍(divisor pair), 최소/최대 약수

풀이 아이디어

왜 최소 약수 × 최대 약수 = N 이 되는가?

핵심은 약수는 항상 쌍으로 존재한다는 성질이다.

• 어떤 수 $N$에 대해 약수 $d$가 있으면, 항상 $N/d$도 약수이다.
• 따라서 약수들은 $(d, N/d)$ 형태의 짝으로 묶인다.
• 이때 각 짝의 곱은 항상 ($d \times (N/d) = N$) 이다.

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long max = Long.MIN_VALUE;
        long min = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            long temp = Long.parseLong(st.nextToken());
            if (temp > max) max = temp;
            if (temp < min) min = temp;
        }

        System.out.println(min * max);
    }
}

시간·공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

어려웠던 점

• 왜 최소 약수와 최대 약수를 곱하면 원래 수 N이 되는지 직관적으로 이해가 안됐다. 하지만 테스트 케이스를 기준으로 규칙성을 찾아 이해는 안되지만 구현하니 됐다.
• “약수는 쌍으로 묶이고, 가장 작은 약수의 짝이 가장 큰 약수”라는 연결이 바로 떠오르지 않았다.

배운 점 및 팁

• 약수 문제는 대부분 짝(pair) 성질을 떠올리면 식이 단순해진다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1037
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 2501번 약수 구하기
  • 백준 - 9506번 약수들의 합

• 확장 문제 (GPT 추천) :

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 3036번 링

난이도: ★★☆☆☆ • solved on: 2026-01-13

문제 요약

• 문제 유형: 자료구조(Queue/Stack), 시뮬레이션 최적화
• 요구사항: 주어진 type(0=queue, 1=stack)과 초기 값들로 구성된 구조에 대해, 입력 m개를 순서대로 넣고 최종적으로 빠져나오는 값을 출력해야 한다.

사용 개념

1. 자료구조

   • Deque : 앞/뒤 삽입·삭제가 O(1)

2. 알고리즘/기법

   • 불필요한 시뮬레이션 제거

3. 핵심 키워드

   • queue만 결과에 영향
   • 초기 queue 값의 “흐름”을 한 덩어리로 처리

풀이 아이디어 및 코드

방법 1 : 시뮬레이션 기반 풀이 (시간 초과로 실패)

전체를 매 입력마다 끝까지 시뮬레이션해서 m × n이 발생하는 구조라 시간 복잡도가 커진다.

Deque를 활용해 구현

//  queuestack

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        String[] types = br.readLine().split(" ");
        String[] values = br.readLine().split(" ");

        int m = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        String num = "";
        String temp = "";
        for(int i = 0; i < m; i++){
            num = st.nextToken();
            for(int j = 0; j < n; j++){
                if(types[j].equals("0")){
                    temp =  values[j];
                    values[j] = num;
                    num = temp;
                } else {
                    continue;
                }
            }

            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

배열을 활용해 구현

//  queuestack

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        int[] types = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

        int m = Integer.parseInt(br.readLine());

        StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<n;i++){
            arr.add(new ArrayDeque<>());
            types[i] = Integer.parseInt(st.nextToken());
            arr.get(i).add(Integer.parseInt(st2.nextToken()));
        }
        int num;
        for(int i = 0; i < m; i++){
            arr.get(0).add(Integer.parseInt(st3.nextToken()));
            for(int j = 0; j < n-1; j++){
                if(types[j] == 0){
                    num = arr.get(j).pollFirst();
                } else {
                    num = arr.get(j).pollLast();
                }
                arr.get(j+1).add(num);
            }

            if(types[n-1] == 0){
                num = arr.get(n-1).pollFirst();
            } else {
                num = arr.get(n-1).pollLast();
            }
            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

방법 2 : 관찰로 O(n+m) 만들기

1. stack(type=1)은 “넣고 바로 빼는 효과”만 내서 최종 출력 흐름에 남는 값이 없다.
2. queue(type=0)의 초기 값들만 결과 스트림에 영향을 준다.
3. 따라서 초기 queue 값들을 한 번에 모아두고, 매 쿼리마다 입력값 push → 맨 앞 pop만 하면 된다.

핵심 로직 흐름

q = deque()
>
// 초기 상태에서 type=0(queue)인 값만 모음
for i in 0..n-1:
    if type[i] == 0:
        q.addLast(value[i])
>
// 실제 출력은 가장 "앞에서" 빠져나오므로,
// 위에서 모은 queue 값들의 순서를 "역방향"으로 맞춰야 한다.
// (구현에서는 q에 넣는 순서를 뒤에서부터 넣거나, 앞에 addFirst로 넣는다)
>
for each x in queries:
    q.addLast(x)
    print q.pollFirst()

Java 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] type = new int[n];
        int[] val = new int[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) type[i] = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) val[i] = Integer.parseInt(st2.nextToken());

        int m = Integer.parseInt(br.readLine());
        StringTokenizer st3 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        Deque<Integer> q = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            if (type[i] == 0) q.addFirst(val[i]);
        }

        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st3.nextToken());
            q.addLast(x);
            sb.append(q.pollFirst()).append(' ');
        }

        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(n × m)
• 공간 복잡도: O(n)

방법 2

• 시간 복잡도: O(n + m)
• 공간 복잡도: O(n) (type=0인 값 개수만큼)

어려웠던 점

• 처음 실제 시뮬레이션 기반의 풀이에서 시간복잡도를 어떻게 더 줄여야 하는지 감이 잡히지 않았다.
• 매 쿼리마다 n개 구조를 끝까지 시뮬레이션하는 방식에서 병목이 생겼다.

배운 점 및 팁

• 전체를 그대로 시뮬레이션하지 말고, 출력에 실제로 영향을 주는 요소만 남기는 관찰이 핵심이다.
• 이 문제는 type=1(stack)이 결과 흐름에서 사라지는 요소라서, type=0(queue)만 모아 한 번에 처리하면 된다.
• Deque로 addLast / pollFirst만 하면 쿼리당 O(1)로 끝난다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/24511
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 12789번 도키도키 간식드리미
  • 백준 - 18258번 큐 2
  • 백준 - 10866번 덱

• 확장 문제 (GPT 추천) :

  • 백준 - 1021번 회전하는 큐
  • 백준 - 1966번 프린터 큐
  • HackerRank - Queue using Two Stacks

이 글은 딥러닝 역사에서 전환점으로 평가받는 AlexNet 논문을 읽으며, 이 모델이 왜 “작동했는가”를 정리하기 위해 작성되었습니다.

성능 비교가 아니라, 당시 기술적 제약 속에서 어떤 선택들이 문제를 해결했는지를 중심으로 살펴보고자 합니다. 또한 이 글은 Standford University의 CS231n의 일부를 참고로 하였습니다. 따라서 Computer Vision에 대해 더 궁금하신 독자께서는 링크를 참고해주세요. link

Paper Information

Title: ImageNet Classification with Deep Convolutional Neural Networks

Authors: Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton

Journal: Advances in Neural Information Processing Systems (NeurIPS 2012) link

arXiv ID: NFI

Ⅰ. Introduction

“To recognize the real world, how much capacity does a model really need?”

Ⅰ.1. 데이터 규모와 문제 복잡성

이 논문에 대한 이야기를 하기 전, 먼저 이러한 모델이 나올 수 있었고 효과가 있었던 배경에 대해 설명하려 합니다.

디지털 사진이 막 도입된 시점 (1960s), 객체 탐지 (Object Recognition)은 상당히 어려운 분야였습니다. 대상이 어디있는가? 어디까지 대상으로 할 것인가?에 대한 Vision Representation에 대한 고전적인 질문과 함께 (Stages of Visual Representation, David Marr, 1970s) 아직은 디지털 데이터에 대해 정리하고 확립하는 과정이었습니다.

그 과정에서 나온 데이터 셋은 NORB와 Caltech-101/256, CIFAR-10/100 등이 있습니다. 이들은 당시 기준으로는 표준적이고 잘 만들어진 데이터셋이지만 데이터의 규모는 객체 인식 연구를 하기에는 충분하지 않은 규모 (수만 장)였습니다.

물론 간단한 인식은 labrl-preserving transformation릏 통한 데이터 증강을 활용하여 이 규모에서도 꽤나 잘 이루어졌지만 문제는 가려짐, 배경 변화, 시점 변화 같은 상황의 경우 단순한 증강으로는 한계점이 있어 더 많은 데이터가 필요해졌습니다.

이때 등장한 것이 바로 ImageNet이었습니다. ImageNet은 2009년 대규모 객체 인식을 위해 등장한 이미지 데이터셋으로. 한 객체 범주 (synset) 당 평균 1000개의 이미지라는 대규모의 데이터셋입니다. 이로써 객체 인식을 위한 데이터의 규모는 갖추어졌지만, 많은 데이터가 필요해짐에 따라 또한 모델의 용량도 이에 맞춰 더 커져야 했습니다.

Ⅰ.2. 모델 용량(Capacity)의 필요성

데이터의 규모가 커진 만큼 데이터의 복잡도 (e.g. 시점 변화, 조명 변화, 배경 변화...)도 느러 연구진은 CNN을 선택하게 됩니다. CNN의 특성은 바로 다음 섹션에서 설명합니다.

이러한 배경에서 연구진들은 다음과 같은 선택을 통해 모델의 용량을 키워 AlexNet의 성능을 끌어올립니다.

• 약 6천만개의 파라미터

• 5개의 Convolution Layer와 3개의 Fully Connected Layer
• 상대적으로 큰 Neural Network

Ⅱ. Key Design Choices

Architecture is not just structure; it is prior knowledge.

Ⅱ.1. Convolution Neural Network (CNN)

CNN은 기존의 Neural Network에 기반하였기에 학습 가능한 weights와 bias를 가진 neuron을 가지고 있습니다. 하지만 가장 큰 변화점은 입력값이 이미지라는 가정하에 다양한 이미지의 특성을 구조에 녹일 수 있다는 점입니다.

다시 말해 "이미지의 내부에는 인접한 픽셀 간의 강한 상관관계가 있다 (Locality)"라는 가정과 "이미지의 통계적 특성은 픽셀의 위치에 따라 크게 변하지 않는다 (Stationarity)"라는 가정을 전제하에 두고 있습니다.

그렇기에 기존의 Nerual Network와는 다르게 더 적은 connection와 parameter를 가지고 더 쉽게 학습 가능하게 됩니다. 물론 이때 약간의 성능하락은 존재하지만 여전히 매력적인 선택지입니다.

하지만 그럼 왜 진작 사용하지 않았는가? 라고 묻는다면 이 모델을 실행할 하드웨어 자원이 부족했기 때문입니다. 하지만 연구진은 당시에 개발된 GPU (GTX 580 3GB GPU)를 CNN에 맞게 적용하여 사용해서 큰 CNN 모델에 대한 학습을 가능하게 합니다. 이를 연구진은 아래와 같이 말합니다.

Luckily, current GPUs, paired with a highly-optimized implementation of 2D convolution, are powerful enough to facilitate the training of interestingly-large CNNs, and recent datasets such as ImageNet contain enough labeled examples to train such models without severe overfitting.

하지만 연구진은 Convolution layer만 사용하지 않고 기존의 Fully connected network 역시 사용합니다. (It contains eight learned layers — five convolutional and three fully-connected.)

Fully-connected layer란? 한 레이어의 모든 뉴런이 바로 이전 레이어의 모든 뉴런과 연결되어 있는 레이어를 말합니다.

1. convolutional layer

• 국소 영역 (local receptive field)만 봄
• 가중치 공유 (weight sharing)
• 공간 구조 (spatial structure)를 유지

2. fully-connected layer

• 공간 구조를 더 이상 고려하지 않음
• 입력 전체를 하나의 벡터로 보고
• 모든 입력을 종합해서 판단

Ⅱ.2. Rectified Linear Units (ReLUs) Nonlinearity

기존의 $tanh$, sigmoid 계열의 활성화 함수는 깊은 네트워크 (입력값의 절댓값이 커질 수록) gradient saturation 문제를 유발하게 됩니다. (e.g. $sigmoid(x) = (1 + e^{-x})^{-1}$) 이런 문제를 해결하고자 연구진은 $f(x) = max(0,x)$ ReLU를 활성화 함수로 지정하여 이러한 saturation 문제를 해결합니다.

Saturation은 왜 문제가 되는가? Fig. 1에서 나타나듯이 Epoch에 따라 Training Error Rate를 보면 ReLU가 tanh에 비해 훨씬 빠른 학습 속도를 보여줍니다. 이 이유는 입력값의 절댓값이 커질 수록 출력이 거의 일정해지고 그렇기에 gradient가 매우 작아지며 학습이 느려지게 되기 때문입니다.

이 ReLU를 통해 학습 속도는 대폭 향상되고, 큰 모델에서도 non-saturating한 활성 함수를 사용하기에 실험을 반복적으로 수행 가능하며, 이러한 깊은 CNN 학습이 현실적인 시간 내에 완료되도록 합니다.

Ⅱ.3. GPU parallelization

연구진이 사용한 GTX 580 GPU는 3GB의 메모리 크기를 가지고 있기에 1,200,000개의 훈련 데이터를 학습하기에 적합한 Network를 돌리기에는 한 GPU 가지고는 모자랐습니다. 그렇기에 연구진의 선택은 두개의 GPU를 통해 병렬 연산을 진행하는 방식을 선택했습니다.

단순히 Kernel이나 Neuron을 절반으로 나누어 각각 넣는게 아니라 GPU간의 communication을 특정 레이어에서만 전체 연결을 허용합니다. 예를 들어 3번 레이어의 Kernel은 2번 레이어의 모든 Kernel로부터 정보를 받습니다. (이는 두 GPU에서의 값을 모두 받는다는 것을 의미합니다. Communication 발생)

하지만 4번 레이어의 Kernel의 경우 동일 GPU에 있는 3번 레이어의 데이터만 입력값으로 받게 됩니다. 이렇게 함으로써 개별 GPU가 소화할 수 있는 적정한 연산량 안에서의 communication 양을 세밀하게 조절할 수 있게 해줍니다.

이러한 구조는 Columnar CNN과 상당히 유사하지만 AlexNet은 column이 독립적이지 않다라는 차이점이 있습니다.

정리하자면 이러한 GPU 병렬화는 개별 GPU로는 수행하지 못하는 양의 연산을 수행하고, 단일 Convolution layer에서 개별 GPU로만 구현했을 때보다 약간 빠르게 수행합니다.

Ⅱ.4. Reducing Overfitting

물론 모델이 커짐에 따라 너무나도 학습 데이터를 잘 학습한 나머지 발생하는 과적합은 필연적이게 됩니다. 이러한 과적합을 연구진은 계속해서 언급했고, 아래의 두가지 전략을 통해 과적합을 줄입니다.

Ⅱ.4.1. Data Augmentation

AlexNet에서는 두가지 방법으로 데이터 증강을 진행합니다. 첫번째는 이미지를 임의로 224 by 224 patch로 잘라내고 좌우 반전을 하는 방식으로 증강을 이루는 것입니다. 이러한 데이터 증강은 훈련 데이터셋의 사이즈를 키우는 방식으로 과적합을 줄여줍니다.

두번째 방법으로는 학습 이미지의 RGB 채널의 강도를 PCA (Primary Component Analysis)를 통해 도출된 principal component를 곱하는 방식으로 조정을 해줍니다. 또한 RGB pixel 값들의 eigenvector와 eigenvalue를 활용해서 단순히 색을 무작위로 변화하는 방식으로 증강한 것이 아니라 현실적인 조명 변화를 흉내내며 증강하게 됩니다.

그래서 Generating image translations and horizontal reflec tions와 Altering the intensities of the RGB channels in training images 두가지 데이터 증강 전략을 통해 과적합을 방지할 수 있었다고 합니다.

Ⅱ.4.2. Dropout

당시 비교적 최근에 소개된 dropout 전략이 AlexNet에 적용된 두번째 과적합 방지 전략입니다. Dropout 전략은 각각의 히든 뉴런의 출력값에 대해서 일정한 확률 (AlexNet에서는 0.5)로 0이 되게끔 설정하는 전략입니다. 이러한 방식으로 누락된 ("Dropped out") 뉴런들은 다음 레이어에 영향을 미치지 않아 back propagation에도 참여하지 못하게 됩니다.

이렇게 함으로써 학습을 진행할 때마다 구조가 조금씩 다른 네트워크를 학습하는 동시에 weight 값은 공유를 하기에 샘플마다 다른 개별 특징에 초점이 맞춰지는게 아니라 더 일반적인 공통된 특징에 더 집중되어 학습을 진행하게 됩니다. 이렇게 진행함으로써 과적합을 방지할 수 있게 됩니다.

Ⅲ. Limitations & Conclusion

결론적으로 AlexNet은 당시의 GPU 발전과 함께 대규모의 깊은 CNN을 구현했고 그 해 2012년 Large Scale Visual Recognition Challenge (LSVRC)에서 top-5 test error rate로 15.3%로 두번째로 낮았던 26.2%보다 훨씬 뛰어난 성능을 보였습니다.

물론 실험을 단순하게 하기 위해 Unsupervised pre-traing을 사용하지 않았으므로 성능을 더 끌어올릴 수 있는 여지가 있다는 점, 인간의 시각 시스템에 비해서는 아직 너무나도 작은 모델이라는 연구진의 자기 평가가 있었지만 그럼에도 불구하고 깊은 CNN 하나만으로 순수 지도학습에서 당시 최고 성능을 달성했다는 점에서 의미있는 시도였습니다.

오늘은 Computer Vision에서 굵직한 마일 스톤 중 하나인 AlexNet에 대한 논문을 읽어보았습니다. 이번에도 긴 글 읽어주셔서 감사합니다.

의견이나 질문이 있다면 댓글로 남겨주시기 바랍니다.

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 에라토스테네스의 체, 구현
• 요구사항: 입력된 구간 [n, m] 안에 존재하는 모든 소수를 한 줄씩 출력해야 한다.

사용 개념

1. 자료구조

   • boolean[] : 합성수 여부 (표시 배열)
   • StringBuilder : 출력 누적

2. 알고리즘/기법

   • 에라토스테네스의 체 (Sieve of Eratosthenes)
   • 배수 마킹 (Marking multiples)

3. 핵심 키워드

   • 소수 (prime number)
   • 합성수 (composite number)
   • 배수 (multiple)

풀이 아이디어

1. 문제 분해

• 0과 1은 소수가 아니므로 먼저 합성수 취급(true)로 표시한다.
• 2부터 시작해, 아직 체크되지 않은 수(소수 후보)를 만나면 그 수의 배수들을 합성수(true)로 표시한다.
• 최종적으로 arr[i] == false인 수만 출력한다(소수만 남김).

2. 핵심 로직 흐름

   arr[0] = arr[1] = true  // 소수 아님(합성수 취급)
   for i = 2 .. m:
       if arr[i] == true: continue
       for j = 2 while i*j <= m:
           arr[i*j] = true  // 합성수 표시
   >
   for i = n .. m:
       if arr[i] == false: print i

3. 예외 처리
   • 0, 1은 소수가 아니므로 반드시 제외한다.
   • boolean 배열의 기본값이 false이므로, “표시되면 합성수(true)” 방식으로 관리한다.

코드

import java.util.*;
import java.io.*;

class Main {
    public static boolean[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new boolean[m+1];
        StringBuilder sb = new StringBuilder();
        makeSlieve();

        for(int i = n; i <= m; i++){
            if(!arr[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
    public static void makeSlieve(){
        arr[0] = true;
        arr[1] = true;
        for(int i = 2; i < arr.length; i++){
            if(arr[i]) continue;
            for(int j = 2; i*j < arr.length; j++){
                arr[i*j] = true;
            }
        }
    }
}

시간·공간 복잡도

• 시간 복잡도: 대략 O(M log log M) 수준 (에라토스테네스의 체)

  • 구현상 i*j 형태로 마킹하므로 상수는 커질 수 있으나, 기본 아이디어는 체 방식이다.

• 공간 복잡도: O(M) (boolean[m+1])

어려웠던 점

• boolean 배열의 기본값이 무엇인지 몰라서 혼란이 있었다.
• 처음에는 소수만 true를 기대했지만 실제로는 기본값이 전부 false라서 의도와 반대로 동작하는 문제가 생겼다.
• 그래서 합성수만 true로 표시하고, 끝까지 false로 남은 값이 소수가 되도록 방향을 바꿔 해결했다.
• 참고 블로그를 통해 boolean 기본값이 false임을 확인했다.

배운 점 및 팁

• Java에서 boolean[]의 기본값은 false라서, 보통은 합성수만 true로 마킹하는 형태가 구현이 편하다.
• 배수 마킹은 j = i*i부터 시작하거나 $i <= \sqrt{m}$까지만 돌리면 더 빠르게 만들 수 있다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1929
• 참고 블로그/깃허브: https://nanarin.tistory.com/53

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1978번 소수 찾기
  • 백준 - 4948번 베르트랑 공준

• 확장 문제 (GPT 추천):

  • 백준 - 17103번 골드바흐 파티션
  • HackerRank - Day 25: Running Time and Complexity

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 소수 판정, 브루트포스
• 요구사항: 각 테스트케이스마다 입력된 수 n 이상에서 가장 작은 소수를 찾아 출력해야 한다.

사용 개념

1. 자료구조

   • StringBuilder : 여러 줄 출력 누적
   • BufferedReader : 빠른 입력

2. 알고리즘/기법

   • 소수 판정(Prime Check)
   • n부터 1씩 증가시키며 첫 소수 탐색

3. 핵심 키워드

   • 소수(prime number)
   • √n 까지 나눗셈 검사

풀이 아이디어

1. 문제 분해

• 각 입력 target에 대해 current = target으로 시작한다.
• current가 소수인지 확인하고, 아니면 current++ 하며 반복한다.
• 처음으로 소수 판정을 통과한 current를 출력한다.

2. 핵심 로직 흐름

   for i in 1..T:
       current = target
       while true:
           if isPrime(current):
               print current
               break
           current++

3. 예외 처리
   • 0, 1은 소수가 아니므로 false로 처리한다.
   • 2는 소수이므로 true로 처리한다.

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long target;
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < n; i++){
            String s = br.readLine();
            target = Long.parseLong(s);
            long current = target;
            while(true){
                if(isPrime(current)){
                    sb.append(current).append("\n");
                    break;
                }
                current++;
            }
        }
        System.out.print(sb);
    }
    public static boolean isPrime(long n){
        if(n == 1 || n == 0) return false;
        if(n == 2) return true;
        for(long i = 2; i*i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

시간·공간 복잡도

• 시간 복잡도: 최악의 경우 O(K × √M)

  • K = 소수를 찾을 때까지 증가한 횟수
  • M = 검사 중인 수 크기

• 공간 복잡도: O(1) (입력/출력 버퍼 제외)

어려웠던 점

• 0, 1이 소수가 아니라는 예외를 놓치면 오답이 나기 쉽다.
• target부터 시작해서 다음 소수를 찾는 반복 구조에서, 소수 판정 함수가 정확해야 한다.

배운 점 및 팁

• 소수 판정은 2부터 √n까지만 나눠보면 된다.
• 밀러-라빈 테스트를 구현하면 더 효율적인 검증이 가능하지만 아직 어려워 이해하지 못했다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/4134
• 참고 블로그/깃허브:
  • Miller–Rabin primality test
  • [Algo] 밀러-라빈 소수 판별법(Miller-Rabin Primality Test)

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1929번 소수 구하기
  • 백준 - 4948번 베르트랑 공준

• 확장 문제 (GPT 추천):

  • 백준 - 17103번 골드바흐 파티션
  • HackerRank - Day 25: Running Time and Complexity

난이도: ★★★☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 최대공약수(GCD)
• 요구사항: 기존 가로수 위치를 기준으로 모든 가로수 사이의 간격이 동일해지도록 만들 때, 추가로 심어야 하는 가로수의 개수를 구해야 한다.

사용 개념

1. 자료구조

   • long[] : 가로수 좌표 및 간격 저장

2. 알고리즘/기법

   • 정렬
   • 유클리드 호제법 (Euclidean Algorithm)

3. 핵심 키워드

   • 인접 간격
   • 간격들의 최대공약수 (GCD)
   • (gap / gcd) - 1

풀이 아이디어 및 코드

방법 1 : 현재 가로수의 위치 정보를 저장

1. 문제 분해

• 가로수 위치를 배열에 저장한다.
• 인접한 가로수 사이의 간격 배열 gaps를 만든다.
• 모든 간격의 GCD를 구해 currentGcd로 저장한다.
• 첫 위치부터 마지막 위치까지 currentGcd 간격으로 하나씩 훑으면서, 기존 가로수가 없는 위치를 카운트한다.
  2. 핵심 로직 흐름

     gaps 생성
     gaps 전체 GCD 계산 → currentGcd
     start부터 end까지 currentGcd 간격으로 순회
     기존 위치에 없으면 count++

  3. 한계

• 좌표 범위가 커질 경우, while 문 순회 횟수가 불필요하게 많아질 수 있다.
• 실제로는 계산으로 바로 구할 수 있는 값을 시뮬레이션으로 처리하고 있다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] positions = new long[n];
        long[] gaps = new long[n-1];
        long currentGcd = 1;

        for(int i=0;i<n;i++){
            positions[i] = Long.parseLong(br.readLine());
            if(i > 0){
                gaps[i-1] = positions[i] - positions[i-1];
            }
            if(i == n-1){
                break;
            }
        }

        Arrays.sort(positions);

        for(int i=0;i<n-1;i++){
            if(i == 1){
                currentGcd = gcd(gaps[i-1], gaps[i]);
            } else if (i > 1){
                currentGcd = gcd(currentGcd, gaps[i]);
            }
        }

        int i = 0;
        int j = 0;
        long start = positions[0];
        int count = 0;

        while((start + currentGcd * j) <= positions[positions.length-1]){
            if(positions[i] == start + currentGcd * j){
                i ++;
                j ++;
                continue;
            } else {
                count++;
                j ++;
            }
        }
        System.out.println(count);
    }

    public static long gcd(long a,long b){
        while(b != 0){
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

방법 2 : 위치 정보 대신 간격 합산에 집중

1. 핵심 관찰

• 최종적으로 모든 가로수 사이의 간격은 “인접 간격들의 최대공약수(GCD)”가 된다.

2. 계산 방식
   • 어떤 간격 gap이 있고 최종 간격이 gcd라면,
   • 해당 구간은 gap / gcd개의 구간으로 나뉜다.
   • 이미 양 끝에 나무가 있으므로, 추가로 필요한 나무 수는 (gap / gcd) - 1이다.
3. 전체 답
   • 모든 인접 간격에 대해 위 값을 더한 합이다.
4. 핵심 로직 흐름

   positions 정렬
   모든 인접 gap의 GCD 계산 → g
   answer = Σ (gap / g - 1)

import java.util.*;
import java.io.*;

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long[] pos = new long[N];
        for (int i = 0; i < N; i++) {
            pos[i] = Long.parseLong(br.readLine());
        }

        Arrays.sort(pos);

        long g = pos[1] - pos[0];
        for (int i = 2; i < N; i++) {
            g = gcd(g, pos[i] - pos[i - 1]);
        }

        long answer = 0;
        for (int i = 1; i < N; i++) {
            long gap = pos[i] - pos[i - 1];
            answer += (gap / g) - 1;
        }

        System.out.println(answer);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: $O(N log N + R / G)$ (R: 좌표 범위, G: 최종 간격)
• 공간 복잡도: $O(N)$

방법 2

• 시간 복잡도: $O(N log N)$
• 공간 복잡도: $O(N)$

어려웠던 점

• 구현 자체는 단순했지만, 시뮬레이션을 수식으로 치환할 수 있다는 발상에 도달하기 어려웠다.
• “모든 위치를 직접 세어보지 않아도 된다”는 점을 떠올리지 못해 시간복잡도 개선 방향을 잡는 데 시간이 걸렸다.

배운 점 및 팁

• 동일 간격을 만드는 문제는 대부분 간격들의 GCD로 귀결된다.
• 좌표 문제에서 “하나씩 훑는 방식”이 보이면, 간격 단위로 계산할 수 있는지 먼저 의심해보는 것이 좋다. (위치 정보의 필요성에 대한 의심)
• 추가 개수는 시뮬레이션보다 $Σ (gap / gcd - 1)$ 형태의 수식이 훨씬 안전하고 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2485
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 2981번 검문

• 확장 문제 (GPT 추천):

  • 백준 - 14476번 최대공약수 하나 빼기
  • 백준 - 1735번 분수 합 `

난이도: ★★☆☆☆ • solved on: 2026-01-02

문제 요약

• 문제 유형: 유클리드 호제법, 수학
• 요구사항: 테스트 케이스마다 두 자연수의 최소공배수(LCM) 를 출력해야 한다.

사용 개념

1. 자료구조

   • StringTokenizer, StringBuilder

2. 알고리즘/기법

   • 최대공약수 (GCD)
   • 최소공배수 (LCM) 관계식: $LCM(a,b) = (a / GCD(a,b)) * b$

3. 핵심 키워드

   • 유클리드 호제법 (Euclidean Algorithm)
   • 공약수/공배수

풀이 아이디어 및 코드

방법 1 : 공통 인수 탐색

1. 문제 분해

• 두 수의 공약수를 작은 값부터 나눠가며 공통 인수를 result에 누적한다.
• 나눠 떨어지면 a, b를 그 인수로 나누고, 나눠 떨어지지 않을 때만 divisor++ 한다.

2. 핵심 로직 흐름

   result = 1
   divisor = 2
   while divisor < a or divisor < b:
       if a%divisor==0 and b%divisor==0:
           result *= divisor
           a /= divisor
           b /= divisor
       else:
           divisor++
   result *= a*b

3. 예외 처리
   • 한 수가 다른 수의 배수인 경우, 더 큰 수가 LCM이므로 바로 출력한다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int a = 0;
        int b = 0;
        int result = 1;

        for(int i = 0; i < n; i++){
            String[] lines = br.readLine().split(" ");

            a = Integer.parseInt(lines[0]);
            b = Integer.parseInt(lines[1]);
            result = 1;

            if(a%b == 0 || b%a == 0){
                sb.append(Math.max(a,b)).append("\n");
                continue;
            }
            int min = Math.min(a, b);
            int divisor = 2;
            while(divisor < a || divisor < b){
                if(a%divisor==0 && b%divisor==0){
                    result *= divisor;
                    a /= divisor;
                    b /= divisor;
                } else {
                    divisor++;
                }
            }

            result *= a * b;
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 유클리드 호제법으로 GCD → LCM

1. 문제 분해

• 최소공배수는 공약수를 “직접” 모두 찾기보다, 최대공약수(GCD) 만 구하면 바로 계산할 수 있다.

2. 핵심 로직 흐름

   gcd(a,b):
       while b != 0:
           t = a % b
           a = b
           b = t
       return a
   >
   lcm = a / gcd(a,b) * b

3. 예외 처리
   • 곱이 커질 수 있으므로 long을 사용한다.

import java.io.*;
import java.util.*;

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long g = gcd(a, b);
            long l = (a / g) * b;   // overflow 방지를 위해 a/g 먼저 수행
            sb.append(l).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 :

• 시간 복잡도: 최악 O(max(a,b))에 가깝게 커질 수 있다. (작은 약수부터 전부 시도하는 구조)
• 공간 복잡도: O(1)

방법 2 :

• 시간 복잡도: O(log(min(a,b))) (유클리드 호제법)
• 공간 복잡도: O(1)

어려웠던 점

• 처음에는 for (divisor++)로 약수를 검사했는데, 이 방식은 같은 소수가 여러 번(예: p²) 나눠지는 경우를 연속으로 반영하기 어렵다는 문제가 있었다.
• 그래서 “약수를 찾지 못할 때만 ++ 한다”는 방식으로 while로 바꿔 중복 약수를 처리하도록 수정했다.

배운 점 및 팁

• 최소공배수는 공약수를 직접 누적하기보다 GCD만 구해도 LCM = a / GCD * b로 바로 계산한다.
• 유클리드 호제법은 구현이 짧고 입력 범위가 커져도 안정적으로 빠르다.
• 곱셈이 들어가는 문제는 int 대신 long을 먼저 떠올리는 습관이 중요하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1934
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 2981번 검문

• 확장 문제 (GPT 추천):

  • 백준 - 3036번 링
  • HackerRank - Euclid's Algorithm

난이도: ★☆☆☆☆ • solved on: 2026-01-01

문제 요약

• 문제 유형: 집합(Set), 해시(Hash)
• 요구사항: 두 집합 A, B에 대해 대칭 차집합 $((A-B) ∪ (B-A))$의 원소 개수를 출력해야 한다.

사용 개념

1. 자료구조

   • HashSet : 원소 존재 여부를 평균 O(1)로 검사한다.

2. 알고리즘/기법

   • 집합 연산의 크기 계산
   • 교집합 개수 세기

3. 핵심 키워드

   • 대칭 차집합 (symmetric difference)
   • 교집합 (intersection)

풀이 아이디어 및 코드

방법 1 : 합집합을 만들고 교집합 개수만큼 빼기

1. 문제 분해

• A, B를 각각 HashSet에 넣는다.
• A∪B 역할을 하는 setAorB를 만든다.
• setAorB를 순회하며 A와 B에 모두 있으면(교집합) count++ 한다.
• 최종 답을 |A∪B| - |A∩B| 로 계산한다.

2. 핵심 로직 흐름

   setAorB = A ∪ B
   count = |A ∩ B|
   answer = |setAorB| - count

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);
        int count = 0;

        HashSet<String> setA = new HashSet<>(n);
        HashSet<String> setB = new HashSet<>(m);
        HashSet<String> setAorB = new HashSet<>();
        StringTokenizer stA = new StringTokenizer(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());

        while(stA.hasMoreTokens()){
            String temp = stA.nextToken();
            setA.add(temp);
            setAorB.add(temp);
        }

        while(stB.hasMoreTokens()){
            String temp = stB.nextToken();
            setB.add(temp);
            setAorB.add(temp);
        }

        for(String a : setAorB){
            if(setA.contains(a)&&setB.contains(a)){
                count++;
            }
        }

        System.out.println(setAorB.size()-count);
    }
}

방법 2 : 교집합만 세서 n + m - 2*common로 바로 계산

1. 개선 포인트

• 대칭 차집합 크기 = (|A-B| + |B-A|) 이고, 이는 (|A| + |B| - 2|A∩B|) 로 정리된다.
• 따라서 합집합 set을 따로 만들 필요가 없다.

2. 핵심 로직 흐름

   common = 0
   A를 set에 저장
   B를 읽으면서 A에 있으면 common++
   answer = n + m - 2*common

3. 추가 개선
   • 입력이 자연수이므로 HashSet<Integer>로 처리하는 편이 의미상 맞고, 변환 비용도 줄인다.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        HashSet<Integer> setA = new HashSet<>(n);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            setA.add(Integer.parseInt(st.nextToken()));
        }

        int common = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (setA.contains(x)) common++;
        }

        int answer = n + m - 2 * common;
        System.out.println(answer);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M) 평균 (해시 연산 가정)
• 공간 복잡도: O(N + M) (setA, setB, setAorB 저장)

방법 2

• 시간 복잡도: O(N + M) 평균
• 공간 복잡도: O(N) (setA만 유지)

어려웠던 점

• 없음

배운 점 및 팁

• 대칭 차집합 크기는 $n + m - 2 * |A∩B|$ 로 바로 계산하는 편이 구현과 메모리 측면에서 더 단순하다.
• 이 문제는 최대 200,000개 원소까지 가능하므로, 이중 루프 대신 해시 기반 포함 검사로 풀어야 한다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1269
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 1764번 듣보잡
  • 백준 - 7785번 회사에 있는 사람
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • HackerRank - No Idea!
  • HackerRank - Two Strings

난이도: ★★☆☆☆ • solved on: 2026-01-01

문제 요약

• 문제 유형: 해시 (Hash), 문자열, 정렬
• 요구사항: 듣도 못한 사람과 보도 못한 사람의 교집합을 찾아 사전식(오름차순)으로 출력해야 한다.

사용 개념

1. 자료구조

   • HashMap<String, Integer> / HashSet<String>
   • ArrayList<String> : 교집합 결과 저장
   • Collections.sort() : 사전식 정렬

2. 알고리즘/기법

   • 해시를 이용한 중복/존재 여부 체크
   • 교집합 추출 후 정렬

3. 핵심 키워드

   • 교집합 (intersection)
   • 사전식 정렬 (lexicographical order)

풀이 아이디어 및 코드

방법 1 : HashMap 카운팅으로 교집합 판별

1. 문제 분해

• 듣도 못한 사람 N명을 map에 넣고 값 1로 기록한다.
• 보도 못한 사람 M명을 입력받아 map.getOrDefault(name, 0) + 1로 누적한다.
• 최종적으로 값이 2인 키가 교집합(듣보잡)이므로 리스트에 담는다.
• 리스트를 사전식으로 정렬한 뒤 개수와 이름들을 출력한다.

2. 핵심 로직 흐름

   map에 N명은 1로 저장
   M명을 읽으며 map[name] += 1
   map 전체 순회하며 value==2인 key만 list에 저장
   list 정렬 후 출력

3. 예외 처리
   • 교집합이 0명일 수도 있으므로, 출력 형식을 그대로 유지한다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n =  Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        HashMap<String, Integer> map = new HashMap<>();
        int total = 0;
        StringBuilder sb = new StringBuilder();
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < n; i++){
            map.put(br.readLine(), 1);
        }

        for(int i = 0; i < m; i++){
            String name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        for(String key : map.keySet()){
            if(map.get(key)==2){
                total++;
                list.add(key);
            }
        }
        System.out.println(total);

        Collections.sort(list);

        for(int i = 0; i < list.size(); i++){
            sb.append(list.get(i)).append("\n");
        }

        System.out.println(sb);

    }
}

방법 2 : HashSet으로 존재 확인 후 교집합만 수집

1. 개선 포인트

• HashMap으로 전체를 카운팅하지 않고, 듣도 목록을 Set에 저장한 뒤 보도 입력을 읽으면서 set.contains(name)인 경우만 결과 리스트에 추가한다.
• 교집합 후보만 모으므로, 불필요한 map.keySet() 전체 순회가 사라지고 코드가 더 단순해진다.

2. 핵심 로직 흐름

   set에 N명 저장
   M명을 읽으며 set에 있으면 result에 추가
   result 정렬 후 출력

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        HashSet<String> heard = new HashSet<>(n * 2);
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            heard.add(br.readLine());
        }

        for (int i = 0; i < m; i++) {
            String name = br.readLine();
            if (heard.contains(name)) {
                result.add(name);
            }
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append('\n');
        for (String name : result) sb.append(name).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M + K log K) (K = 교집합 크기, 정렬 비용)
• 공간 복잡도: O(N + M) 수준 (map에 둘 다 들어갈 수 있음)

방법 2

• 시간 복잡도: O(N + M + K log K)
• 공간 복잡도: O(N + K) (듣도 set + 결과만 보관)

어려웠던 점

• 처음에는 HashMap으로 false/true 판별 방식도 고려했지만, 사전식 정렬을 해야 해서 결국 카운팅 방식으로 저장한뒤 정렬 로직을 따로 구성했다.
• Set.contains(value)는 평균적으로 O(1)인 것을 까먹었다

배운 점 및 팁

• 교집합 문제는 “한 쪽을 Set에 넣고, 다른 쪽을 보면서 contains로 걸러내기”가 가장 단순한 정석 패턴이다.
• 사전식 정렬은 결과 리스트만 정렬하면 되므로, 전체 자료구조를 정렬형(TreeSet)으로 유지할 필요는 보통 없다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1764
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡 (정렬 대신 출력 포맷/자료구조 변형 연습)
  • HackerRank - Hash Tables: Ransom Note

난이도: ★★☆☆☆ • solved on: 2025-12-31

문제 요약

• 문제 유형: 해시맵(HashMap), 카운팅(counting)
• 요구사항: N개의 정수 카드에서 각 질의 수가 몇 개 있는지 개수를 출력해야 한다.

사용 개념

1. 자료구조

   • HashMap<Integer, Integer>: (숫자 → 등장 횟수) 저장

2. 알고리즘/기법

   • 빈도수 카운팅 (frequency counting)
   • getOrDefault를 이용한 안전 조회

3. 핵심 키워드

   • 평균 O(1) 조회
   • 중복 원소 개수(count)

풀이 아이디어 및 코드

방법 1 : HashMap을 활용한 누적 카운팅

1. 문제 분해

• N개의 카드를 읽으면서 map에 숫자별 등장 횟수를 누적한다.
• M개의 질의를 읽으면서 map.getOrDefault(q, 0)으로 개수를 출력한다.

2. 핵심 로직 흐름

   입력 N
   카드 N개를 map에 카운팅
   >
   입력 M
   질의 M개에 대해 map[q] 출력 (없으면 0)

3. 예외 처리
   • 질의 숫자가 없는 경우 0 출력 (getOrDefault)

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        HashMap<Integer, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        String m = br.readLine();
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        while(st.hasMoreTokens()){
            int temp = Integer.parseInt(st.nextToken());
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }

        while(st2.hasMoreTokens()){
            int q = Integer.parseInt(st2.nextToken());
            sb.append(map.getOrDefault(q, 0)).append(" ");
        }

        System.out.println(sb);
    }
}

방법 2 : 정렬 + 이분 탐색

1. 개선 포인트

• 해시맵 풀이도 정답이고 빠르지만, 이 문제는 전형적으로 정렬 후 lower/upper bound로 개수를 세는 풀이도 자주 사용한다.
• 해시맵은 평균 O(1)이지만, 정렬 기반 풀이는 성능이 안정적이고(결정적), 구현 연습 가치가 있다.

2. 핵심 로직 흐름

   카드 배열 정렬
   count(x) = upperBound(x) - lowerBound(x)

3. 예외 처리
   • 카드에 없는 값이면 두 bound가 같아 0

import java.io.*;
import java.util.*;

public class Main {
    static int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    static int upperBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] > target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) cards[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(cards);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int q = Integer.parseInt(st.nextToken());
            int cnt = upperBound(cards, q) - lowerBound(cards, q);
            sb.append(cnt).append(' ');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 (HashMap)

• 시간 복잡도: O(N + M) (평균)
• 공간 복잡도: O(N) (서로 다른 값 개수만큼)

방법 2 (정렬 + 이분 탐색)

• 시간 복잡도: O(N log N + M log N)
• 공간 복잡도: O(N)

어려웠던 점

• 없음

배운 점 및 팁

• 이 문제는 카운팅이므로 해시맵이 가장 직관적이다.

• 코딩 테스트 관점에서는

  • 빠르게 맞추기: 해시맵
  • 기본기/안정성 연습: 정렬 + lower/upper bound 둘 다 정석 범위에 들어간다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/10816
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 10815번 숫자 카드
  • 백준 - 14425번 문자열 집합

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡
  • HackerRank - Frequency Queries

난이도: ★★☆☆☆ • solved on: 2025-12-31

문제 요약

• 문제 유형: 해시맵(HashMap), 문자열 처리, 구현
• 요구사항: 포켓몬 이름 ↔ 번호를 빠르게 상호 변환하여 질의 M개에 답해야 한다.

사용 개념

1. 자료구조

   • HashMap<String, Integer>: 이름 → 번호 조회
   • String[] names: 번호 → 이름 조회 (인덱스 기반)

2. 알고리즘/기법

   • 양방향 매핑 (bidirectional mapping)
   • 질의가 숫자인지/문자인지 판별하여 분기 처리

3. 핵심 키워드

   • 해시 조회
   • 문자열 판별

풀이 아이디어 및 코드

방법 1 : 내 풀이

1. 문제 분해

• names[i]에 i번 포켓몬 이름을 저장한다.
• map에 (이름 → 번호)를 저장한다.
• 질의가 숫자면 names[index], 문자면 map.get(name)을 출력한다.

2. 핵심 로직 흐름

   입력 N, M
   for i=1..N:
       names[i] = pokemon
       map[pokemon] = i
   >
   for each question:
       if (question is number) -> names[number]
       else -> map[question]

3. 예외 처리
   • 없음

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        String[] names = new String[n+1];
        HashMap<String, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= n; i++){
            String pokemon = br.readLine();
            names[i] = pokemon;
            map.put(pokemon, i);
        }

        for(int i = 0; i < m; i++){
            String question = br.readLine();
            if(question.toUpperCase().equals(question)){
                int index = Integer.parseInt(question);
                sb.append(names[index]).append("\n");
            } else {
                sb.append(map.get(question)).append("\n");
            }
        }

        System.out.println(sb);
    }
}

방법 2 : 개선된 최적의 풀이 (숫자 판별 로직 교정)

1. 개선 포인트

• question.toUpperCase().equals(question)는 “질의가 숫자인지” 판별하는 조건으로 부적절하다.
  • 숫자 문자열은 대소문자 변화가 없어서 true가 되지만, 이름이 전부 대문자인 경우도 true가 되어 Integer.parseInt()에서 예외가 난다.
  • 하지만 이 문제에서는 예외가 발생하지 않았다. 와우.

• 따라서 첫 글자가 숫자인지로 판별하는 방식이 안전하고 빠르다. (Character.isDigit(question.charAt(0)))

2. 핵심 로직 흐름

   if Character.isDigit(question.charAt(0)):
       idx = Integer.parseInt(question)
       print names[idx]
   else:
       print map.get(question)

3. 예외 처리
   • 없음 (문제 조건상 숫자 질의는 항상 올바른 번호로 주어진다)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String[] names = new String[n + 1];
        HashMap<String, Integer> map = new HashMap<>(n * 2);

        for (int i = 1; i <= n; i++) {
            String pokemon = br.readLine();
            names[i] = pokemon;
            map.put(pokemon, i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String q = br.readLine();
            if (Character.isDigit(q.charAt(0))) {
                sb.append(names[Integer.parseInt(q)]).append('\n');
            } else {
                sb.append(map.get(q)).append('\n');
            }
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M)
• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N + M)
• 공간 복잡도: O(N)

어려웠던 점

• 없음

배운 점 및 팁

• “문자열이 숫자인지” 판별할 때 대소문자 변환 비교는 목적에 맞지 않다.
• 이 문제처럼 입력이 “번호 또는 이름”으로만 주어질 때는 Character.isDigit(첫 글자)가 가장 간단하고 안전하다.
• 입출력은 BufferedReader + StringTokenizer + StringBuilder 조합이 안정적으로 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1620
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 7785번 회사에 있는 사람

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡
  • 백준 - 10816번 숫자 카드 2
  • HackerRank - Hash Tables: Ransom Note

난이도: ★★★☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬, 해시(좌표 압축)
• 요구사항: 주어진 수열의 각 값에 대해, 중복 제거 후 정렬했을 때의 인덱스를 원래 순서대로 출력해야 한다.

사용 개념

1. 자료구조

   • HashSet : 중복 제거
   • ArrayList : 유니크 값 정렬
   • HashMap : 값 → 압축 인덱스 매핑
   • int[] : 숫자 배열 처리
   • StringTokenizer : 빠른 입력 파싱

2. 알고리즘/기법

   • 좌표 압축 (coordinate compression):
     • 중복 제거 → 정렬 → rank(0..k-1) 부여 → 원본 순서대로 출력
     • 원래 가지고 있던 값들의 의미는 모두 사라지고 오직 순서에 따른 정보만 남게 되는 테크닉

3. 핵심 키워드

   • value-to-rank mapping (값→순위 매핑)
   • unique + sort + map

풀이 아이디어 및 코드

방법 1 : HashSet 중복 제거 + 정렬 + HashMap 매핑

1. 문제 분해

• 입력 수열을 문자열 배열로 받고 HashSet으로 중복 제거한다.
• 유니크 값 리스트(arrList)를 정렬한다.
• 정렬된 유니크 리스트의 인덱스를 HashMap에 저장해 값→순위 매핑을 만든다.
• 원본 배열을 순회하면서 map.get(num)으로 순위를 출력한다.

2. 핵심 로직 흐름

   arr = 입력(문자열)
   set = 중복 제거
   arrList = set -> 리스트 변환
   arrList 정렬
   >
   map[value] = 정렬 인덱스
   for num in arr:
       출력 map[num]

3. 예외 처리
   • 중복이 많아도 HashSet으로 유니크만 정렬하므로 정렬 대상이 줄어든다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String line = sc.nextLine();
        String[] arr = line.split(" ");
        HashSet<String> set = new HashSet<>(Arrays.asList(arr));
        ArrayList<String> arrList = new ArrayList<>(set);

        arrList.sort((a,b)-> {
            return Integer.valueOf(a).compareTo(Integer.valueOf(b));
        });
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < arrList.size(); i++) {
            map.put(arrList.get(i), i);
        }
        StringBuilder sb = new StringBuilder();
        for(String num : arr){
            sb.append(map.get(num)).append(" ");
        }
        System.out.println(sb);
    }
}

방법 2 : int 배열 복사본 정렬 + 중복 스캔으로 rank 매핑 + 빠른 입력

1. 핵심 개선 포인트

• Scanner/split 대신 BufferedReader + StringTokenizer로 입력 비용을 줄인다.
• String 대신 int로 처리해 변환/비교 비용을 줄인다.
• HashSet 없이도, 정렬된 배열을 한 번 스캔하며 중복을 제거하면서 map을 만들 수 있다.

2. 핵심 로직 흐름

   origin = 원본 int[]
   sorted = origin 복사본
   sorted 정렬
   >
   rank = 0
   for i in 0..n-1:
       if i==0 or sorted[i] != sorted[i-1]:
           map[sorted[i]] = rank++
   for x in origin:
       출력 map[x]

3. 예외 처리
   • 음수/큰 수여도 정렬 후 인덱스 기반이므로 문제 없음
   • 출력 마지막 공백은 조건으로 처리

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] origin = new int[n];
        int[] sorted = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(st.nextToken());
            origin[i] = v;
            sorted[i] = v;
        }

        Arrays.sort(sorted);

        HashMap<Integer, Integer> map = new HashMap<>(n * 2);
        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                map.put(sorted[i], rank++);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(origin[i]));
            if (i + 1 < n) sb.append(' ');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: 대략 O(NlongN)

  • 중복 제거 O(N)
  • 유니크 정렬 O(U log U)
  • 매핑/출력 O(N)
  • 단, Scanner와 split, Integer.valueOf 반복 호출로 체감 시간이 늘 수 있다.

• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

어려웠던 점

• 처음 시행착오에서는 정렬된 유니크 리스트에서 순위를 얻기 위해 arrList.indexOf(num) 같은 방식으로 접근했는데, 이 경우 TimeOut이 발생한다.

  • 이유는 원소마다 리스트를 선형 탐색하게 되어 전체가 최악 O(N²) 로 커질 수 있었기 때문이다.

• 결국 “값의 순위를 찾는 과정”은 반복 탐색이 아니라, HashMap으로 값→순위를 미리 만들어서 즉시 조회해야 한다는 점이 핵심이었다.

• 추가로, 입력이 커질 때 Scanner + split 조합이 병목이 될 수 있다는 점도 체감할 수 있는 포인트였다.

배운 점 및 팁

• 좌표 압축은 정렬 + 매핑이 핵심이며, 출력 단계는 반드시 O(1) 조회로 끝나야 한다.
• 대량 입력 문제는 알고리즘이 같아도 입력 방식(Scanner vs BufferedReader) 에서 제출 성능 차이가 크게 난다.
• 숫자는 가능하면 String으로 들고 가지 말고 int로 즉시 파싱하는 편이 깔끔하고 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/18870
• 참고 블로그/깃허브: 좌표 압축 개념 참고 https://wikidocs.net/214469

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 11651번 좌표 정렬하기 2
  • 백준 - 10814번 나이순 정렬

• 확장 문제 (GPT 추천) :

  • Hackerrank - No Idea!
  • Hackerrank - Sorting: Comparator

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬 (Sorting), 안정 정렬 (Stable Sort)
• 요구사항: 회원을 나이 오름차순으로 정렬하되, 나이가 같으면 가입한 순 (입력 순) 을 유지해서 출력한다.

사용 개념

1. 자료구조

   • String[][] : 입력순 인덱스, "나이 이름" 원문을 한번에 저장
   • Member[] : 나이/이름을 분리 저장 (커스텀 클래스)

2. 알고리즘/기법

   • 정렬 (Comparator)
   • 안정 정렬 (stable sort) 활용

3. 핵심 키워드

   • 안정 정렬 (stable sort), 입력 순서 유지 (input order)

풀이 아이디어 및 코드

방법 1 : 배열을 활용한 인덱스 저장

1. 문제 분해

• 각 입력에 대해 원래 순서를 arr[i][0]에 문자열로 저장한다.
• Comparator에서 나이를 비교하고, 같으면 저장한 순서를 비교한다.

2. 핵심 로직 흐름

   arr[i] = (i, "age name")
   정렬: age 오름차순, age 같으면 i 오름차순
   arr[i][1] 출력

3. 예외 처리
   • 나이가 같은 경우 입력 순서 유지

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] arr = new String[n][2];
        for(int i = 0; i < n; i++){
            arr[i][0] = i + "";
            arr[i][1] = br.readLine();
        }
        Arrays.sort(arr, (a, b) -> {
            String[] person1 = a[1].split(" ");
            int person1Age = Integer.parseInt(person1[0]);

            String[] person2 = b[1].split(" ");
            int person2Age = Integer.parseInt(person2[0]);

            if(person1Age != person2Age){
                return person1Age - person2Age;
            }
            return Integer.parseInt(a[0]) - Integer.parseInt(b[0]);
        });

        StringBuilder sb = new StringBuilder();
        for(String[] data : arr){
            sb.append(data[1]).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 입력 파싱 1회 + 안정 정렬 활용

1. 개선 포인트 (시간/공간)

• 방법 1은 정렬 비교할 때마다 split()과 parseInt()가 반복되어 비용이 크다.

• 입력 받을 때 나이/이름을 미리 분리 저장하면 비교가 매우 가벼워진다.

• 또한 이 문제는 “나이가 같으면 입력 순서 유지”인데, Java에서 객체 배열 정렬은 안정 정렬이므로 나이만 비교해도 입력 순서가 유지된다. → “순서 인덱스”를 따로 저장할 필요가 없어진다.

2. 핵심 로직 흐름

   members[i] = (age, name)
   안정 정렬: age 오름차순만 비교
   출력: age + " " + name

3. 예외 처리
   • 나이가 같을 때는 Comparator가 0을 반환 → 안정 정렬이라 입력 순서 유지

import java.io.*;
import java.util.*;

public class Main {

    static class Member {
        int age;
        String name;
        Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Member[] members = new Member[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            members[i] = new Member(age, name);
        }

        Arrays.sort(members, (a, b) -> a.age - b.age); // 나이만 비교 (안정 정렬 활용)

        StringBuilder sb = new StringBuilder();
        for (Member m : members) {
            sb.append(m.age).append(' ').append(m.name).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N * L)

  • 비교 함수가 호출될 때마다 split() 등 문자열 처리 비용이 반복됨 (L = 문자열 길이)

• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)

• 공간 복잡도: O(N)

어려웠던 점

• 입력 순서 정보를 어떻게 유지할지 설계하는 부분에서 난감했고, 처음에는 배열에 인덱스를 같이 저장하는 방식으로 해결했다.

배운 점 및 팁

• 이 문제의 핵심은 나이 같으면 입력 순서 유지인데, 안정 정렬(stable sort) 을 활용하면 인덱스 저장 자체가 필요 없어질 수 있다.
• Comparator 안에서 split() 같은 문자열 파싱을 하면, 정렬 과정에서 같은 문자열을 계속 쪼개게 되어 비효율이 커진다. 따라서 파싱은 최초 저징시 진행하는 것이 좋다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/10814
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 1181번 단어 정렬
  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 10825번 국영수

• 확장 문제 (GPT 추천)

  • 백준 - 18870번 좌표 압축
  • Hackerrank - Sort
  • Hackerrank - Comparator

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬 (Sorting), 문자열 (String), 중복 제거 (Deduplication)
• 요구사항: 단어를 길이 오름차순, 길이가 같으면 사전순 오름차순으로 정렬하되 중복 단어는 한 번만 출력해야 한다.

사용 개념

1. 자료구조

   • ArrayList<String>: 단어 저장 및 정렬
   • HashSet<String>: 중복 제거(개선 풀이)

2. 알고리즘/기법

   • 커스텀 정렬 기준 (Comparator)
   • 중복 제거 후 정렬

3. 핵심 키워드

   • 사전순 정렬 (lexicographical order)
   • 다중 키 정렬 (multi-key sort)
   • 해시 기반 중복 제거 (hash-based dedup)

풀이 아이디어 및 코드

방법 1 : 처음 풀이

1. 문제 분해

• 입력을 받으면서 ArrayList에 저장하되, contains로 중복이면 건너뛴다.
• Comparator로 (길이 → 사전순) 기준으로 정렬한다.

2. 핵심 로직 흐름

   for each word:
       if words.contains(word) continue
       words.add(word)
   >
   words.sort(길이 오름차순, 같으면 사전순)
   출력

3. 예외 처리
   • 중복 단어는 contains로 제거

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<String> words = new ArrayList<>();

        for(int i = 0; i < n; i++){
            String word = br.readLine();
            if(words.contains(word)){
                continue;
            }
            words.add(word);
        }

        words.sort(new StringComparator());

        StringBuilder sb = new StringBuilder();
        for(String word : words){
            sb.append(word).append("\n");
        }
        System.out.println(sb);
    }

    public static class StringComparator implements Comparator<String>{
        @Override
        public int compare(String o1, String o2) {
            if(o1.length() != o2.length()){
                return o1.length() - o2.length();
            }
            if(!o1.equals(o2)){
                return o1.compareTo(o2);
            }
            return 0;
        }
    }
}

방법 2 : HashSet으로 중복 제거 후 정렬

1. 개선 포인트 (시간/공간)

• 방법 1의 병목은 words.contains(word)가 O(N) 이라서, 전체가 최악 O(N²) 로 커질 수 있다는 점이다.
• 중복 제거는 HashSet이 평균 O(1) 이므로 입력 단계가 훨씬 빨라진다.

2. 핵심 로직 흐름

   set에 단어 N개 추가(중복 자동 제거)
   set -> list로 변환
   list.sort(길이 오름차순, 같으면 사전순)
   출력

3. 예외 처리
   • HashSet이 중복을 자동으로 제거하므로 별도 처리 불필요

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(br.readLine()); // 중복 자동 제거
        }

        ArrayList<String> words = new ArrayList<>(set);

        words.sort((a, b) -> {
            if (a.length() != b.length()) return a.length() - b.length();
            return a.compareTo(b);
        });

        StringBuilder sb = new StringBuilder();
        for (String w : words) sb.append(w).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: 최악 O(N² + M log M)

  • 중복 체크 contains가 누적되어 최악 O(N²) 가능
  • M = 중복 제거 후 단어 수

• 공간 복잡도: O(M)

방법 2

• 시간 복잡도: 평균 O(N + M log M)

  • HashSet 삽입 평균 O(1) × N
  • 정렬 O(M log M)

• 공간 복잡도: O(M)

어려웠던 점

• 없음

배운 점 및 팁

• 중복 제거 + 정렬 문제는 보통

  • 입력 단계: HashSet (또는 TreeSet/정렬 필요 시)로 중복 처리
  • 출력 단계: List로 옮겨 sort 이 조합이 가장 자주 쓰인다고 한다.

• 비교 함수에서 if(!o1.equals(o2)) return o1.compareTo(o2); 부분은, 길이가 같다면 그냥 return o1.compareTo(o2); 로 충분하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1181
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 10825번 국영수
  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 10814번 나이순 정렬

• 확장 문제 (GPT 추천)

  • 백준 - 18870번 좌표 압축
  • Hackerrank - Java Comparator
  • Hackerrank - Java Sort